[파이썬(Python)] 백준 10972번 다음 순열

 

 

백준 10972번: 다음 순열

문제 바로 가기

---

📌 문제

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을 출력한다.

 

 

 

 

 

 

 

 

 

 

📝 문제 분석

 

 

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

 

 

 

 

 

✅ 사전순 정렬

 

사전순 정렬이란 우리가 사전을 펼쳐서 단어를 찾을 때의 순서를 말합니다. 예를 들어, apple → banana → cherry 는 사전순으로 정렬되어 있습니다. 

 

 

마찬가지로 숫자도 작은 숫자 → 큰 숫자 순서대로 정렬할 수 있습니다. 예를 들어, 숫자 1234 부터 4321 까지 모든 가능한 숫자를 사전순으로 정렬하면 아래와 같습니다. 

1234  
1243  
1324  
1342  
...
4312  
4321

즉, 어떤 숫자가 주어졌을 때 그 다음에 올 수 있는 가장 작은 숫자를 찾아야 합니다. 

 

 

 

 

 

 

 

 

 

💡 해결 방법

 

 

 

1️⃣ Step 1: 뒤에서부터 처음으로 감소하는 위치 찾기

 

 

오른쪽에서 왼쪽으로 탐색하며 처음으로 감소하는 위치를 찾습니다.

 

 

 

예제 1: 1 2 3 4

인덱스:  0  1  2  3
값:      1  2  3  4

 

뒤에서부터 탐색을 시작해서 처음으로 감소하는 숫자를 찾습니다. → 3 < 4 이므로 3 (index = 2)이 바꿀 숫자입니다.

 

 

 

 

 

예제 2: 5 4 3 2 1

인덱스:  0  1  2  3  4
값:      5  4  3  2  1

뒤에서부터 탐색하면 감소하는 지점이 없습니다. → 이미 가장 마지막 순열이므로 -1을 출력합니다. 

 

 

 

 

 

 

 

2️⃣ Step 2: 뒤에서부터 i에 해당하는 값보다 큰 값 찾고 교환하기

 

 

 

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

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

 

 

 

예제 1: 1 2 3 4

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

뒤에서부터 3보다 큰 숫자를 찾기 → 4 (index = 3)이 있습니다.

 

 

바뀐 후:  1 2 4 3

3 과 4 를 교환합니다. 

 

 

 

 

 

 

 

3️⃣ Step 3: i 이후의 값들을 오름차순 정렬하기

 

 

i 이후의 값들은 항상 내림차순으로 정렬된 상태이므로 이를 오름차순으로 변경해야 합니다. 

 

내림차순으로 정렬된 배열을 오름차순으로 바꾸는 가장 빠른 방법은 단순히 뒤집는 것입니다. 따라서 별도의 정렬 없이 reverse() 를 사용하면 됩니다. 

 

 

 

예제 1: 1 2 4 3

바뀌기 전:  1 2 4 3
i 이후 부분: 4 3 (내림차순 → 오름차순 변경)

i 이후의 값들을 오름차순으로 정렬합니다. → 4 뒤에 숫자가 3이고 이미 오름차순으로 정렬되어 있으므로 그대로 둡니다. 

 

 

 

 

 

 

 

 

 

 

👩‍💻 나의 답안

def next_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()))

next_permutation(seq)

 

Algorithm/백준/Silver/10972. 다음 순열 at main · kuun1000/Algorithm