👇🏻 문제
https://programmers.co.kr/learn/courses/30/lessons/72411
이 문제로 정말 애를 좀 먹었다. 로직은 대충 알겠는데 막상 구현에서 쩔쩔맸다. 그 이유는 다음과 같다.
조합을 구현하는데에 무한 loop 에 빠졌다. 재귀함수 잘못 짠...
파이썬에 combinations가 있었던 걸 알았다면, 더 편하게 짰을 것 같다.
나의 로직은 다음과 같다.
1. course의 반복문을 돌며 orders의 원소들을 일일히 검사한다.
2. course보다 orders 원소의 길이가 길 때만 검사를 하며, orders 원소는 리스트 형태로 변환해 정렬을 먼저 해준다. (테스트 3번의 예외를 잡아주기 위해서)
3. course의 개수대로 orders 원소를 조합하고 comb_list가 비어있다면 그대로 배열에 삽입한다. (nCr)
4. comb_list가 비어있지 않으면 새로운 orders 원소 조합이 comb_list에 있는지 확인한 다음, 없으면 추가하고 있으면 find_comb에 추가한다.
5. find_comb에 있으면 카운트를 증가시켜주고 없으면 카운트 = 2(이미 들어있던 것 + 새로 들어온 것도 있을 경우이므로)으로 추가해준다.
6. find_comb 가 비어있지 않을 경우, 가장 큰 카운트 value 를 가지고 있는 key를 찾아 answer에 추가해준다.
7. answer을 오름차순으로 정렬해준다.
👇🏻 코드
from itertools import combinations
def solution(orders, course):
answer = []
for length in course:
comb_list=[]
find_comb={}
for order in orders:
if len(order) >= length:
order_list = list(order)
comb_list.sort()
order_list.sort()
if len(comb_list) == 0: comb_list += [list(elem) for elem in list(combinations(order_list,length))]
else:
for elem in list(combinations(order_list,length)):
if list(elem) in comb_list:
string=''
for e in list(elem):
string += str(e)
if string in find_comb: find_comb[string] += 1
else: find_comb[string] = 2
else:
comb_list.append(list(elem))
if find_comb:
max_value = max(find_comb.values())
for key in find_comb:
if max_value == find_comb[key]:
answer.append(key)
answer.sort()
return answer
orders=["XYZ", "XWY", "WXA"]
course=[2,3,4]
solution(orders,course)
'Python > 문제풀이' 카테고리의 다른 글
[➕ 오답노트] 백준 11478번 (0) | 2022.05.19 |
---|---|
[ ➕ 오답노트] 백준 17298번 오큰수 (0) | 2022.05.17 |
[ ➕ 오답노트] 프로그래머스 해시 - 베스트앨범 (0) | 2022.05.11 |
[2] 백준 13458번: 시험감독 (0) | 2022.04.27 |
[1] 백준 12100번: 2048 (Easy) (0) | 2022.04.26 |