[파이썬(Python)] 백준 10973번 이전 순열

 

 

백준 10973번: 이전 순열

문제 바로 가기

---

📌 문제

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 바로 이전에 오는 순열을 구하는 프로그램을 작성하시오.
사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다.

 

 

 

 

 

 

 

 

 

 

📝 문제 분석

 

 

 

이 문제는 주어진 순열의 이전 순열을 찾는 문제입니다. 즉, 사전순으로 현재 순열보다 조금 더 작은 순열을 찾아야 합니다. 

 

 

 

 

 

✅ 사전순 정렬

 

숫자를 사전에서 단어를 찾듯이 작은 값부터 큰 순서로 정렬할 수 있습니다.

 

예를 들어, 숫자 1234 부터 4321 까지 모든 가능한 숫자를 사전순으로 정렬하면 아래와 같습니다. 

1234  
1243  
1324  
1342  
...
4312  
4321

즉, 어떤 순열이 주어졌을 때 그보다 바로 앞에 오는 순열을 찾아야 합니다. 만약 가장 첫 번째 순열이라면 -1을 출력합니다.

 

 

 

 

 

 

 

💡 해결 방법

 

 

 

1️⃣ Step 1: 뒤에서부터 탐색하며 처음으로 증가가 멈추는 위치 찾기

 

 

순열의 오른쪽에서부터 왼쪽으로 탐색하며 처음으로 감소하는 지점을 찾습니다. 

 

 

 

예제 1: 5 4 3 2 1

5 > 4 > 3 > 2 > 1

숫자를 오른쪽에서부터 보면 5 > 4 > 3 > 2 > 1 로 계속 감소합니다. 즉, 처음으로 감소하는 지점이 없으므로 가장 첫 번째 순열이기 때문에 -1을 출력합니다. 

 

 

 

 

 

예제 3: 1 3 5 4 2

1 3 (5 > 4) (4 > 2)

5 > 4 가 처음으로 감소하는 지점이므로 i = 2 가 됩니다. 

 

 

 

 

 

 

 

2️⃣ Step 2: i에 해당하는 값보다 작은 값 중 가장 큰 값 찾아 교환

 

 

1. seq[i] 보다 작은 숫자 중에서 가장 큰 값 seq[j] 를 찾습니다.

2. seq[i] 와 seq[j] 를 교환(Swap)합니다. 

 

 

 

예제 3: 1 3 5 4 2

바뀌기 전: 1 3 5 4 2
i = 2, seq[i] = 5

i 이후에서 5 보다 작은 숫자 중에서 가장 큰 값을 찾기 → 4 (j = 3) 이 있습니다.

 

 

1 3 4 5 2

5와 4를 교환합니다. 

 

 

 

 

 

 

 

3️⃣ Step 3: i 이후의 값들을 내림차순으로 정렬하기

 

 

이제 i 이후의 숫자들을 내림차순으로 정렬합니다. 

 

 

예제 3: 1 3 5 4 2

바뀌기 전: 1 3 4 5 2
i 이후 부분: 5 2 > 2 5
정렬 후: 1 3 4 2 5

 

 

 

 

 

 

 

 

 

 

👩‍💻 나의 답안

def prev_permutation(seq):
    
    i = n - 2
    while i >= 0 and seq[i] <= seq[i+1]:
        i -= 1

    if i == -1:
        print(-1)
        return
    
    j = n - 1
    while seq[i] <= seq[j]:
        j -= 1

    seq[i], seq[j] = seq[j], seq[i]

    seq[i+1: ] = reversed(seq[i+1: ])
    
    print(*seq)



n = int(input())
seq = list(map(int, input().split()))

prev_permutation(seq)

 

Algorithm/백준/Silver/10973. 이전 순열 at main · kuun1000/Algorithm