[문제 풀이] 메뉴 리뉴얼

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

 

해결 과정

첫 번째 시도는 문제 자체를 이해하지 못하고 풀었다. 두 번째 시도는 테스트케이스 13, 14, 15 번에서 시간초과가 떴다. orders에 대해서 무작정 모든 경우의 수를 구해서 생긴 문제인데, 이 글과 이 글을 참고해서 힌트를 얻었다. 모든 경우의 수를 구할 필요가 없지. 만약 num이 7이라면 orders 중에 7 이상인 대상에 대해서, 각각 가능한 조합을 만들고 더하는 형태로 구현했더니 해결 완료.

나의 풀이

from itertools import combinations

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

    maxLen = max([len(k) for k in orders])
    
    for num in course:  # 2, 3, 4
        if num > maxLen:
            continue

        answerList = {}
        combiList = []  # AB, BC, CA
        for element in orders:
            if len(element) >= num:
                combiList += list(set(combinations(element, num)))

        for combi in combiList:
            count = 0
            for item in orders:
                if set(combi).issubset(set(item)):
                    count += 1
            tmp = ''.join(sorted(list(combi)))
            answerList[tmp] = count

        allValues = answerList.values()
        maxValue = max(allValues)
        if maxValue > 1:
            answer += [k for k, v in answerList.items() if v == maxValue]

    answer.sort()
    return answer

 

counter를 이용한 풀이

from itertools import combinations
from collections import Counter

def solution(orders, course):
    answer = []
    sortedOrders = []
    
    for num in course: # 2, 3, 4
        # 따질 필요 없으면 건너뛰기
        if num > max([len(x) for x in orders]):
            continue
        # num 별로 가장 많이 주문한 조합 뽑는 방법
        candidates = set()
        # 일단 가능한 조합을 먼저 뽑아내야 함
        for order in orders:
            sortedOrder = sorted(list(order))
            sortedOrders.append("".join(sortedOrder))
            candidates |= set(combinations(sortedOrder, num))
        
        # 포함 여부 찾기
        counter = Counter()
        for candidate in list(candidates): # ("A", "B")
            
            for order in orders: # "ABCED"
                if len(order) >= num:
                    if set(candidate) == set(order) & set(candidate):
                        counter["".join(candidate)] += 1

        # answer에 붙이기
        maxValue = counter.most_common(1)[0][1]
        if maxValue > 1:
            answer += [k for k, v in counter.items() if v == maxValue]
        
        
    # 나중에 answer은 오름차순으로 정렬되어야 함
    return sorted(answer)

 

 

첫 번째 시도는 문제 자체를 이해하지 못하고 푼 결과이다. -> 주어진 예시에 대해서 먼저 제대로 이해하고, (시간 충분히 갖자) 코드 하자.

from itertools import combinations

def solution(orders, course):
    answer = []
    element = [] # A, B, C
    temp = ""
    
    for i in orders:
        temp += i
    element = list(set(temp))
    
    for num in course:
        combiList = [] # AB, BC, CA

        combiList = list(combinations(element, num))
        
        for combi in combiList:
            count = 0

            for item in orders:
                if set(combi).issubset(set(item)):
                    count += 1

                if count == 2:
                    # TODO: 알파벳 순으로 answer 바꿔야 함
                    answer.append(''.join(combi))
                    break

    return answer

두 번째 시도는 테스트케이스 13, 14, 15 번에서 시간초과가 뜬 풀이이다. orders에 대해서 무작정 모든 경우의 수를 구해서 생긴 문제인데, 이 글과 이 글을 참고해서 힌트를 얻었다. 모든 경우의 수를 구할 필요가 없지. 만약 num이 7이라면 orders 중에 7 이상인 대상에 대해서, 각각 가능한 조합을 만들고 더하는 형태로 구현했더니 해결 완료.

from itertools import combinations


def solution(orders, course):
    answer = []
    element = []  # A, B, C
    temp = ""

    for i in orders:
        temp += i
    element = list(set(temp))
    maxLen = max([len(k) for k in orders])

    for num in course:  # 2, 3, 4
        if num > maxLen:
            print(max(orders))
            continue

        answerList = {}

        combiList = []  # AB, BC, CA

        combiList = list(combinations(element, num))

        for combi in combiList:
            count = 0
            for item in orders:
                # print(combi, count, item)
                if set(combi).issubset(set(item)):
                    # print(set(combi), set(item), count)
                    count += 1
            tmp = ''.join(sorted(list(combi)))
            answerList[tmp] = count

        # print(answerList)
        all_values = answerList.values()
        max_value = max(all_values)
        if max_value > 1:
            answer += [k for k, v in answerList.items() if v == max_value]

    answer.sort()
    return answer


print(solution(["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"], [2, 3, 4]))
# ["AC", "ACDE", "BCFG", "CDE"]

다른 풀이

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) ]

'가장 많은' 데이터 세 기. dictionary를 사용해서 할 수 있는데 python의 기본 으로 제공하는 collections 모듈의 Counter라는 클래스를 알아보자. 다음 글의 도움을 받았다.

https://www.daleseo.com/python-collections-counter/

 

이건 combination 중복되는게 발생할 수 있는 구조임. 나는 set을 이용하긴 했는데 어느게 성능이 더 좋은 것일지?

처음에 이렇게 생각했는데 이게 이 문제를 푸는 방법 이었음 ㅋㅋㅋ 나는 한 번 더 생각한 구조였네.

IDEA

sorted(LIST) 는 새로운 리스트를 반환하는 것이고

LIST.sort()는 기존 리스트 자체를 바꾸는 것이다.

 

효율성 따지기. 모든 조합을 구할 필요가 없었다. 조금 더 생각해봐야 할 영역.

 

문제에 제시되어 있는 예시들은 제대로 이해하고 코드 접근하기. 이게 시간을 줄일 수 있는 방법이다.

 

sorted("BAC") => ['A', 'B', 'C']

sorted() 내에 들어갈 매개변수는 iterable한 객체이기 때문에 문자열(str)을 넣어도 된다. 리스트로 변환 작업 할 필요가 없음. 반환은 무조건 리스트로 함.

• 대표적으로 iterable한 타입 - list, dict, set, str, bytes, tuple, range

for k, v in 튜플의 리스트: (1, 2) 이런 튜플이 모아져 있는 형태라면 이렇게 for 문으로 분리 가능

기타

2021 카카오 신입공채 1차 온라인 코딩 테스트 - 2번 문제 풀이

'테스트 케이스를 모두 통과해야 풀이한 것으로 인정한다.'

이 문제에서 모든 combination 구하는 방식으로 해결했으면 다 풀어놔도 결국 못 푼 문제가 되는 셈이다.