[Javascript/PGS] Lv.3 : 보석 쇼핑

 

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

프로그래머스

---

프로그래머스 레벨 3.

 

처음에 이중 반복문으로 풀었다가 범위 보니 시간초과날 것 같아서 갈아엎었다.

투포인터/슬라이딩 윈도우를 적용해야하는 문제인건 눈치를 챘는데

구현 방식이 가물가물해서 고전했다..^-^

 

그리고 슬라이딩 윈도우를 잘못 적용해서 비효율적인 코드가 됨. (그냥 계속 창문 만드는 사람 됨)

개선 방법을 찾아보니 Map을 사용해서 Set과 갯수 비교를 하면 된다고 하길래 깜짝 놀랐다

실전에서 이런 아이디어를 떠올리려면 더 열심히 해야겠음ㅠ

생각해보니 Map도 key값 중복이 안되니까 Set이랑 종류 갯수 비교가 가능하다

 

gpt..공부 시켜줘서 고맙다

 

 

나의 풀이

var answer = [];

function solution(gems) {
    let gemSet = new Set(gems);
    let size = gemSet.size;
    let start = 0;
    let end = 0;
    let gemCount = new Map(); // 현재 윈도우 내 보석 개수
    let min = 100001;
    // 각 인덱스 start에서 최소 end값 찾기
    while(end < gems.length){
        gemCount.set(gems[end], (gemCount.get(gems[end])||0) + 1);
        
        while(size == gemCount.size){ // 윈도우 내부의 종류 갯수가 같을 동안
            if(min > end-start){
                min = end-start;
                answer = [start+1, end+1];
            }
            // 앞부분 제거 후 start + 1 (축소)
            gemCount.set(gems[start], gemCount.get(gems[start]) - 1);
            if (gemCount.get(gems[start]) === 0) {
                gemCount.delete(gems[start]);
            }
            start++;
        }
        // 종류 갯수가 다르다면 end + 1 (확장)
        end++;
    }
    
    return answer;
}

 

프로그래머스 레벨3 정답률 50%대 이하부터는 결코 만만하지 않다....

복습해야지!!