오늘 풀어본 문제는 프로그래머스 보석쇼핑 이다!
2020 카카오 인턴십 3번 문제이고 Level 3 문제였다. 문제에 정확성 테스트와 효율성 테스트가 모두 존재했기 때문에 시간 초과를 조심해야 할 것이라 예상했고 나름대로 방법을 생각해 봤으나 통과하지 못할 것 같긴 했다,, 하지만 고민 시간이 이미 30분이 지났었기 때문에 실전처럼 그냥 풀었고, 그나마 긍정적이었던건 정확성 테스트는 한번에 모두 통과했다!
이후 해설을 보고 다시 풀어봤고 TwoPointer 를 사용하는 문제였다!
프로그래머스 보석쇼핑
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
개발자 출신으로 세계 최고의 갑부가 된 어피치는 스트레스를 받을 때면 이를 풀기 위해 오프라인 매장에 쇼핑을 하러 가곤 합니다.
어피치는 쇼핑을 할 때면 매장 진열대의 특정 범위의 물건들을 모두 싹쓸이 구매하는 습관이 있습니다.
어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 아래 목적을 달성하고 싶었습니다.
진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매
예를 들어 아래 진열대는 4종류의 보석(RUBY, DIA, EMERALD, SAPPHIRE) 8개가 진열된 예시입니다.
| 진열대 번호 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 보석 이름 | DIA | RUBY | RUBY | DIA | DIA | EMERALD | SAPPHIRE | DIA |
진열대의 3번부터 7번까지 5개의 보석을 구매하면 모든 종류의 보석을 적어도 하나 이상씩 포함하게 됩니다.
진열대의 3, 4, 6, 7번의 보석만 구매하는 것은 중간에 특정 구간(5번)이 빠지게 되므로 어피치의 쇼핑 습관에 맞지 않습니다.
진열대 번호 순서대로 보석들의 이름이 저장된 배열 gems가 매개변수로 주어집니다. 이때 모든 보석을 하나 이상 포함하는 가장 짧은 구간을 찾아서 return 하도록 solution 함수를 완성해주세요.
가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며, 만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.
입출력
[제한사항]
- gems 배열의 크기는 1 이상 100,000 이하입니다.
- gems 배열의 각 원소는 진열대에 나열된 보석을 나타냅니다.
- gems 배열에는 1번 진열대부터 진열대 번호 순서대로 보석이름이 차례대로 저장되어 있습니다.
- gems 배열의 각 원소는 길이가 1 이상 10 이하인 알파벳 대문자로만 구성된 문자열입니다.
| gems | result |
|---|---|
| ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] | [3,7] |
| ["AA", "AB", "AC", "AA", "AC"] | [1,3] |
| ["XYZ", "XYZ", "XYZ"] | [1,1] |
| ["ZZZ", "YYY", "NNNN", "YYY", "BBB"] | [1,5] |
풀이
시간초과 발생
먼저 처음에 시간초과를 피해갈 확실한 방법을 생각해내지 못했었다.
dp 를 사용해야 하나,, 고민해봤지만 떠올리지 못했고 일단 내가 할 수 있는대로 최선의 방법을 생각해 보았다.
배열 gems 의 크기가 최대 100,000 이므로 최대한 탐색 횟수를 줄여야 했다. 먼저 gems 에 등장하는 보석 종류들을 배열 kinds 에 담고 (<algorithm> 헤더의 sort, unique 이용) gems 를 한번 선형 탐색 하면서 보석 종류별로 등장 위치를 오름차순으로 map<string, vector<int>> location 에 담았다.
이후 gems[i] 원소를 기준으로 i 이후 원소 중에 gems[i] 가 아닌 보석이 가장 빨리 나오는 위치를 location 을 통해 구하고 모든 종류의 보석이 i 이후에 존재한다면 그 범위를 저장하였다.
정확성 테스트에서는 모두 통과했지만 효율성 테스트에서는 모두 시간 초과가 떴고 예상했던 결과이기 때문에 해설을 보고 새로운 접근 방법을 알게 되었다.
시간 초과 코드
#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
int isGemExist(map<string, vector<int>> locations, int front, string gem){
for (int i = 0; i < locations[gem].size(); ++i) {
if (locations[gem][i] > front) return locations[gem][i];
}
return -1;
}
vector<int> solution(vector<string> gems) {
vector<int> answer;
vector<string> kinds = gems;
map<string, vector<int>> locations;
sort(kinds.begin(), kinds.end());
kinds.erase(unique(kinds.begin(), kinds.end()), kinds.end());
int K = kinds.size();
if (K==1){
answer.push_back(1);
answer.push_back(1);
return answer;
}
for (int i = 0; i < gems.size(); ++i) {
if (locations.find(gems[i]) == locations.end()){
locations[gems[i]] = vector<int>();
}
locations[gems[i]].push_back(i);
}
bool searchable = true;
int i = 0;
int start, end, length = gems.size()+1;
while (searchable){
string now = gems[i];
int back = i;
for(int j = 0; j<K; j++){
if (kinds[j] ==now) continue;
int next = isGemExist(locations, i, kinds[j]);
if(next > i) {
if (back < next) back = next;
continue;
}
else searchable = false;
}
if (searchable && length > (back-i+1)){
start = i;
end = back;
length = back-i+1;
}
i++;
}
answer.push_back(start+1);
answer.push_back(end+1);
return answer;
}정답 풀이
나의 풀이의 경우 배열 gems를 최소 2번은 탐색해야 하고 그 외에 location, kinds 에 접근하는 등의 시간이 필요하다.
하지만 통과된 풀이에선 배열 gems 진열대 위에 위치하는 두개의 포인터 left, right 를 이용한다.
우리는 left - right 구간에 위치하는 보석들이 총 몇개의 종류인지를 확인 하는데 우리는 최소 구간을 찾는 것이므로 가장 좁은 범위(1)에서 시작하고 left, right 모두 진열대 가장 왼쪽에서부터 시작한다. 혹은 뭐 오른쪽에서 해도 알고리즘상에 문제는 없을 것 같다.
만약 left-right 구간에 존재하는 보석이 전체 종류보다 작다면 범위를 늘려야 하므로 right를 증가시키고, 전체 종류 수와 같다면 범위를 좀 더 좁힐 수 있는지 확인해야 하므로 left를 증가시킨다.
이 때, 매번 left->right 로 탐색을 진행한다면 시간복잡도가 증가할 것이기 때문에 이전에 확인한 보석 종류에서 left를 증가시킨 경우에는 가장 왼쪽의 보석을 제외시키고 right를 증가시킨 경우엔 새로운 right 위치의 보석 종류를 포함시킨다.
이 과정에 map<string, int> count 을 사용하는데 이는 현재 left-right 구간 내에 각 보석이 몇번 진열되어 있는지를 나타낸다! 만약 새로운 종류의 보석이 들어오면 count의 새로운 key 로 추가시켜주고 left를 증가시킨 뒤 더이상 이전의 보석이 구간에 존재하지 않는다면 count 에서 해당 key 값을 제외시킨다.
즉, map<string, int> count 의 크기가 현재 두 포인터가 가리키는 구간에 존재하는 보석 종류의 수를 나타내게 되는 것이다!
늘 그렇지만,, 투포인터만 생각했다면 풀 수 있었을 것 같아서 아쉽다 ,,! 하지만 다음주 토요일까지 반복해서 여러 문제를 풀어보면 또 생각이 날 수 있지 않을까,,? 제발!
통과 코드
#include <vector>
#include <algorithm>
#include <map>
// 프로그래머스 보석 쇼핑, 투포인터, level3, 2020 카카오 인턴십
using namespace std;
vector<int> solution(vector<string> gems) {
vector<int> answer;
vector<string> kinds = gems; // 존재하는 모든 보석 종류
sort(kinds.begin(), kinds.end());
kinds.erase(unique(kinds.begin(), kinds.end()), kinds.end());
if (kinds.size()==1){
answer.push_back(1);
answer.push_back(1);
return answer;
}
int left = 0, right = 0, length = gems.size()+1;
int start = 0, end = 0 ;
map<string, int> count;
count[gems[0]] = 1; // 첫 구간은 0-0
// gems 진열대 내에서 움직이는 두 포인터 left, right
while (left<=right && left>=0 && left<gems.size() && right>=0 && right<gems.size()){
if (count.size() == kinds.size()){ // 범위 좁히기
if (length > right-left+1){
length = right-left+1;
start = left;
end = right;
}
if (count[gems[left]] == 1) count.erase(gems[left]);
else count[gems[left]] -= 1;
left++;
}else{ // 범위 늘리기
if (right +1 <gems.size()){
if (count.find(gems[right+1]) == count.end()) count[gems[right+1]] = 1;
else count[gems[right+1]] += 1;
}
right++;
}
}
answer.push_back(start+1);
answer.push_back(end+1);
return answer;
}