백준_10972 (다음 순열_실버3_itertools 사용 x_다시)

itertools 사용 x

• 링크 : https://www.acmicpc.net/problem/10972
  
  

1차 풀어본 - 메모리 초과일 것 같음

• itertools로 모든 경우의 수 다 구해서 하는 방법인데
• 보나마나 메모리 초과일 거라 테스팅은 안함

from itertools import permutations

n = int(input())
arr = list(map(int, input().split()))
ans = [i for i in arr]  # 정렬 후 같이 저장되어버려서 이렇게함

memory = []

arr.sort()

for i in permutations(arr):
    memory.append(i)

leng = len(memory)

for i in range(leng):
    if memory[i] == memory[-1]:
        print(-1)
    elif ans == list(memory[i]):
        print(" ".join(map(str,memory[i+1])))
        break            

---

2차 풀어본 - 시간 초과

from itertools import permutations
import sys

n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

ans = [i for i in arr]  # 정렬 후 같이 저장되어버려서 이렇게함
ans_reverse = [i for i in arr]  # 정렬 후 같이 저장되어버려서 이렇게함

arr.sort()  # 테케 2번같은 입력을 permutations하면 결과가 안나와서 정렬해줌
ans_reverse.sort(reverse = True)

flag = False

for i in permutations(arr):
    if flag == True:
        print(" ".join(map(str,i)))
        break
        
    if list(i) == ans_reverse:
        print(-1)
    elif list(i) == ans:
        flag = True

---

결국 라이브러리 쓰지 말고,

현재 순열의 다음 순열 딱 하나 찾는 방식으로 설계해야하는 듯

---

솔루션 코드

• https://ji-gwang.tistory.com/262
• https://velog.io/@wlrhkd49/백준-10972-다음-순열-Python

C++에서 next_permutation을 사용하면 쉽게 풀 수 있지만, python에선 이를 직접 구현해야된다고 함

결국 규칙을 찾아야 풀 수 있는 문제인데

---[1 4 3 2]를 예로 들어보자---

1. 뒤에서부터 순열을 비교하며, 뒷 값이 앞 값보다 큰 경우를 찾기만 한다.

   1. 이때 뒷 값 인덱스 = i = y (= 1의 인덱스)
   2. 앞 값 인덱스 = i - 1 = x (= 4의 인덱스)
   • 1, 4, 3, 2

2. 찾으면 다시 뒤에서부터 x보다 큰 값을 찾아 swap한다

   1. 여기서 x보다 큰 값은 2이고, x랑(=arr[i-1]이랑) swap한다
   • 2, 4, 3, 1

3. y부터 끝까지 내용물을 sorting한 다음 x 뒤에 concat한다

   1. sorted(arr[i:])
   2. arr[:i] + sorted(arr[i:]) ~> arr완성
   • 2, 1, 3, 4
   3. 출력 후 exit()

4. if문에서 다 걸러졌기 때문에 경우가 없으면 print(-1)

# https://velog.io/@wlrhkd49/백준-10972-다음-순열-Python
# https://ji-gwang.tistory.com/262
n = int(input())
arr = list(map(int, input().split()))
#arr = [1,4,3,2]

for i in range(n-1, 0, -1):   # 끝에서부터 앞 값이랑 비교하기 위해 idx=1까지 반복
    if arr[i-1] < arr[i]:
        for j in range(n-1, -1, -1):
            if arr[i-1] < arr[j]:
                arr[i-1], arr[j] = arr[j], arr[i-1]
                ans = arr[:i] + sorted(arr[i:])
                print(" ".join(map(str,ans)))
                exit()
print(-1)