다음 순열

💡 문제 해결 아이디어

• 내가 생각한 아이디어
  • 순열의 맨 뒤에서부터, 숫자가 증가하지 않는 순간을 찾는다. (for)
  • 숫자가 증가하지 않는다는 것은, 그보다 앞의 숫자를 건드리지 않고도, 사전순으로 더 높은 순열을 만들 수 있다는 뜻이다.
    • 그보다 앞의 숫자들은 건드리지 않는다.
    • 그리고 그 때까지의 숫자들로, 사전순으로 다음에 오는 순열을 만들어 붙인다.
      • 감소한 순간의 숫자를 key라고 할 때, 그 때까지의 숫자들 중 key의 바로 다음으로 큰 숫자를 찾아 key의 자리에 앉히고, 나머지 숫자들은 오름차순으로 정렬하여 key의 자리 뒤에 붙인다.
  • 숫자가 증가하지 않는 순간을 찾지 못하면, -1을 출력한다. (else)

💻 작성된 코드

n = int(input())
ls = list(map(int, input().split()))
key = 0
for i in range(n-1, -1, -1):
	# 숫자가 증가하지 않으면, 
    if ls[i] < key:
    	# 그 부분 이후로 전체 sort
        tmp = ls[i:]
        tmp.sort()
        # 바로 다음으로 큰 숫자를 찾아 그 자리에 앉힌다.
        index = tmp.index(ls[i])
        first = tmp.pop(index+1)
        # 건드리지 않은 앞부분 + 바로 다음으로 큰 숫자 + 오름차순 정렬된 나머지 뒷부분
        print(" ".join(list(map(str, ls[:i] + [first] + tmp))))
        break
    # 숫자가 증가하면, 비교 기준을 갱신해준다.
    key = ls[i]
# 숫자가 계속 증가하는 형태라면, 마지막 순열이기에 다음 순열이 없다.
else :
    print(-1)

이전 순열

💡 문제 해결 아이디어

• 내가 생각한 아이디어
  • 다음 순열의 정반대 알고리즘
  • 순열의 맨 뒤에서부터, 숫자가 감소하지 않는 순간을 찾는다. (for)
  • 숫자가 감소하지 않는다는 것은, 그보다 앞의 숫자를 건드리지 않고도, 사전순으로 더 낮은 순열을 만들 수 있다는 뜻이다.
    • 그보다 앞의 숫자들은 건드리지 않는다.
    • 그리고 그 때까지의 숫자들로, 사전순으로 이전에 오는 순열을 만들어 붙인다.
      • 증가한 순간의 숫자를 key라고 할 때, 그 때까지의 숫자들 중 key의 바로 다음으로 작은 숫자를 찾아 key의 자리에 앉히고, 나머지 숫자들은 내림차순으로 정렬하여 key의 자리 뒤에 붙인다.
  • 숫자가 감소하지 않는 순간을 찾지 못하면, -1을 출력한다. (else)

💻 작성된 코드

n = int(input())
ls = list(map(int, input().split()))
key = 10001
for i in range(n-1, -1, -1):
	# 숫자가 감소하지 않으면
    if ls[i] > key:
    	# 그 부분 이후로 전부 내림차순 정렬
        tmp = ls[i:]
        tmp.sort(reverse=True)
        # 바로 다음으로 작은 숫자를 찾아
        index = tmp.index(ls[i])
        first = tmp.pop(index+1)
        # 건드리지 않은 앞부분 + 바로 다음 작은 숫자 + 내림차순 정렬된 나머지
        print(" ".join(list(map(str, ls[:i] + [first] + tmp))))
        break
    # 숫자가 감소했다면, 비교대상 갱신
    key = ls[i]
# 숫자가 계속 감소하기만 했다면, 맨 첫번째 순열이기에, 이전 순열이 없다.
else :
    print(-1)