[백준] 10972 다음 순열

iamjinseo·2022년 7월 11일

백준 완전탐색

문제풀이-Python

목록 보기

23/134

문제

입출력

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.

입출력예시

해설

해설 1

코드

import sys
# 숫자 개수 입력
N = sys.stdin.readline()

# 순열 입력
A = list(map(int, sys.stdin.readline().split()))

# 다음 순열 찾기
    # 단계 1 : A[i-1]<A[i]를 만족하는 가장 큰 i 찾기
max = 1
for i in range(1, len(A)):
    # 오른쪽 값이 큰 것 중 가장 뒤에 있는 한 쌍 고르기
    if A[i] > A[i-1] :
        max = i
# print("max", max)

# 단계 2 : j>=i 이면서 A[j]>A[j-1]를 만족하는 가장 큰 j를 찾는다
bigger = max
for j in range(max+1, len(A)):
    # 왼쪽 값보다 크면서 가장 오른쪽에 있는 값 찾기
    if A[j] > A[max-1]:
        bigger = j
# print("bigger", bigger)

# 단계3 : A[i-1]과 A[j]를 swap한다.
A[max-1], A[bigger] = A[bigger], A[max-1]

#A[i]부터 순열 뒤집기 (오름차순 정렬)
A[max:] = A[len(A):max-1:-1]

# 출력
ans = ""
for num in A:
    ans += str(num)+" "
print(ans)

이건 출력 초과 오류 나서 맞지는 않음. 해설 기반으로 짜보긴 했는데 망함

코드 2

다른 분의 코드를 구글링으로 가져옴

N = int(input())
input_array = list(map(int, input().split()))

for i in range(N - 1, 0, -1):  # 마지막 항부터 돈다
    if input_array[i - 1] < input_array[i]:  # 만약 앞 열의 값이 그 뒷열의 값보다 작다면
        for j in range(N - 1, 0, -1):  # 다시 그 앞 열의 값을 맨 뒷열부터 비교
            if input_array[i - 1] < input_array[j]:  # 그 앞열의 값이 뒤에 있는 어느 열보다 작다면
                input_array[i - 1], input_array[j] = input_array[j], input_array[i - 1]  # 그 두 값을 스왑
                input_array = input_array[:i] + sorted(input_array[i:])  # i-1 번째 까지의 리스트와 그 뒤에리스트를 정렬한 채로 붙인다.
                print(*input_array)  # *를 이용해 리스트 내부의 원소들을 공백을 사용하여 출력
                exit()  # 코드 종료

print(-1)  # 만약 위에서 코드 종료가 일어나지 않았다면(마지막 항이라면) -1 출력