[Python] 프로그래머스 : 메뉴 리뉴얼 (구현)

2021 카카오 블라인드 채용
https://school.programmers.co.kr/learn/courses/30/lessons/72411

머리말

풀이 시간 1시간 5분

처음 생각한 로직을 쭉 풀어쓰다가 문제에서 이해하지 못한 부분 때문에 코드가 난잡해졌다.

접근 방법

2번 예제에서 왜 AB는 답에 포함되지 않을까 고민을 많이 했다.
하지만 문제에서 가장 많이 함께 주문한 단품 메뉴들을 코스요리 메뉴로 구성 이라는 말을 잘 생각해야 한다.
AB도 2번 이상 포함되기는 하지만, AD, CD가 3번씩 포함되므로 이것만 답에 포함시켜야 한다.

나는 다음과 같은 로직으로 문제를 풀었다.

• 단품 메뉴 가장 많이 주문한 사람의 개수를 maxLen에 저장한다.
• 그 개수가 course 보다 작다면 확인할 필요가 없으므로 건너뛴다.
• courses를 순회하면서 c개만큼 순열을 구할 것이다.
• 그 순열을 포함하는 course를 구해서 checkTwoList에 넣는데, checkTwo는 몇 명의 사람이 순열을 포함하는지를 나타낸다.
• 가장 많이 포함하는 checkTwo에 해당하는 사람의 주문 순열을 answer에 저장한다.
• courses를 모두 순회하며 순열을 구하기 때문에 AX, XA와 같은 것을 다르게 해석한다. 따라서 정답을 출력하기 전에 해당 중복을 제거한다.

🐥 이건 얻어가자

• 문자열 길이 기준 최댓값 구하기 : maxLen = len(max(orders, key=len))
• 조합 구하기
  • from itertools import combinations
  • for comb in combinations(splits, c):
• 리스트 안에 특정 문자 포함하는 개수 구하기: listA.count(strB)
• tuple to string: ''.join(comb)
• string을 사전 순으로 정렬하기: ''.join(sorted(answer[i]))
• list 중복제거: answer = list(set(answer))

코드

from itertools import combinations

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

    maxLen = len(max(orders, key=len))

    for c in course:
        if c > maxLen: continue

        # order를 탐색하면서
        checkTwoList = []
        checkTwoMax = 0

        for order in orders:
            if len(order) < c: continue

            # 순열 구해서 orders를 순회하며 해당 순열이 모두 포함되면 answer에 넣기
            splits = list(order)
            for comb in combinations(splits, c):
                checkTwo = 0

                for order in orders:
                    checkC = 0
                    for i in comb:
                        checkC += order.count(i)
                    if checkC >= c: checkTwo += 1

                if checkTwo >= 2:
                    if checkTwo > checkTwoMax: checkTwoMax = checkTwo
                    checkTwoList.append((checkTwo, ''.join(comb)))

        for i in checkTwoList:
            if i[0] == checkTwoMax:
                answer.append(i[1])

    for i in range(len(answer)):
        answer[i] = ''.join(sorted(answer[i]))

    answer = list(set(answer))    
    answer.sort()

    return answer

더 읽을거리

• https://pybasall.tistory.com/67
• https://pearlluck.tistory.com/468
• https://velog.io/@daybreak/Python%EC%97%90%EC%84%9C-%EB%A6%AC%EC%8A%A4%ED%8A%B8-%EC%A4%91%EB%B3%B5%EC%A0%9C%EA%B1%B0
• https://stackoverflow.com/questions/15046242/how-to-sort-the-letters-in-a-string-alphabetically-in-python