[백준] 15656번 N과 M(9)

www.acmicpc.net/problem/15663

15663번: N과 M (9)

 

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열

 

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

 

출력

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

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

 

 

풀이

이 문제의 경우에는 
1 4 4 9 와 같은 입력이 들어왔을때, 1 4 는 1번만 나와야하지만 4 4는 나와야한다.

그래서 처음에는 결과를 리스트에 입력해서 이미 리스트에 존재하는 경우에는 추가안하는 방법으로 코드를 구성하였다.

def NandM9(index, N, M):
    if index == M:
        if temp not in answer:
            answer.append(temp[:])
        return

    for i in range(N):
        if not check[i] :
            check[i] = 1
            temp.append(N_list[i])
            NandM9(index + 1, N, M)
            temp.pop()
            check[i] = 0

 

시간 초과가 발생하였다.
그래서 다음 방법으로 정렬된 리스트를 이용하기 때문에 이 전에 나왔던 숫자를 저장해서 동일하면 넘어가는 식으로 코드를 구현했더니.

 

    if index == M:
        global temp
        if temp != answer :
            print(' '.join(map(str, answer)))
        temp = answer[:]

        return

1 2 4 4와 같은 입력에서 4에 대한 반복을 2번 돌면서 문제가 생겼다.

 

즉, 같은 반복에서는 이 전에 사용했던 숫자를 사용하면 안되지만 한 루프 안에서는 (4 , 4)가 나올 수 있게 판단해야해서
중복을 확인하는 dup라는 변수를 이용했다 한 반복 안에서는 dup가 초기화 되지는 않지만 새로운 함수를 호출했을 때는 dup를 초기화하도록 for 문 밖에 dup = 0을 선언했더니 문제가 해결되었다.

N과 M문제 중에서 가장 어려웠었다.

전체 코드

import sys

N, M = map(int, sys.stdin.readline().split())
N_list = list(map(int, sys.stdin.readline().split()))
N_list.sort()
check = [0 for _ in range(N)]
answer = []

def NandM9(index, N, M):
    if index == M:
        print(' '.join(map(str, answer)))
        return
    dup = 0
    for i in range(N):
        if not check[i] and N_list[i] != dup:
            check[i] = 1
            answer.append(N_list[i])
            dup = N_list[i]
            NandM9(index + 1, N, M)
            answer.pop()
            check[i] = 0


NandM9(0, N, M)