프로그래머스 - 보석 쇼핑 파이썬, C++

November 18, 2023

문제

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

접근 방식

투포인터를 사용해서 효율성 부분을 통과할 수 있습니다.

lt, rt라는 2개의 인덱스를 사용해서 0에서 시작해서 보석을 전체 포함하는 인덱스를 구합니다. 맨 왼쪽에 있는 lt를 오른쪽으로 한 인덱스씩 이동해서 문제에서 요구하는 최소 길이를 구할 수 있습니다.

풀이

from collections import defaultdict
def solution(gems):
    answer = [0, 0]
    d = defaultdict(int)
    LEN = len(gems)
    s = set(gems)
    unique_count = len(s)
    lt = 0
    max_length = 100_000

    for rt in range(LEN):
        d[ gems[rt] ] += 1
        
        while len(d) == unique_count:
            if rt - lt + 1 < max_length:
                max_length = rt - lt + 1
                answer = [lt + 1, rt + 1]
        
            d[ gems[ lt ] ] -= 1
            if d[ gems[ lt ] ] == 0:
                del d[ gems[ lt ] ]
            lt += 1
            
    return answer

#include <bits/stdc++.h>

using namespace std;

map<string, int> gemCount;

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

    set<string> uniqueGems(gems.begin(), gems.end());
    int uniqueCount = uniqueGems.size();

    vector<int> answer;

    int lt = 0;
    int maxLen = 100'000;

    for (int rt = 0; rt < gems.size(); ++rt) {
        gemCount[gems[rt]]++;

        while (gemCount.size() == uniqueCount) {
            if (rt - lt + 1 < maxLen) {
                maxLen = rt - lt + 1;
                answer = vector{lt + 1, rt + 1};
            }

            gemCount[gems[lt]]--;

            if (gemCount[gems[lt]] == 0) {
                gemCount.erase(gems[lt]);
            }
            lt++;
        }
    }

    return answer;
}