N과 M -(9) [문제번호 : 15663] (Python 파이썬 풀이)

문제 [15663]

문제 설명

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

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

입력

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

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

출력

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

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

• 예제 입력 1
  3 1
  4 4 2

• 예제 출력 1
  2
  4

• 예제 입력 2
  4 2
  9 7 9 1

• 예제 출력 2
  1 7
  1 9
  7 1
  7 9
  9 1
  9 7
  9 9

• 예제 입력 3
  4 4
  1 1 1 1

• 예제 출력 3
  1 1 1 1

문제 해석

이번 문제는 주어지는 N개의 숫자들 중에서 중복되는 숫자가 있어서 출력값이 중복되지 않도록 해야 하는 문제이다. 예를 들어 예제 2는 입력이 4 2 / 9 7 9 1 이므로 이전과 같이 List = [1, 7, 9, 9] 가 될테지만 출력값으로 1 7 // 19 // 19 // 7 1 //... 가 아닌 17 // 19 // 7 1 //... 로 중복되는 값은 제외시켜야 한다.

일단 초기값을 설정해 주자. 초기값은 이전과 동일하게 시작한다.

1 2 3 4

N , M = map(int,input().split()) List = sorted(list(map(int,input().split()))) use_check = [True]*N Answer = [] Colored by Color Scripter

cs

(초기값들의 설명은 N과 M -1에서 설명해주고 있다. https://codingabc.tistory.com/2)

이제는 중복을 어떻게 없앨지를 고민해보자.

첫번째 풀이

초기에 고안한 방법은 새로운 리스트를 생성하여 출력을 하기 전에 새로운 리스트에 값을 추가시키고, 다음부터는 리스트에 출력하기 전에 중복되어 있는지 확인을 하는 방식으로 짜 보았다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Basket = []   def bubun(idx):     if idx == M:         if not Answer in Basket:             Basket.append(Answer)             print(*Answer)                  else:         for i in range(N):             if use_check[i]:                 use_check[i] = False                 Answer.append(List[i])                 bubun(idx+1)                 Answer.pop()                 use_check[i] = True bubun(0)

cs

그래서 이와같이 코딩을 하였다. 하지만 디버깅을 해보면 Basket에 한 번 넣고난 이후 분명 Answer을 pop을 시켰는데 Basket안의 값도 같이 pop이 되는 것을 확인할 수 있었다. 그래서 생각해낸 방법이 얕은 복사이다.

그래서 이와같이 코딩을 하였다. 바뀐 점이라고는 idx값이 M이 될 때 바로 Answer값을 print하는 것이 아니라 Basket이라는 새로운 리스트에 Answer이 중복되는지 확인 한 후, 출력하도록 만들었다. 아쉽게도 디버깅을 해보면 Basket에 한 번 넣고난 이후 Answer을 pop을 시켰는데 Basket의 값도 같이 pop이 되는 것을 확인할 수 있었다. Basket 안의 값과 Answer의 값이 같은 메모리 공간을 참조하고 있어서 다른 방법을 사용해야 한다.

두번째 풀이 [ 시간 초과 ]

그래서 생각해낸 방법이 얕은 복사이다. 얕은 복사는 참조는 같으나 객체가 달라서  idx값이 M이 되었을 때, Answer을 imt라는 리스트로 얕은 복사를 한 후, Basket에 담도록 만들었다. (아래 else구문은 동일)

1 2 3 4 5 6 7

def bubun(idx):     if idx == M:         immi = Answer[:]         if not immi in Basket:             Basket.append(immi)             print(*Answer)

cs

설명 그대로 idx값이 M일때 얕은 복사로 Answer을 immi로 얕은 복사 후 사용하였기 때문에 print 이후에 Answer을 pop시켜도 Basket 안에는 immi라는 짝퉁 리스트를 사용하고 있기 때문에 변함이 없다. 이제 출력값을 확인해 보자. 그러면 우리가 원했던 예시에 나오는 출력값이 나오는 것을 확인할 수 있다. 원리는 간단하다. Basket에 리스트를 담고, 만약 리스트가 중복된다면 출력에서 제외시키는 것이다. 하지만 백준에 이대로 코드를 제출한다면 시간초과가 뜰 것이다. 우리는 이보다 더 간략한 방법으로 풀어야 하다. 얕은 복사를 시도해 봤으니 깊은 복사를 시도해 본다면 오히려 시간이 더 오래 걸린다는 것을 알 수 있다. 그러면 접근 방법을 다른 식으로 해봐야 겠다.

세번째 풀이 [ 시간 초과 해결 ]

세번째로 고안한 방법이 만약 같은 자릿수에 이전에 사용한 숫자가 있다면 제외하는 방법은 어떨까 라고 생각하여 만들어낸 코드이다. 다시 예제 2를 예시로 한다면, 표현하기 쉽게 List = [1, 7, 9(1), 9(2)] 라고 하자. 1 7과 1 9(1)를 출 력한 뒤 마지막으로 append시킨 값이 9(1)이고 for 구문 안에서 i는 다음 번의 9(2)를 확인할 것이다. 그러므로 append 시킨값과 다음번 인덱스에 해당하는 숫자가 같으면 출력을 하지 않도록 하는 것이다. 그래서 이번에는 Basket을 없애고, 이전에 append시킨값을 last라고 지칭하였으며, last는 함수 안에서 초기화가 되게 만들었다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

def bubun(idx):     if idx == M:         print(*Answer)         return          else:         last = 0         for i in range(N):             if use_check[i] and last != List[i]:                 use_check[i] = False                 Answer.append(List[i])                 last = List[i]                 bubun(idx+1)                 Answer.pop(-1)                 use_check[i] = True

cs

idx값이 M이 아닐 때, last는 append시킨 값이고, append 이후 last값과 다음 List[i]값이 다를 때 if 구문을 돌게 만들었다. 그래서 결과를 확인해보면 원하는 출력값을 확인할 수 있으며 다른 예제도 마찬가지로 원하는 결과를 확인 할 수 있다. 끝으로 코드롤 공개하여 이번 포스팅을 마친다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

N , M = map(int,input().split()) List = sorted(list(map(int,input().split()))) use_check = [True]*N Answer = []   def bubun(idx):     if idx == M:         print(*Answer)         return          else:         last = 0         for i in range(N):             if use_check[i] and last != List[i]:                 use_check[i] = False                 Answer.append(List[i])                 last = List[i]                 bubun(idx+1)                 Answer.pop()                 use_check[i] = True   bubun(0) Colored by Color Scripter

cs

출처

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

[

15663번: N과 M (9)

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

www.acmicpc.net

](https://www.acmicpc.net/problem/15663)