1. [C++] 프로그래머스 2020 카카오 인턴십 : 보석쇼핑 - 코딩도치

안녕하세요. 코딩도치입니다~

 

오늘은 프로그래머스에 있는 2020 카카오 인턴십 : 보석쇼핑 문제를 풀어보려고 합니다!

 

해당 문제는 정확성과 효율성까지 테스트하는 문제입니다.

 

그래서 문제를 딱 보고 완전탐색과 같은 방법으로 해결할 수는 있겠지만, 그렇게 하면 효율성 테스트를 통과할 수 없겠죠?

 

여기서 필요한 알고리즘이 바로 투 포인터(Two Pointer) 알고리즘입니다.

 

어떠한 연속된 배열의 범위를 구하는 문제이고, 빠른 검색을 요구하기 때문에 위 알고리즘을 생각해볼 수 있는 것입니다.

 

먼저 투 포인터(Two Pointer)가 무엇인지부터 살펴보겠습니다.

 

투 포인터(Two Pointer)란,

 

리스트를 두 개의 포인터를 이용해 순차적으로 접근하면서,  두 포인터 구간의 값이 타겟 값과 같을 때 까지 포인터를 조작하는 기법을 말합니다.

 

지렁이가 기어가는 모습을 상상해 보시면 쉽게 이해할 수 있습니다!

 

배열이 있을 때 배열의 인덱스를 가리키는 포인터를 아래와 같이 두개를 선언합니다.

 

처음에는 위치가 동일하겠죠?

문제 해결을 위한 어떠한 조건에 의해서 포인터 하나가 뒤로 움직이게 됩니다.

원하는 결과값을 얻지 못했다면 어떠한 조건에 의해서 또 다른 포인터가 움직이게 되는 것이죠.

색칠된 부분을 보시면 지렁이가 움직이는 것 같지 않나요?!(앞으로 이동하기 위해 늘어났다가 줄어들고 하니까요😙)

 

이렇게 두개의 포인터가 조건에 의해서 움직이면서 두 포인터 사이에 범위를 생성하게 되고, 원하는 결과값을 얻을 수 있는지 확인하는 것입니다.

 

투 포인터를 이용하게 되면,

 

이중 반복문을 이용하지 않고 리스트를 한번 탐색하는 것으로 원하는 결과값을 얻을 수 있으니 훨씬 효율적이겠죠??

 

그 효과는 데이터가 많아지면 많아질 수록 확연히 차이날 것입니다.

 

그럼 본격적으로 투 포인터를 이용해서 2020 카카오 인턴십 : 보석 쇼핑 문제를 풀어보도록 하겠습니다!

 

해당 문제는 진열되어 있는 보석들의 배열이 매개변수로 들어오는데, 그 중에는 중복된 보석들도 많이 있습니다.

 

저희는 범위 안에 보석이 종류별로 한가지씩만 포함되면 되기 때문에, 먼저 보석의 종류가 몇가지인지 알아야합니다.

 

그리고 do while문을 이용해서 start포인터가 end포인터와 같아질 때까지 반복 조건을 걸어주었습니다.

 

보석을 종류별로 포함하는 범위는 다양하고 그 중에서 가장 범위가 짧은 경우를 골라야 하기 때문에,

 

start와 end 포인터가 배열의 끝에서 만나면 반복이 끝나도록 조건을 설정한 것입니다.

 

(do while을 사용한 것은 처음 start와 end포인터가 동일한 시작 위치에 있기 때문입니다!)

 

그럼 각 포인터가 움직이는 조건을 알아보도록 하겠습니다.

 

이때, c++의 map 자료구조를 사용하였습니다.

 

key 값이 보석의 이름이 되고, value값이 범위 안에 보석의 개수가 되도록 하였습니다.

 

즉, 범위 안에 모든 종류의 보석이 있다면, map의 사이즈는 보석의 종류수가 되는 것입니다.

 

범위 안에 같은 종류의 보석이 여러개 나오더라도 해당 보석의 value값이 증가는 것이지 map자체의 요소의 수가 증가하지 않기 때문입니다.

 

먼저, map의 사이즈가 보석 종류수와 같은지 그리고 end포인터가 보석 배열의 사이즈를 넘어가지 않는지 체크합니다.

    - map의 사이즈가 보석 종류수와 같지 않고, end포인터가 배열의 사이즈를 넘어가지 않는다면

       end 포인터가 가리키고 있는 보석이 map의 요소인지 확인합니다. 

    - map의 요소라면 해당 요소의 value값을 1 증가시키고, 요소가 아니라면 맵의 요소로 추가합니다(value값은 1).

    - end 포인터를 1 증가시킵니다.

 

위와 같은 조건으로 모든 종류의 보석이 들어오도록 end포인터를 증가시키면서 map을 먼저 채우는 것입니다.

 

map의 사이즈가 보석 종류수와 같다면 start 포인터를 움직일 시간이 된 것입니다.

    - 먼저 배열을 끝까지 돌면서 end포인터가 배열의 끝에 도착했을 때 map에 모든 종류의 보석이 들어 있지 않을 때에도 이번 로직에 들어        오게 되므로 map의 사이즈가 보석 종류의 수와 같은지 확인하는 작업을 통해 불필요한 검색을 하지 않도록 탈출 조건을 걸어 줍니다.

    -  start포인터가 앞으로 이동하면서 범위에서 보석을 하나씩 빼는 것이기 때문에

       map에서 포인터가 가리키고 있는 보석의 value값을 1 감소 시킵니다.

    - 이때, 감소시킨 후 해당 보석의 value값이 0이라면 해당 보석이 없다는 것이므로 모든 종류를 포함하도록 하는 범위가 깨지는 것입니다.

       따라서 현재 start포인터부터 end포인터까지가 모든 종류를 포함하도록 하는 범위인 것입니다.

    - 기존에 있던 answer의 범위보다 현재 찾은 start, end 포인터 범위가 짧다면 answer의 범위를 교체해줍니다.

    - 그리고 이후 end포인터가 다시 증가할 수 있도록 해당 보석 요소를 map에서 제거해줍니다.

    - start 포인터를 1증가시킵니다.

 

저는 이러한 조건들을 걸어주고 문제를 해결했는데요.

 

저보다 저 효율적인 소스코드를 작성한 분들도 있을 수 있으니 좋은 의견 있으시면 댓글 남겨주세요!

 

감사합니다!

 

#include <string>
#include <vector>
#include <map>

using namespace std;

vector<int> solution(vector<string> gems) {
    vector<int> answer{1,100000};
    map<string, int> map;
    int kind = 0, start=0, end=0;
    
    // 보석 종류수 알아내기
    for(int i=0; i<gems.size(); i++){
        map[gems[i]] = 1;
    }
    
    kind = map.size();
    map.clear();
    
    // 투 포인터로 검색 시작
    do{
        if(map.size() != kind && end < gems.size()){ 
            string temp = gems[end++];
            
            if(map[temp] == 0){
                map[temp] = 1;
            }else{
                map[temp]++;
            }
        }else{
            if(map.size() != kind){
                break;
            }
            
            string temp = gems[start++];
            
            map[temp]--;
            
            if(map[temp] == 0){
                
                if(end - start < answer[1] - answer[0]){
                    answer[0] = start;
                    answer[1] = end;
                }
                
                map.erase(temp);
            }
        }
    }while(start != end);
    
    return answer;
}