풀이_10972.md

#🐢 백준 10972 - 다음 수열

• Date : 2021.08.01(일)
• Time : 20분

문제

• 1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오. 사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다. N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

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

코드 풀이

        if i == len(num_list)-1 :
            num_list[i],num_list[j] = num_list[j],num_list[i]
            break

: 먼저 인접한 두 숫자를 본 다음에 뒤의 숫자가 더 크다면 단순히 바꿔주는 걸로 다음 순열을 완성할 수 있다.

        else :
            re_list = num_list[j:]
            print(re_list)
            num_list = num_list[:j]
            print(num_list)
            i = 0
            j = len(re_list)-1
            while re_list[i] >= re_list[j]:
                j -= 1
            re_list[i], re_list[j] = re_list[j], re_list[i]
            h = 1
            t = len(re_list)-1
            while h<t:
                re_list[h],re_list[t] = re_list[t],re_list[h]
                t -= 1
                h += 1
            num_list = num_list + re_list
            break

: 그렇지 않은 경우에는 먼저 j를 기준으로 리스트를 쪼개준다. 그리고 뒤쪽 리스트에서 값의 위치를 변경할 수 있다면 변경해준다. 그리고 다시 합쳐준다~ 처음에는 itertools로 구현을 했었는데, 간단하지만 메모리 초과가 나서 직접 구현으로 풀어야했다.