[프로그래머스] 파이썬 _ 메뉴리뉴얼 (2021 KAKAO BLIND) ⭕️

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

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

 

문제유형 : 문자열, 구현

 

문제풀이 : 

• 주어진 orders에 따라서 해당하는 각각의 개수만큼의 조합을 찾는다.
  • 예를들어, 주어진 배열이 ["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"],[2,3,4] 일때

  • // 각 원소에 대해서 차례로 2개개수 조합, 3개개수 조합, 4개개수 조합
    [('A', 'B'), ('A', 'C'), ('A', 'F'), ('A', 'G'), ('B', 'C'), ('B', 'F'), ('B', 'G'), ('C', 'F'), ('C', 'G'), ('F', 'G'), ('A', 'C'), ('C', 'D'), ('C', 'E'), ('D', 'E'), ('A', 'C'), ('A', 'D'), ('A', 'E'), ('C', 'D'), ('C', 'E'), ('D', 'E'), ('B', 'C'), ('B', 'F'), ('B', 'G'), ('C', 'F'), ('C', 'G'), ('F', 'G'), ('A', 'C'), ('A', 'D'), ('A', 'E'), ('A', 'H'), ('C', 'D'), ('C', 'E'), ('C', 'H'), ('D', 'E'), ('D', 'H'), ('E', 'H')]
    [('A', 'B', 'C'), ('A', 'B', 'F'), ('A', 'B', 'G'), ('A', 'C', 'F'), ('A', 'C', 'G'), ('A', 'F', 'G'), ('B', 'C', 'F'), ('B', 'C', 'G'), ('B', 'F', 'G'), ('C', 'F', 'G'), ('C', 'D', 'E'), ('A', 'C', 'D'), ('A', 'C', 'E'), ('A', 'D', 'E'), ('C', 'D', 'E'), ('B', 'C', 'F'), ('B', 'C', 'G'), ('B', 'F', 'G'), ('C', 'F', 'G'), ('A', 'C', 'D'), ('A', 'C', 'E'), ('A', 'C', 'H'), ('A', 'D', 'E'), ('A', 'D', 'H'), ('A', 'E', 'H'), ('C', 'D', 'E'), ('C', 'D', 'H'), ('C', 'E', 'H'), ('D', 'E', 'H')]
    [('A', 'B', 'C', 'F'), ('A', 'B', 'C', 'G'), ('A', 'B', 'F', 'G'), ('A', 'C', 'F', 'G'), ('B', 'C', 'F', 'G'), ('A', 'C', 'D', 'E'), ('B', 'C', 'F', 'G'), ('A', 'C', 'D', 'E'), ('A', 'C', 'D', 'H'), ('A', 'C', 'E', 'H'), ('A', 'D', 'E', 'H'), ('C', 'D', 'E', 'H')]
    

• Counter함수를 이용해서 각 원소가 몇개인지 센다.
  • 이때 ('X','Y') 와 ('Y','X')를 같게 하기 위해서 정렬을 이용해서 두 원소를 같게해준다! ( 이부분에서 어떻게 두개를 같게할수 있을까 살짝 헤멤)
    
  • Counter의 most_common() : 아래처럼 가장많이 나온것부터 차례대로 보여준다. 인자로 숫자를 주면 그 갯수만큼만 보여준다.

  • [(('A', 'C'), 4), (('C', 'D'), 3), (('C', 'E'), 3), (('D', 'E'), 3), (('B', 'C'), 2), (('B', 'F'), 2), (('B', 'G'), 2), (('C', 'F'), 2), (('C', 'G'), 2), (('F', 'G'), 2), (('A', 'D'), 2), (('A', 'E'), 2), (('A', 'B'), 1), (('A', 'F'), 1), (('A', 'G'), 1), (('A', 'H'), 1), (('C', 'H'), 1), (('D', 'H'), 1), (('E', 'H'), 1)]
    

• 추가적인 예외들 :
  • 주어진 course배열의 최대문자열길이가 n인데 n보다 큰 order가 주어진경우 빈배열이 나오므로 index out of range에러를 방지하기위해 배열이 비어있을때를 체크해준다.
  • 주문한 사람이 최소 2명이상이여야하므로 체크해준다.
  • 같은 최대값이 2개이상인경우가 있으므로 최대값을 지정하고 그 값과 같을때까지 계속 추가한다.

 

정답코드 : 

from itertools import combinations

from collections import Counter


def solution(orders, course):
    answer = []
    # 2개짜리인것들을 모두 배열의 원소로 만들고 Counter
    for i in course:  # 2,3,4
        # 만들수있는 2개, 3개 각각의 모든 조합을 찾는다.
        temp = []
        temp2 = []
        for j in orders:  # abcfg, ac
            if temp == None:
                temp = list((combinations(j, i)))
            else:
                temp.extend(list(combinations(j, i)))

        # ('X','Y') 와 ('Y','X')를 같게 하기 위해서
        for k in temp:
            temp2.append(tuple(sorted(k)))

        most_list = Counter(temp2).most_common()

        if not most_list:
            continue
        count = most_list[0][1]# 제일큰값
        for item in most_list:
            curr_count = item[1]
            if curr_count == count and curr_count >1:
                answer.append(item[0])
    result = []
    for t in sorted(answer):
        result.append(''.join(t))
    return result

 

풀이2 (210707) :

- 조합 바깥 포문에 안두고 안쪽포문에 두고 한 문자열에대해 모든조합구하고, 다음문자열 이렇게하니까 최종 딕셔너리에 문자열길이가 모두 섞여있게되서 더복잡하게 풀렸다..

from itertools import combinations
from collections import defaultdict
def solution(orders, course):
    answer = []
    dic = defaultdict(int)

    # 1. orders배열의 각 원소를 리스트로 하여 가능한 조합을 1~해당 원소의 길이까지 구한다.
    # 2. 딕셔너리에 해당 조합을 키로하여 값을 1 증가시킨다.
    # 3. course배열의 숫자를 하나씩 순회하면서 딕셔너리에 해당 길이와 매핑되는 키값을 찾는다.
    # 4. 키값이 여러개라면 값을 비교하여 가장큰값을 찾는다. 동일한값이 있을수 있다.
    # 5. result에 키값을 추가한다.
    # 6. result를 알파벳순 정렬하여 리턴한다.
    for i in orders:
        # 조합에서 가능한 갯수 2(최소2가지음식을 하나의코스)~ 해당문자열길이까지 
        for j in range(2, len(i)+1):
            for case in combinations(list(i), j):
                case = list(case)
                case.sort()   # x,y / y,x 같게 
                dic[''.join(case)] += 1
    divide = [ [] for i in range(course[-1]+1)]
    
    for i in dic.items():
        key, val = i[0], i[1]
        if len(key) in course and val > 1:
            divide[(len(key))].append((key,val))
        
    for i in course:
        for idx, j in enumerate(sorted(divide[i], key=lambda x: x[1], reverse=True)):
            if idx == 0:
                answer.append(j[0])
                curr_max = j[1]
            else:
                if curr_max == j[1]:
                    answer.append(j[0])
                else:
                    break
    answer.sort()
    return answer