15665 N과 M (11)

N과 M (11) 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	450	308	267	72.162%

문제

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

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

입력

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

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

출력

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

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

쉬운 문제인줄 알았으나 의외의 복병이 있었다.

이전 문제의 소스를 수정하여 

n,m = map(int, input().split())

answer =  sorted(list(map(int,input().split())))

temp = [""]*m

t_list = []

    

def cal_perm(deepness):

    if deepness == m:

        a = str(temp)[1:-1].replace(",","")

        if a not in t_list:

            t_list.append(a)

            print(a)

    else:

        for i in answer:

            temp[deepness] = i

            cal_perm(deepness+1)

cal_perm(0)

이 소스를 제출 했으나 시간초과가 떠서 최적화를 진행하여

n,m = map(int, input().split())

answer =  sorted((map(int,input().split())))

temp = [""]*m

t_list = []

    

def cal_perm(deepness):

    if deepness == m:

        a = str(temp)[1:-1].replace(",","")

        if a not in t_list:

            t_list.append(a)

            print(a)

    else:

        for i in answer:

            temp[deepness] = i

            cal_perm(deepness+1)

            #temp[deepness] = -1

cal_perm(0)

이 소스를 제출했으나 또 시간초과가 떠서 질문에 올리자

어떤 파이썬 고수님이 

a = str(temp)[1:-1].replace(",","")

        if a not in t_list:

            t_list.append(a)

            print(a)

저 부분이 문제라고 지적해주셨고, 나는 당연히 문자열 슬라이싱이 문제 겠구나 하고 print(*a) 문을 사용하여

문자열 슬라이싱 부분을 없앴다.

그런데도 시간초과가 뜨자 내가 중복을 제거하기 위해 만든 부분을 체크 했다.

자료가 리스트안에 존재하는지 찾는시간이 오래 걸렸다고 밖에 볼 수 없는 상황.

그렇다면 리스트안에 다 넣어버리고 중복을 없애보자는 취지로 여러가지 시도를 했고,

애초에 set자료형에 넣으면 된다는 것을 깨달았다.

그러나 set형에는 list형을 자료로 넣을 수 없으므로 str형으로 바꿔서 넣었고,

그 set형을 재 정렬하여 출력하였다.

이것도 역시 시간초과.....

이렇게 멘붕하는 도중 백준의 한 고수님이 set에 tuple형태로 넣으라고 알려주셨다.

그러자 바로 성공....

str으로 바꾸고 출력할때 다시 변환하는 과정이 오래걸린듯 싶다.

나는 당연히 list형을 자료로 못받길래 tuple형도 자료로 못 받는 줄 알았는데 충격이다...

아래는 통과한 소스 

import sys

sys.stdin = open("input.txt", "r", encoding="utf-16")

n,m = map(int, input().split())

answer = sorted((map(int,input().split())))

temp = [""]*m

memo = set()

def cal_perm(deepness):

if deepness == m:

memo.add(tuple(temp))

else:

for i in answer:

temp[deepness] = i

cal_perm(deepness+1)

cal_perm(0)

memo = sorted(memo)

for i in memo:

print( *i )

역시 풀때가 제일 짜릿해