-
15663. [Python]N과 M(9)Python_알고리즘/Silver II 2023. 10. 3. 16:31
1. 문제
https://www.acmicpc.net/problem/15663
15663번: N과 M (9)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
2. 접근 방법
- 시간 제한: 1초
- 메모리 제한: 512MB
- 백트래킹
3. 파이썬 코드
# 중복된 수 제거한 순열 생성 def N_and_M(num): # ans 리스트 길이가 M 과 같으면 if len(ans) == M: # set 에 tuple 형태로 저장 answer.add(tuple(ans)) return else: # 그 외의 경우 for i in range(N): # i 값이 num으로 들어온 index 값과 다를 경우 if i != num: # num_list[i] 값이 카운트 갯수가 0개가 아닌 경우 if num_dict[num_list[i]] > 0: # num_dict 에서 num_list[i] 의 갯수를 -1 해줌 num_dict[num_list[i]] -= 1 # ans 에 값 저장 ans.append(num_list[i]) # 재귀 실행 N_and_M(i) # 조건 탈출시 ans 값 뽑아옴 ans.pop() # num_dict 의 value 값 다시 1 증가 num_dict[num_list[i]] += 1 N, M = map(int,input().split()) num_list = list((map(int,input().split()))) # 리스트 정렬 num_list.sort() # 리스트 갯수가 몇개인지 체크할 딕셔너리 num_dict = {} for i in num_list: if i not in num_dict: num_dict[i] = 1 else: num_dict[i] += 1 # 값을 임시 저장할 리스트 ans = [] # 정답을 출력할 set answer = set() # 초기 값 -1로 실행 N_and_M(-1) # set을 list로 다시 변환 answer = list(answer) # 정렬 후 출력 answer.sort() for i in answer: print(*i)
4. 문제를 풀고난 후 생각
- ans 라는 리스트를 생성하여 재귀와 백트래킹을 진행하며 값을 저장한 것을 answer이라는 set에 추가해주는 문제였다.
- 중복된 수의 경우 중복된 리스트가 나오기 때문에 set 으로 중복제거를 진행해 주었고, num_list 에서 중복된 숫자들의 갯수를 별도로 체크해줘 재귀와 백트래킹을 진행하며 카운트 갯수를 더해주고 뺴고 리스트를 넣고 뽑고를 반복하며 리스트를 생성했다.
기존의 N과 M 문제들과는 약간 형식이 달라서 고민을 좀 많이 했던 문제였고, set을 사용하는게 맞는지 의문이 들었지만 문제를 풀며 set 과 숫자의 개수를 체크해주는 별도의 딕셔너리 혹은 리스트가 필요할 것 같아서 추가해서 사용했다.
5. 문제를 푸는데 도움이 되는 지식
- 백트래킹
'Python_알고리즘 > Silver II' 카테고리의 다른 글
1706. [Python]크로스 워드 (0) 2024.01.14 1138. [Python]한 줄로 서기 (1) 2023.12.05 17086. [Python]아기 상어2 (0) 2023.09.26 18870. [Python]좌표 압축 (0) 2023.09.04 2644. [Python]촌수계산 (0) 2023.09.04