다음수열, 이전수열

#10972번 다음 수열 https://www.acmicpc.net/problem/10972

10972번: 다음 순열

 

다음 수열을 구하는 문제이다.

이 전까지는 수열을 구할 때 재귀함수를 활용해 구했다.

내가 알고있던 파이썬으로 수열을 구현하는 방법은 두 가지 였다.

 

1. itertools 라이브러리 사용하기

 : 수열과 조합을 위한 라이브러리이다.

 

2. 재귀함수 사용하기

 : 그래프 탐색 이론에 기반한(?) 형태라고 할 수 있다.

 

위 두 가지 방법으로는 도저히 해답이 떠오르지 않았다.

 

그래서 또 검색... (검색 안하는 날이 올까?)

 

Next_permutation.py

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

x = 0
for i in range(N-1, 0, -1):
    if target[i-1] < target[i]:
        x = i-1
        break

for i in range(N-1, 0, -1):
    if target[x] < target[i]:
        target[x], target[i] = target[i], target[x]
        target = target[:x+1] + sorted(target[x+1:])
        print(*target)
        exit()
print(-1)

위 코드는 인덱스 교체 (swap)를 통해 수열을 구현하는 코드에 기반한다.

 

첫 번째 for문에서는 Focus를 둘 index를 찾는다. 

그 뒤 두 번째 for문에서는 focus보다 큰 수를 찾았을 때 그 두 수의 위치를 바꾼다.

그 뒤, focus index 뒤에 있는 나머지 수 들을 정렬하면

입력 수열의 다음수열이 나오게 된다.

 

예를 들어보자. 입력 : 1 4 3 2

뒤에서부터 탐색한다. (수열을 순차적으로 나열했을 때, 맨 오른쪽에 위치한 수 부터 바뀌기 때문에)

1) 오른쪽에 있는 수보다 작은 index를 찾는다. -> 1. index=0

2) 한번 더 루프를 돌면서 index=0보다 큰 수를 찾는다 -> 2, index=3

3) 두 수의 위치를 바꿔준다. -> 2 4 3 1

4) 그 뒤 index=0 이후의 수들을 정렬한다 -> [ 2 ] + [ 1, 3, 4 ]

5) 최종 결과 : 2, 1, 3, 4

 

+) exit()는 함수를 따로 정의하지 않았을 때 프로그램을 종료하고 싶다면 사용하기에 좋다. (이걸 왜 이제 알았을까....)

 

6) 프로그램이 종료되지 않았을 경우에 -1을 출력하도록 한다. -> 적합한 수열이 없는 경우 = 주어진 수열이 마지막 수열인 경우

 

 

대충 이해가 되나? 아주 센스넘치는 코드라고 생각한다.

 

그럼 약간의 조건 수정을 통해서 다음 문제를 해결할 수 있다.

 

#10973번 이전 수열 https://www.acmicpc.net/problem/10973

10973번: 이전 순열

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

x = 0
for i in range(N-1, 0, -1):
    if target[i-1] > target[i]:
        x = i-1
        break

for i in range(N-1, 0, -1):
    if target[x] > target[i]:
        target[x], target[i] = target[i], target[x]
        target = target[:x+1] + sorted(target[x+1:], reverse=True)
        print(*target)
        exit()
print(-1)

원리는 다음수열과 같다. 다만 몇가지 조건을 바꿔줘야한다.

1) if문이 가지고 있던 조건을 전부 반대로 바꿔준다.

2) 리스트 정렬시 조건을 역정렬한다

 

예를 들어보자. 입력 : 1 4 2 3

1) 오른쪽에 있는 수보다 왼쪽에 있는 수가 더 큰 경우를 맨 오른쪽에서부터 탐색한다 : 4. index : 1

2) 찾은 수(focus)보다 작은 수가 나오는 경우, 그 수와 위치를 바꿔준다 -> 1 3 2 4

3) 그 뒤, focus 뒤에 오는 수열을 역정렬한다 -> [ 1, 3 ] + [ 4, 2 ]

4) 결과 : 1 3 4 2

재귀함수를 통해서 1,2,3,4의 수열을 출력한 결과이다.

 

1 4 2 3 이전에 1 3 4 2 가 나옴을 확인할 수 있다.