[백준] 10972번(다음 순열)

백준 10972번

처음 작성한 코드

def solution(arr, n):
  for i in range(n-1, 0, -1):
    for j in range(i-1, 0, -1):
      if arr[j] < arr[i]:
        sorted_arr = array[j:i] + arr[i+1:]
        result = arr[:j] + [arr[i]] + sorted(sorted_arr)
        print(*result)
        return
        
  print(-1)
  return
  
n = int(input())
array = list(map(int, input().split()))
comp = [i for i in range(n, 0, -1)]

solution(array, n)

◼ 뒤에서부터 가장 먼저 나타나는 오름차순 정렬 부분을 찾는 부분을 빼먹음

최종 제출 코드

def solution(arr, n):
  for i in range(n-1, 0, -1):
    if arr[i-1] < arr[i]:
      for j in range(n-1, -1, -1):
        if arr[i-1] < arr[j]:
          sorted_arr = array[i-1:j] + arr[j+1:]
          result = arr[:i-1] + [arr[j]] + sorted(sorted_arr)
          print(*result)
          return
        
  print(-1)
  return
  
n = int(input())
array = list(map(int, input().split()))
comp = [i for i in range(n, 0, -1)]

solution(array, n)

◼ 바로 앞뒤의 원소가 내림차순이 아닌 부분을 찾는다

• 가장 뒤에 있는 원소부터 바로 앞의 원소와 비교하며 오름차순으로 정렬되어 있는 부분을 찾는다
• 그 부분을 [x, y]라고 할 때, 다시 배열의 가장 마지막으로 가서 x보다 큰 값을 찾는다. (이 값은 z라고 한다.)
• x와 z의 자리를 바꾸고, z+1부터 배열의 맨끝까지 오름차순으로 정렬한다