프로그래머스 (C/C++, Java) 67258 : 보석 쇼핑

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

프로그래머스

 

---

풀이

투포인터를 사용하는 것까진 알겠으나, 정확히 어떻게 사용해야 할지 모르겠어서 답지를 봤다.

'end로 모든 보석이 들어간 범위를 구한 후, start로 그 범위를 좁힌다'는 아이디어를 보고 set으로 모든 보석의 종류를  먼저 구했다.

이후 end를 늘려가며 현재 범위에 모든 보석이 들어 있는지를 확인했다. 이후 start를 늘리며 start에 위치한 보석을 제외해도 현재 범위에 모든 보석이 들어 있는지 확인한다. 이 범위의 최소 값을 구해 반환했다.

---

C/C++ 코드

#include <string>
#include <vector>
#include <set>
#include <unordered_map>

using namespace std;

vector<int> solution(vector<string> gems) {
    set<string> getGemTypeCnt;
    for (string gem : gems)
        getGemTypeCnt.insert(gem);
    
    int typeCnt = getGemTypeCnt.size();
    
    unordered_map<string, int> cntGems;
    set<string> types;
    
    int start = 0, end = 0;
    int minRange = 100'000, minEnd;
    
    while (end < gems.size()) {
        cntGems[gems[end]]++;
        types.insert(gems[end]);
    
        // 모든 종류의 보석이 범위 내에 있다면
        if (types.size() == typeCnt) {
            
            // start를 오른쪽으로 이동하며 범위를 좁힘
            while (start < end) {
                if (cntGems[gems[start]] > 1) {
                    cntGems[gems[start]]--;
                    start++;
                }
                else break;
            }
            
            // 최소 구간 갱신
            if (minRange > end - start) {
                minRange = end - start;
                minEnd = end;
            }
        }
        end++;
    }
    return {minEnd - minRange + 1, minEnd + 1};
}

 

Java 코드

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        int size = gems.length;
        
        // 보석의 종류의 수 구함
        Map<String, Integer> types = new HashMap<>(); 
        for (String gem : gems) 
            types.put(gem, 0);
        int typeCount = types.size();
        
        Set<String> cntTypes = new HashSet<>();
        int start = 0, end = 0, minLen = Integer.MAX_VALUE, minEnd = 0;
        for (String gem : gems) {
            cntTypes.add(gem);
            types.put(gem, types.get(gem) + 1);
            
            // 모든 종류의 보석이 범위 내에 있다면
            if (cntTypes.size() == typeCount) {
                
                // start를 오른쪽으로 이동하며 범위를 좁힘
                while (start <= end) {
                    int nowGemCount = types.get(gems[start]);
                    if (nowGemCount > 1)
                        types.put(gems[start], nowGemCount - 1);

                    else {
                        // 최소 구간 갱신
                        if (end - start < minLen) {
                            minLen = end - start;
                            minEnd = end;
                        }
                        break;
                    }
                    start++;
                }
            }
            end++;

        }
        return new int[]{minEnd - minLen + 1, minEnd + 1};
    }
}