Programmers - 메뉴 리뉴얼 (2021 Kakao Blind Recruitment)

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

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

 

해당 문제는 2021 KAKAO BLIND RECRUITMENT 1차 코딩 테스트에 출제된 문제입니다.

 

문제를 다 읽었을 때 들었던 느낌은 "카카오스럽다" 였습니다.

 

지금까지 카카오 코테 기출을 보면 문자열 문제가 1~3번에 무조건 출제되는 경향이 있는데 이 문제 역시 문자열 관련 문제였습니다.

 

문자열의 최대 길이가 10이기 때문에 각 문자열에서 나올 수 있는 모든 부분 문자열을 구하는 것이 시간 복잡도를 충분히 만족합니다. (사실 이 문제에서는 시간제한이 주어지지 않았기 때문에 상관없었음)

 

대부분 이렇게 많은 양의 문자열을 다루는 문제가 주어진다면 뒤도 안 돌아보고 MAP을 사용하면 됩니다.

 

제가 생각한 풀이과정은 다음과 같습니다.

 

map 2개 생성 - 1) 해당 문자열이 나왔는지 아닌지 확인할 배열, 2) 출현 개수 저장할 map

 

1. 문자열이 들어오면 모든 경우의 수를 만들기 (미리 문자열 내의 각 문자 사전 순으로 정렬시켜놓기)
2. 각각의 문자열들을 1번 map을 통해 이미 나왔는지 확인
   1) 이미 나온 문자열이라면 2번 map에서 출현 개수 ++
   2) 처음 나온 문자열이라면 2번 map에 새로 push
3. 2번 map에서 최댓값들만 뽑아서 answer 배열에 넣어놓고 sort 후 출력

 

map을 하나만 만들어도 충분히 해결 가능하지만

제가 두 개를 만든 이유는 "문자열의 길이 별로 저장하기 위해서"입니다.

 

정답을 구할 때 문자열의 길이별로 구해야 하기 때문에 위처럼 map을 두 개 만드는 게 훨씬 편합니다.

 

결론적으로 보면 이 문제는 "순열 생성", "Map 사용", "구현", "브루트포스", "문자열", "정렬" 등 여러 기본 알고리즘만으로도 풀 수 있었습니다.

 

아래의 링크에 코드를 남겨놓았습니다. 주석을 달았으니 이해하기 어렵지 않을 겁니다.

https://github.com/kimtaehyun98/Jandi/blob/main/2021.8/pm_%EB%A9%94%EB%89%B4%20%EB%A6%AC%EB%89%B4%EC%96%BC.cpp

GitHub - kimtaehyun98/Jandi: 🍀 Solved.AC & GitHub 잔디 심기