N과 M (11)
https://www.acmicpc.net/problem/15665
문제
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
N개의 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
4 4 2
예제 출력 1
2
4
예제 입력 2
4 2
9 7 9 1
예제 출력 2
1 1
1 7
1 9
7 1
7 7
7 9
9 1
9 7
9 9
예제 입력 3
4 4
1 1 2 2
예제 출력 3
1 1 1 1
1 1 1 2
1 1 2 1
1 1 2 2
1 2 1 1
1 2 1 2
1 2 2 1
1 2 2 2
2 1 1 1
2 1 1 2
2 1 2 1
2 1 2 2
2 2 1 1
2 2 1 2
2 2 2 1
2 2 2 2
풀이
문제의 핵심은 같은 인덱스의 같은 숫자가 나와도 되지만, 다른 인덱스의 같은 숫자는 또 나오면 안된다.
ex) n = 3, m = 2, arr=[7, 9, 9]
7(idx=0) 7(idx=0) => 같은 인덱스, 같은 숫자 OK
7(idx=0) 9(idx=1)
9(idx=1) 7(idx=0)
9(idx=1) 9(idx=2) => 다른 인덱스, 같은 숫자 NOPE
두 가지 방법으로 풀었다.
checked 리스트 유무 밖에 차이가 없다.
1번 방법
1. default 값이 0인 checked 리스트를 만들어서 수열에 나올 때 증가시키면서 m번 나올 수 있도록 함.
2. temp 변수로 다른 인덱스, 같은 숫자인지 확인
2번 방법
1. temp 변수로 다른 인덱스, 같은 숫자인지 확인
1번 방법으로 처음에 풀고 난 후에 '어차피 파라미터로 몇 번째 수열에 넣어야하는지 넘겨주고
for문으로는 인덱스 0부터 n-1까지 반복하는데 굳이 방문했는지 확인하는 리스트가 필요할까' 라는 생각이 들어서
2번 방법으로도 풀었다.(결론 : 필요없었음)
코드
# 1번 방법 336ms
import sys
input = sys.stdin.readline
def tracking(k):
if k == m:
for i in range(m):
print(answer[i], end = ' ')
print()
return
temp = 0
for i in range(n):
if checked[i] < m and temp != arr[i]:
checked[i] += 1
answer[k] = arr[i]
temp = arr[i]
tracking(k+1)
checked[i] -= 1
n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
answer = [-1]*n
checked = [0]*n
tracking(0)##################################################################################################
# 2번 방법 328ms
import sys
input = sys.stdin.readline
def tracking(k):
if k == m:
for i in range(m):
print(answer[i], end = ' ')
print()
return
temp = 0
for i in range(n):
if temp != arr[i]:
answer[k] = arr[i]
temp = arr[i]
tracking(k+1)
n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
answer = [-1]*n
tracking(0)
그렇게 큰 차이는 없지만 당연히 checked 리스트를 안 쓴 2번 방법이 더 빠르다.
