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

2021-01-26

문제 : https://www.acmicpc.net/problem/10972

10972번: 다음 순열

이 문제는 백준 강의에 사용하는 code.plus 문제집 목록에서 'SW 역량 테스트 준비 - 기초' 중 브루트 포스 문제집에 있는 문제임

사실 코드업 100제를 풀려고 했는데 여기있는 문제를 풀기로 했다 

 

처음에 permutations 썼다가 시간초과 나왔음! 당연하다!

 

[시간초과 나온 소스코드]

from itertools import combinations, permutations
n = int(input())
m = list(map(int, input().split()))
lst = []
for i in range(n):
    lst.append(i+1)
per = permutations(lst, n)
cnt = 0
for p in per:
    if cnt == 4:
        for pp in p:
            print(pp, end=' ')
        break
    cnt = 0
    for i in range(n):
        if p[i] != m[i]:
            break
        cnt += 1

 

다른 방법을 생각해보다가 맨 뒤에서부터 수를 비교해가면 list 중간에 i번째 수가 i-1이나 그 앞에 있는 수보다 큰 경우 서로 위치를 swap 한다는 것을 찾았음

근데 두 수 스왑하고 나면 i 뒤에 있는 숫자들 처리를 어떻게 할지 고민하다가 결국 구글링해서 알아냈다

 

예를 들어서

1 2 3 5 4  # 4와 그 앞에 있는 수 중 작은 수인 3의 위치를 swap 

1 2 4 3 5  # 5는 밀려남, 5와 3 위치 swap

1 2 4 5 3  # 밀려날 수 없음, 5와 4 위치 swap

1 2 5 3 4  # swap 후 5 4 3 에서 [4, 3] sort 하면 5 3 4

이런식으로 변경됨

 

[소스코드]

n = int(input())
m = list(map(int, input().split()))
find = False
for i in range(n-1, 0, -1):
    if m[i-1] < m[i]:  # 뒷 값이 앞 값보다 크다면
        for j in range(n-1, 0, -1):
            if m[i-1] < m[j]:
                m[i-1], m[j] = m[j], m[i-1]  # 간단한 스왑
                m = m[:i] + sorted(m[i:])  # 이 부분 떄문에 헤맴
                find = True
                break
    if find:
        print(*m)  # 리스트 앞에 *를 붙이면 안에 있는 숫자들을 1 2 3 4 이런 식으로 출력할 수 있음
        break
if not find:
    print(-1)