[프로그래머스 보석 쇼핑] c++ (풀이,코드, 투포인터 알고리즘)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/67258

프로그래머스

 

문제

 

풀이 및 코드 (투포인터 알고리즘)

이 문제를 사용하기 위해 투포인터 알고리즘을 사용하였습니다.

 

투포인터 알고리즘이란?

https://bendeng-life.tistory.com/130

투포인터 알고리즘(Two-Pointer Algorithm)이란? (예시,활용코드)

투포인터 알고리즘이란 두 포인터를 이용하여 특정한 합을 가지는 부분 연속 수열의 합을 구할때 자주 사용하는 알고리즘이라고 할 수 있습니다.

 

이런 문제에서 저는 아무생각없이 dfs로 진입하였다가 시간초과로 뚜들겨 맞고 투포인터 알고리즘으로 호다닥 바꾸었습니다..ㅋㅋㅋㅋㅋㅋㅋ

 

문제를 예시인  ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]를 기준에 뒤에 RUBY를 추가한 그림과 함께 보겠습니다.

즉, 조건에 충족(잼의 종류== 현재 잼의 종류) 할때까지 end 인덱스를 미루면서 충족을 할때는!!

start인덱스를 다시 밀게 되면서 반복합니다.

 

end인덱스가 마지막 그림인 start인덱스가 sapphire일때(마지막 그림, 조건을 충족했으니 start인덱스++을했음) 조건을 충족하지 않으니 end인덱스++를 하게 되면서 반복문을 이탈하는 구조를 가지게 하였습니다.

 

#include <string>

#include <vector>

#include <map>

using namespace std;

vector<int> solution(vector<string> gems) {

    vector<int> answer;

    map<string, int> m;

    int start = 0; // 시작지점

    int end = 0; // 끝나는 지점

    int gemCount = 0; // 보석 현재 갯수

    int startAns, endAns; // 위치 임시 저장

    int len = 100000;

    // 보석 종류의 갯수 세기

    for (int i = 0; i < gems.size(); i++) {

        m[gems[i]] = 0;

    }

    int gemType = m.size(); // 보석의 종류 갯수

    while (1) {

        if (gemType == gemCount) {

            // 최소 길이인지 확인하고 갱신

            if (end - start < len) {

                startAns = start;

                endAns = end;

                len = end - start;

            }

            if (m[gems[start]] > 1) {

                m[gems[start]]--;

                start++;

            }

            else {

                m[gems[start]]--;

                start++;

                gemCount--;

            }

        }

        else {

            // 종류와 현재 갯수가 다를 때, end를 이동시키면서 현재 종류와 같아지도록 함

            if (end == gems.size())

                break;

            if (m[gems[end]] == 0)

                gemCount++;

            m[gems[end]]++;

            end++;

        }

    }

    answer.push_back(startAns + 1);

    answer.push_back(endAns);

    return answer;

}