카카오 20상반기 인턴 코테 풀이(2) - 보석쇼핑

풀이 설명

지난번에 이어서 프로그래머스에 올라온 20년 상반기 카카오 인턴 코테 문제인 보석 쇼핑을 풀어보았다.

• 프로그래머스에 올라온 문제 : https://programmers.co.kr/learn/courses/30/lessons/67258

지난번 풀었던 “키패드 누르기”문제보다 난이도가 높은 편이다.

문제의 정확도 점수와 효율성 점수까지 있는 문제였다.

문제는 세계 최고 갑부 어피치가 오프라인 매장에서 진열대에 있는 보석을 구매하려고 하는데

진열대에 있는 모든 종류의 보석을 구매할 수 있는 가장 짧은 연속되는 진열대 구간[시작위치, 끝위치]을 구하는 문제이다.

가장 짧은 구간이 여러개인 경우, 시작 진열대 번호가 작은 구간을 선택한다.

문제를 풀기 위해 필요한 알고리즘을 정리해보면 다음과 같다.

1. 전 구간에서 unique 한 보석갯수를 세어야 하므로 보석이름을 key로 하는 map을 사용하여 unique한 보석갯수를 센다.

2. 우리가 구하려는 구간의 시작,끝 위치를 구하려면 완전 탐색이 필요하다.

   • 시간 복잡도 O(n) 이상

위와 같이 큰 틀에 대해 정리를 한 후 아래와 같이 코드를 구현하였다.

• 사용 언어: C++
• 프로그래머스에서 정확도 33.3, 효율성66.7 로 100점의 점수를 얻었다.