본문 바로가기
백준 알고리즘(BOJ)

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

by Think_why 2019. 10. 15.

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

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

 

15650번: N과 M (2)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

www.acmicpc.net

 

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

 

728x90

댓글