[BOJ][Python]15663번 풀이

https://www.acmicpc.net/problem/15663

15663번: N과 M (9)

import sys
ssr = sys.stdin.readline

def sol():
    if len(ans) == m:
        print(*ans)
        return
    last = 0
    for i in range(n):
        if visited[i] == 0 and last != num[i]:
            visited[i] = 1
            ans.append(num[i])
            last = num[i]
            sol()
            ans.pop()
            visited[i] = 0

n,m = map(int, ssr().split())
num = sorted(list(map(int, ssr().split())))
visited = [0 for _ in range(n)]
ans = []
sol()

저는 도저히 해당 문제를 풀어낼 방법을 찾지 못해서 결국 풀이를 찾아봤습니다. 보고나면 이렇게 간단한데 왜 그 때는 생각이 안나는지...

 

문제의 접근은 백트래킹입니다. 큰 틀은 다른 N과 M 문제들과 동일한데 근본적인 차이가 있다면 바로 중복되는 수열은 출력하면 안되는 조건이 있다는 것입니다. 저는 처음에는 수열을 출력하기 전에 이 때 까지 나왔던 답을 모아놓은 거랑 비교를 하는 방식으로 코드를 작성했습니다. 보통 이렇게 1차원적인 풀이는 통과하지 못하기 마련이고 예상한대로 시간초과로 틀렸습니다. 그 다음에는 해당 숫자가 사용되었던 인덱스를 저장해서 같은 숫자가 같은 인덱스로 들어오려고 하면 넘기는 방식으로 짜봤는데 중복되는 숫자가 가장 큰 숫자일 경우(num의 마지막 원소일 경우), 다음 작업은 pop을 하고 새로운 숫자를 이용해야 하는데 pop을 한 다음에 그 이전의 인덱스로 변경할 방법이 없었습니다. 글로 쓰니 짧지만 하루 종일 틈만 나면 어떻게 풀지 고민하고 있었습니다. 차라리 아예 생각이라도 안났더라면 빨리 풀이를 찾아봤을텐데 뭔가 될 것 같은데 조금씩 엇나가는 것 같아서 너무 오래 잡고 있었네요.

 

해당 문제를 푸는 방법은 수열의 중복을 확인할 때 맨 뒤 숫자만 확인하는 방법입니다. 처음에는 이게 되나 싶었는데 어차피 중복된 숫자가 있더라도 중복되는 수열이라면 출력을 할 수 없으니 상관없겠더라구요. 그래서 숫자를 추가하기 전, 이미 수열에 들어가있는 숫자들 중 마지막 숫자를 저장하는 변수를 하나 선언하고 해당 변수와 이제 추가할 숫자를 비교해서 같다면 넘어가는 방법입니다. 왜 해당 방법이 가능한지 잠깐 살펴볼게요. 주어진 예시 2를 사용해보겠습니다. 편의상 1 7을 출력한 다음부터 진행하는 것으로 할게요.

 

1 7을 출력했다면 ans에서 7을 pop합니다. 방문도 안했던 것으로 바꾸고요. for 반복으로 인해서 i 는 2가 됩니다. 당연히 방문한 적이 없고 last = 7이고 num[2] = 9이니 조건도 만족하죠. 9를 ans에 추가하고 last는 9가 됩니다. sol을 재귀호출하겠죠. 1 9 를 출력하고 다시 돌아와서 9를 pop하고 방문도 0으로 바꿉니다. 그리고 아직 남은 9가 있으니 for 반복문을 실행하게 되는데 last가 9이므로 더이상 조건문이 실행되지 않고 종료되는 것입니다. 이게 9가 중복이 아니라 7이나 1이 중복이었어도 동일합니다. 1 1, 1 7, 1 9가 나온 후에 7 1이 되면 어차피 last = 1이므로 7 1은 한 번만 나오겠죠. 3개를 뽑는 경우라면 어떨까요.

4 3

1 1 7 9

라는 입력이 주어졌다면 1 1 7, 1 1 9, 1 7 1, 1 7 9, 1 9 1, 1 9 7, 7 1 1, 7 1 9 하고 반복문으로 다시 1이 추가될 차례가 되면 바로 9로 넘어가겠죠.

 

코드가 직관적으로 이해가 안되신다면 예시 입력을 하나씩 넣어보면서 디버깅을 해보시면 어떻게 돌아가는지 감이 잡히실 겁니다.

 

참고로 이건 저도 처음 써봤는데 상당히 간편하고 좋네요. N과 M 모든 문제를 이걸로 풀 수 있을 것 같아요.

from itertools import permutations
import sys
ssr = sys.stdin.readline

n,m = map(int, ssr().split())
num = sorted(list(map(int, ssr().split())))
ans = list(set(permutations(num, m)))
ans.sort()
for i in ans:
    print(*i)

itertools 자체는 몇 번 들어봐서 알고 있었는데 써볼 기회도 없고 해서 잊은 채로 지냈는데 이런 편리한 기능이 있었네요.