[프로그래머스] 보석 쇼핑
✔️ 문제
- 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/67258
- 카카오 기술블로그 문제 해설 : https://tech.kakao.com/2020/07/01/2020-internship-test/
- 2020 카카오 인턴 채용 코딩테스트 기출문제다.
✔️ 문제 이해
- 매장 진열대에 보석이 놓여져 있다.
- 어피치는 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 연속된 구간을 찾아서 구매하려고 한다.
- 진열대 번호 순서대로 보석들의 이름이 저장된 배열 gems가 매개변수로 주어진다. 이때 모든 보석을 하나 이상 포함하는 가장 짧은 구간을 찾아서 return 하도록 solution 함수를 완성하면된다.
- 제한 사항
- gems 배열의 크기는 1 이상 100,000 이하
- gems 배열의 각 원소는 진열대에 나열된 보석을 나타낸다.
- gems 배열에는 1번 진열대부터 진열대 번호 순서대로 보석이름이 차례대로 저장되어있다.
- gems 배열의 각 원소는 길이가 1 이상 10 이하인 알파벳 대문자로만 구성된 문자열이다.
✔️ 알고리즘 설계
set을 사용하여 주어진 보석의 종류수를 구한다.투포인터기법을 사용해 진열대의 가능한 모든 구간을 살펴본다.map을 사용하여 구간내 보석의 개수를 카운트한다.
✔️ 알고리즘 설계
-
배열로 들어오는 보석들을 모두 셋에 넣고 셋의 크기를 확인하면, 보석의 종류 개수를 얻을 수 있다.
-
map을 사용해 구간에 포함된 보석의 개수를 관리한다. map의 크기는 현재 구간에 포함된 보석의 개수다.
- 구간에 보석이 포함 : m[루비] ++;
- 구간에서 보석을 제거 : m[루비] –;
- 만약 m[루비] 가 0이되면 map에서 루비를 제거해준다.
👨🏻💻 소스 코드
#include <unordered_map>
#include <unordered_set>
#include <iostream>
using namespace std;
vector<int> solution(vector<string> gems) {
vector<int> answer;
answer.push_back(0);
answer.push_back(0); // 정답 리턴을 위한 초기화
// set을 사용하여 보석의 종류수를 센다.
unordered_set<string> s;
for (auto tmp : gems) {
s.insert(tmp);
}
int kind = s.size();
// map을 사용하여 구간내 보석의 빈도수를 센다.
unordered_map<string, int> m;
int start = 0, end = 0;
int minDist = 0x7fffffff;
// 투포인터 기법을 사용해 연속된 구간들을 탐색해본다.
while (1) {
if (m.size() >= kind) { // 현재 구간이 조건에 맞는다면,(모든 종류의 보석을 포함한다면)
m[gems[start]]--; // 구간을 줄여본다.(맨앞 보석을 제거)
if (m[gems[start]] == 0)
m.erase(gems[start]);
start++;
} // 현재 구간이 조건에 맞지않고, 마지막 포인터가 범위를 초과하면,
else if (end == gems.size())
break; // 구간 탐색을 중지한다.
else { // 현재 구간이 조건에 맞지 않는다면, 마지막 포인터를 증가시켜본다.(맨뒤에 보석 추가)
m[gems[end]]++;
end++;
}
if (m.size() == kind) { // 현재 구간이 조건에 맞는지 확인한다.(모든 종류 보석 포함여부)
if (abs(end - start) < minDist) { // 조건을 만족하는 최소 구간을 구한다.
minDist = abs(end - start);
answer[0] = start + 1;
answer[1] = end;
}
}
}
return answer;
}
✔️ 문제 회고
- set과 map을 잘 사용할 수 있어야했다.
- c++의 set과 map은 레드블랙 트리로 구현돼있다. 따라서 O(logN) 시간이 걸린다. 저장되는 원소가 정렬된다.
- unordered_set과 unordered_map은 해쉬 테이블로 구현돼있다. 따라서 O(1)~O(N) 시간이 걸린다. 저장되는 원소가 정렬되지 않는다.
- unordered_set, unordered_map을 사용했더니 대략 3배 정도 빨랐다.
- 투포인터는 두 개의 포인터를 조작하며 구간을 탐색하는 기법이다.
- 좋은 투포인터 설명 : https://blog.naver.com/kks227/220795165570