프로그래머스 메뉴리뉴얼

https://programmers.co.kr/learn/courses/30/lessons/72411

코딩테스트 연습 - 메뉴 리뉴얼

 

약간헤매기도 했고, 재미도 있었던 문제다.

잠깐 생각해보고 길은 제대로 봤는데 구현이 생각보다 좀 오래 걸린듯하다.

풀면서도 이렇게 푸는게 맞는가 싶고, 다 풀고나서도 뭔가 어거지로 푼 느낌이 강한데, 

다른 사람의 풀이보기 로 보니 코드가 좀 더 세련됐냐 안세련됐냐의 차이뿐.. 방법은 대동소이했다.

 

이 문제를 풀면서 바로 떠올린게 combinations 고 두번째로 떠올린게 Counter 였는데 Counter 사용법을 잘몰라서 

그냥 직접 dictionary 에 카운트 했다.

 

풀이는 아래와 같다.

 

1. 메뉴 구성을 위한 코스 숫자를 순회한다. (i)

2. 손님의 주문내역을 순회하면서 코스 숫자(i)의 모든 조합을 구해 dictionary 의 해당 코스 숫자(i)에 해당하는 키에 저장한다.

 

3. 코스숫자를 키로 갖고 코스숫자가 가능한 모든 조합을 값으로 가지고 있는 d 를 순회한다.

4. 각 조합이 등장한 횟수를 구한다. 

5. 각 조합이 등장한 횟수가 큰순으로 정렬한다.

 

6. 코스숫자를 순회한다.

7. 위 과정에서 구한 리스트에서 코스숫자에 해당하는 조합의 길이를 가진 항목을 list comprehension (filtering) 한다

8. 필터링 한 값에 항목이 존재하고 첫번째 값의 조합이 등장한 횟수가 1 보다 크다면 첫번째 항목을 answer 에 추가한다.

> 첫번째 값의 조합을 본 이유는 5에서 이미 조합이 등장한 횟수가 큰순으로 정렬했기 때문이다.

9. 필터링 한 값의 두번째 부터 순회하면서 이전에 추가한 등장횟수와 같다면 answer에 추가한다.

 

코드가 좀 .. 많이 너저분하다.

 

from itertools import combinations


def solution(orders, course):
    answer = []
    temp = []
    d = {}
    for i in course:
        for s in orders:
            temp.extend(list(combinations(sorted(s), i)))
        d[i] = temp

        temp = []

    cnt_d = {}
    for k, v in d.items():
        for tup in v:
            if tup in cnt_d:
                cnt_d[tup] += 1
            else:
                cnt_d[tup] = 1

    l = sorted(cnt_d.items(), key=lambda x: x[1], reverse=True)
    for i in course:
        r = [(''.join(x), c) for x, c in l if len(x) == i]
        if r and r[0][1] > 1:
            answer.append(r[0][0])
            max_cnt = r[0][1]
            for j in range(1, len(r)):
                if r[j][1] == max_cnt:
                    answer.append(r[j][0])
                else:
                    break
    answer.sort()
    return answer

 

 

다른분의 세련된풀이는 아래와 같다.

나는 Counter 와 most_common 의 존재를 잘 몰랐다.

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)

        most_ordered = collections.Counter(order_combinations).most_common()
        result += [k for k, v in most_ordered if v > 1 and v == most_ordered[0][1]]

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