[2021 KAKAO Blind Recruitment] Q2. 메뉴 리뉴얼 (C++, Python, Java)

문제 링크

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

 

예상 난이도

S2 - G5

 

알고리즘 분류

정렬, 브루트 포스

 

풀이

이 문제는 코스 메뉴 조합을 추출하는 부분과 코스요리 메뉴의 빈도를 계산하는 부분으로 나눌 수 있습니다. 우선 코스 메뉴 조합 추출부터 생각해보면, 이건 2진법을 이용해 쉽게 처리가 가능합니다.

 

그 다음으로 진행되는 빈도 계산의 경우, 여러가지 방법이 있으니 이 방법들을 알아봅시다.

 

O(N²)에 처리하는 방법은 그냥 배열에 다 담아둔 후 2중 for문을 돌면서 빈도를 세는 방법입니다.

 

빈도 계산을 O(NlgN)에 처리할 수 있는 첫 번째 아이디어는 정렬을 거치고 나면 내용이 동일한 원소들끼리 붙어있게 된다는걸 이용하는 방법입니다. 이 방법에 대한 자세한 설명이 필요하다면 정렬 II 단원을 참고해주세요.

 

정렬을 이용한 방법을 공부해둘 필요는 있지만 사실 해쉬 혹은 Binary Search Tree를 사용하면 매우 편하게 구현을 할 수 있습니다.

 

이렇게 여러가지 방법이 있는데 2중 for문을 도는 O(N²) 방법의 경우 N이 최대 20,000이기 때문에 사용할 경우 시간초과가 발생될 수 있습니다. 정렬을 이용한 방법은 사용해도 괜찮지만 그보다는 구현이 편리한 해쉬 혹은 BST를 이용합시다.

 

 

코드(C++)

 

A. 코스 메뉴 조합 추출 안에서 주석처리한 부분은 그 밑의 5줄과 완전히 동일한 기능을 합니다. 비트 연산에 익숙하다면   2진법에 대한 처리를 저렇게 하는 것도 고려해볼 수 있습니다. << 는 left shift로, 1 << order.size() 를 하게 되면 2의 order.size() 제곱이 계산됩니다.

 

코드(Python)

 

코드에 대한 설명은 위의 설명을 참고해주세요. 참고로 Python에는 dictionary보다 더 풍성한 기능을 가지고 있는 Collections라는 모듈이 있습니다. 이 모듈을 활용하면 코드를 더욱 짤막하게 만들어낼 수 있습니다. 다른 사람의 코드를 참고해보세요.

 

코드(Java)

 

코드에 대한 설명은 위의 설명을 참고해주세요.