10973

날짜 : 2023. 06. 15

사용 언어 : python

 

문제

https://www.acmicpc.net/problem/10973

 

 

코드

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))  # 숫자 입력

for i in range(n-1, 0, -1):
    j = i - 1
    if a[j] > a[i]:  # 현재 수가 앞 수보다 작은 경우
        tmp = sorted(a[i:])  # 현재 수 기준으로 오름차순 정렬하는 리스트 생성
        tmp.sort(reverse=True)  # 내림차순 정렬
        # print(tmp)
        for k in range(len(tmp)):
            if a[j] > tmp[k]:  # 기준이 되는 수보다 작은 수 중에서 가장 큰 수 추출
                a[j], tmp[k] = tmp[k], a[j]  # swap
                tmp.sort(reverse=True)  # 내림차순 후 붙이기
                a[j+1:] = tmp
                print(*a)  # 출력 후 탈출(exit 없으면 TLE)
                exit()
print(-1)  # 순열 중 가장 작은 케이스(사전순으로 가장 처음에 오는 순열)

 

 

풀이

- 사전순으로 정렬할 때 본인 순열의 바로 앞자리인 케이스는 각각의 값의 증가하는 지점의 가장 마지막 부분에서의 값보다 작은 수 중 최댓값으로 놓고, 나머지 부분을 내림차순으로 정렬한 순열이라고 정의할 수 있다.

 

- 동그라미로 그린 부분(j)을 보면 가장 마지막으로 감소하는 부분이라는 것을 알 수 있다.

- 그 부분의 앞쪽의 숫자 중 동그라미 부분의 값보다 작은 수 중 가장 큰 수를 구하고, 나머지 부분을 내림차순으로 정렬해서 붙여버리면 된다.

 

 

알게된 점

- permutaion을 사용해서 풀면 n값이 최대 10000이라 무조건 TLE가 발생한다.

- 그래서 계속 다른 풀이들을 생각했고, 각각의 자리를 비교하면서 값들을 swap한 다음 출력하는 것이 포인트라는 것을 알 수 있었다.

- 근데 이게 왜 조합 카테고리에 있는지는 잘 모르겠다.

 

 

참고 사이트

-