백준 알고리즘 15650 (N과 M(2)) - python

[문제] 백준 알고리즘 15650 (N과 M(2)) - python

> https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

 

N과 M(1)에서 오름차순 출력이 추가된 문제.

그래서 N과 M(1)의 내용을 조건에 맞게 수정해서 풀었다.

 

 

1. 순열을 담은 list를 오름차순으로 정리한 후(sorted()), 문자열로 만든다.

2. 출력용 list에 그 문자열이 없다면, append한다.

3. 출력용 list를 한 줄씩 출력한다.

 

[Code]

N, M = map(int, input().split())
visited = [False] * N
out, out_all = [], []

def solve(depth, N, M):
    if depth == M:
        out_str = ' '.join(map(str, sorted(out)))
        if out_str not in out_all:
            out_all.append(out_str)
        return
    for i in range(N):
        if not visited[i]:
            visited[i] = True
            out.append(i+1)
            solve(depth+1, N, M)
            visited[i] = False
            out.pop()
solve(0, N, M)

for i in out_all:
    print(i)

 

답은 맞았지만 중간에 Sort를 사용해서 효율적이지 않고, 시간이 꽤 오래 걸렸다.

다른 사람들의 풀이 방식을 참조해보니, 더 효율적이고 간단한 방식으로 풀어놓았다.

바로, 이전의 idx 값을 넘겨주어, idx 이하는 진행하지 않는 것이다.

마치 1차원 배열 A의 모든 두 요소를 비교할 때, 아래의 방식으로 시간복잡도를 줄이는 것과 비슷하다는 느낌을 받았다.

 

for i in range(len(A)-1):

      for j in range(i+1, len(A)):

            if A[i] < A[j]:

                  ....

 

효율적인 힌트를 얻고 내 방식에 맞춰서 다시 풀어보았다. N과 M(1)에서 달라질 것은 거의 없다.

 

[Code]

N, M = map(int, input().split())
visited = [False] * N
out = []

def solve(depth, idx, N, M):
    if depth == M:
        print(' '.join(map(str, out)))
        return
    for i in range(idx, N):
        if not visited[i]:
            visited[i] = True
            out.append(i+1)
            solve(depth+1, i+1, N, M)
            visited[i] = False
            out.pop()
solve(0, 0, N, M)

 

그런데.. Python... 이것조차 itertools의 combinations로 만들어 놓았다고 한다... 리스펙...

 

[Code]

from itertools import combinations
N, M = map(int, input().split())
C = combinations(range(1, N+1), M)  # iter(tuple)
for i in C:
    print(' '.join(map(str, i)))  # tuple -> str