[python]programmers - 메뉴리뉴얼

programmers Level2 2021 KAKAO BLIND RECRUITMENT 메뉴리뉴얼

 

카카오 코테에서 이 문제를 풀었던 기억이 난다. 그때 문제를 덜 이해해서 정답을 맞추지는 못했었다.

 

[입출력 예]

orders	course	result
["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"]	[2,3,4]	["AC", "ACDE", "BCFG", "CDE"]
["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"]	[2,3,5]	["ACD", "AD", "ADE", "CD", "XYZ"]
["XYZ", "XWY", "WXA"]	[2,3,4]	["WX", "XY"]

이전 코테에서 문제를 풀때 두번째 예시의 정답에 왜 'AB'가 안들어 가는지 이해가 안됐었다.

분명 'ABCDE', 'AB' 두개의 orders에 'AB' 존재하므로 result에 들어가야 하는 것 아닌가..?

=> course = 2일 때, 가장 많이 나온 단품메뉴의 조합을 찾는 것이다

'AB'는 orders에서 'ABCDE', 'AB' 에 존재하므로 2번

'AD'와 'CD'는 orders에서 3번 나온다

따라서 course = 2일 때의 정답은 'AD', 'CD' 인 것이다

 

아마 문제의 "가장 많이 함께 주문된 단품메뉴 조합에 따라 "스카피"가 만들게 될 코스" 이부분이 위의 내용을 뜻하는 부분인 것 같다.

 

소스코드 1 - 처음에 내가 작성한 코드

# 메뉴리뉴얼

from itertools import combinations

# 만들고자 하는 course의 menu수로 조합을 만든다
def makeCourse(menu, n) :
    l = len(menu)
    result = []
    for i in range(l) :
        result += list(combinations(tuple(sorted(menu[i])), n))
    return result

# 해당 조합이 order에 2개 이상 존재하는지 count한다
def countMenu(menu) :
    o = list(set(menu))
    result = []
    l = len(o)
    for i in range(l) :
        if(menu.count(o[i]) == 1) :
            continue
        result.append((o[i], menu.count(o[i])))
    
    return sorted(result, key= lambda x : x[1], reverse=True)

# 2개 이상 존재하는 조합 중 가장 많이 나온 메뉴조합을 고른다
def findMax(menu) :
    result = []
    m = menu[0][1]
    for i in menu : 
        if(i[1] == m) :
            result.append(''.join(i[0]))
        elif(i[1] < m) :
            break
    return result

def solution(orders, course):
    answer = []
    for i in course :
        course_comb = makeCourse(orders[:], i)
        if(len(course_comb) <= 1) : # 조합을 구했는데 1개 : 최소 2개는 있어야 메뉴로 선정하므로 넘어간다
            continue
        
        count_result = countMenu(course_comb)
        if(len(count_result) == 0) : # 만약 조합의 count가 1이 넘지 않으면
            continue
        answer += findMax(count_result)
    
    return sorted(answer)

1. course 수에 해당하는 조합들을 만든다 (def makeCourse)

• 예를 들어 1번 testcase에서 course = 2일 때 'AC'를 구해야 한다
• 단품메뉴 2개이상으로 만들어진 'ABCFG', 'CDE' 등을 2개의 단품메뉴 조합으로 만든다
• ex) 'ABCFG' -> 'AB', 'AC', 'AF', 'AG', 'BC', 'BF', 'BG', 'CF', 'CG', 'FG'
• 이때 문제조건에서 알파벳 오름차순으로 정렬해야 하므로 각 조합에서 메뉴를 오름차순으로 sort한다
  • 이걸 꼭 해줘야 하는게 3번 testcase에서 XWY로 2개 조합을 만들면 => 'XW', 'XY', 'WY' 가 나오고, WXA에서 2개의 조합을 만들면 => 'WX', 'WA', 'XA' 가 나오기 때문에 'XW' 와 'WX'가 다른 문자열로 되서 나중에 카운트할때 각각 1개로 나온다 (사실 'WX' 2개로 count되어야 함)
• 함수에 넣어줄때 orders를 그대로 넣지 않고 orders[:] 를 넣어주었다 (orders list shallow copy)
  • 그냥 orders를 넣어주면 원본 orders가 함수에서 구하는 조합으로 변경된다
  • 밑에 참고 사이트를 첨부했음!

 

2. orders 전체로 만든 2개의 단품메뉴 조합들에서 각 조합들이 몇번 나오는지 count한다 (def countMenu)

• ex) 'AC'는 총 4번 나온다 ('ABCFG'에서 만든 조합에서 1번, 'AC'에서 1번, 'ACDE'로 만든 조합에서 1번, 'ACDEH'로 만든 조합에서 1번)

3. count한 것 중에 최대를 찾는다 (이때 count는 2이상이어야 하고, 만약 max인것이 여러개면 해당하는 것 모두를 찾는다) (def findMax)

 

4. 최대를 찾은 후 sort해서 반환한다 (문제 조건)

 

소스코드2 - 다른사람 풀이(Counter 사용)

# 메뉴리뉴얼 - 다른사람 풀이 (counter 사용)

import collections
import itertools

def solution(orders, course):
    result = []

    for course_size in course:
        order_combinations = []
        for order in orders:
            order_combinations += itertools.combinations(sorted(order), course_size)
        print('order_combination : ', order_combinations)

        most_ordered = collections.Counter(order_combinations).most_common()
        print('Counter(order_combinations) : ', collections.Counter(order_combinations)) # ('A', 'C') : 4 이렇게 dict형태로
        print('most_ordered : ', most_ordered) # (('A', 'C'), 4) tuple로 묶어줌
        result += [ k for k, v in most_ordered if v > 1 and v == most_ordered[0][1]] # count수가 제일큰게 1일수도 있으니까 v > 1도 넣어준다

    return [ ''.join(v) for v in sorted(result) ]

로직은 같았다. 다만 countMenu를 내가 직접 함수로 구현했다면, 이분은 collections에서 Counter를 사용하여 손쉽게 구했다. 또한 count가 2개이상인 것을 찾는걸 나는 함수로 만들어 구현했다면 이분은 한줄로 깔끔하게 구했다

 

소스코드3 - 내 풀이에 Counter 적용

# 메뉴리뉴얼 - 내 풀이에 counter 적용시켜보기

from itertools import combinations
from collections import Counter

# 만들고자 하는 course의 menu수로 조합을 만든다
def makeCourse(menu, n) :
    l = len(menu)
    result = []
    for i in range(l) :
        result += list(combinations(tuple(sorted(menu[i])), n))
    return result

def solution(orders, course):
    answer = []
    for i in course :
        course_comb = makeCourse(orders[:], i)
        if(len(course_comb) <= 1) : # 조합을 구했는데 1개 : 최소 2개는 있어야 메뉴로 선정하므로 넘어간다
            continue

        most_ordered = Counter(course_comb).most_common()
        answer += [''.join(k) for k, v in most_ordered if v > 1 and v == most_ordered[0][1]]

    return sorted(answer)

makeCourse는 그대로 함수로 두었고 Counter를 사용해보았다

 

 

 

• Counter 사용법

[파이썬] collections 모듈의 Counter 클래스 사용법

 

• list를 함수의 인자로 넣을 때 주의해야 하는 사항
  • 참고 사이트1
  • 참고 사이트2

파이썬에서 리스트를 함수 인자로 받는 경우 - 전역 변수의 문제

파이썬 함수 인자 전달시 변경되는 객체 – 리스트 등