[투포인터] 프로그래머스 '보석 쇼핑' - js

1. 문제

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

프로그래머스

2. 코드

처음 푼 코드) 타임아웃. 또 예상했던 것. gems 길이가 길어지면 완탐으로는 시간이 오래걸릴 것 같다고 생각했다.

function solution(gems) {
    let set = [...new Set(gems)]; // 보석 종류
    let visited = new Array(set.size).fill(0);
    let candidate = [];
    let answer = [];
    
    for(let i=0;i<gems.length;i++){
        visited[set.indexOf(gems[i])] = 1;
        let temp = 0;
        for(let j=i;j<gems.length;j++){
            if(visited.filter(el => el===0).length < set.length) visited[set.indexOf(gems[j])] = 1;
            if(visited.filter(el => el===1).length === set.length) {
                temp = j;
                break;
            }
        }
        if(visited.filter(el => el===1).length === set.length) candidate.push([i+1,temp+1]);
        visited = new Array(set.size).fill(0);
    }
    
    let min = 99999;
    
    for(let i=0;i<candidate.length;i++){
        if(candidate[i][1] - candidate[i][0] < min) {
            answer = candidate[i];
            min = candidate[i][1] - candidate[i][0];
        }
    }
    
    return answer;
}

정답)

https://tech.kakao.com/2020/07/01/2020-internship-test/

function solution(gems) {
    const cnt = new Set(gems).size;
    let answer = [1, gems.length];
    let l = 0, r = 0; // 투포인터
    const visited = new Map(); // 보석 방문 여부
    visited.set(gems[0], 1);

    while (r < gems.length) {
        if (visited.size === cnt) { // 모든 보석 종류 
            // 지금 answer 값 차이보다 현재 포인터가 가리키는 위치 차이가 더 작다면
            if(answer[1] - answer[0] > r - l) 
                answer = [l + 1, r + 1]

            visited.set(gems[l], visited.get(gems[l]) - 1); // l 포인터 오른쪽으로 한 칸
            if (visited.get(gems[l]) === 0) visited.delete(gems[l])
            l++;
        }
        else {
            r++; // r 포인터 오른쪽으로 한 칸
            visited.set(gems[r], (visited.get(gems[r]) || 0) + 1);
        }
    }
    return answer;
}

 

투포인터 알고리즘은 배열과 같이 연속적인 값에서 특정 부분을 조건에 맞게 잘라내야 할 때 사용한다.

 

복기

6/27