programmers. 보석 쇼핑

문제

문제

코딩테스트 연습 - 보석 쇼핑

풀이

전형적인 투 포인터 문제..라고 하지만 나는 투 포인터를 어떻게 사용하는 것인지 몰랐다

1. 주어진 배열의 배열에 대해 0을 가르키는 두 개의 포인터(start, end)를 선언한다
2. start부터 end 까지의 원소들이 주어진 조건을 만족하는지 검사한다
3. 만족하지 않는다면 만족할 때 까지 end를 1씩 증가시킨다
4. 만족한다면 이제는 만족하지 않을 때 까지 start를 1씩 증가시킨다 (이 과정에서 조건을 만족->불만족으로 넘어갈 때 최소값을 찾을 수 있다) 증가시키면서 [start, end] 값을 매번 갱신해서 저장해둔다
5. end가 배열의 끝지점에 갈 때 까지 3-4를 반복한다

start부터 end까지의 원소들이 조건을 만족하는지 검사하는 과정에서 map을 사용했는데 map에 원소들을 넣으면서 map의 길이가 총 보석의 종류와 같은지 매번 비교해주었다

코드

function solution(gems) {
    let all = [...new Set(gems)];
    let map = new Map();

    let left = 0;
    let right = 0;
    let answer = [0, gems.length-1];
    let check = true;

    while(left<=right && right <= gems.length-1) {
        if(check && all.length !== map.size) {
            if(map.has(gems[right])) {
                map.set(gems[right], map.get(gems[right]) + 1);
            }
            else {
                map.set(gems[right], 1);
            }
        }
        if(all.length === map.size) {
            let [dx, dy] = answer;
            if(dy-dx > right - left) {
                answer = [left, right]
            }
            else if(dy-dx === right - left && left < dx) {
                answer = [left, right]
            }
            if(map.get(gems[left]) === 1) {
                map.delete(gems[left]);
            }
            else {
                map.set(gems[left], map.get(gems[left]) - 1);
            }
            left +=1;
            check = false;
        }
        else {
            right += 1;
            check = true;
        }
    }
    let [x ,y] = answer;
    return [x+1, y+ 1];
}

다른 풀이

위의 풀이에서는 map의 key를 보석의 이름 value를 개수로 저장해서 사용했지만 value에 인덱스를 저장해서 푸는 방법이 존재한다

맵에 보석 이름과 인덱스를 저장하고 새로운 보석이 들어간다면 이전의 값을 지우고 인덱스를 계속해서 갱신시켜주는 것

똑같이 맵의 크기가 총 보석의 종류와 같아지면 조건을 만족하는 상태이고 그 상태에서 map 원소의 첫 value와 마지막 value가 조건을 만족하는 배열의 인덱스가 된다

코드

function solution(gems) {
    var answer = [];
    const gemsLength = new Set(gems).size;
    const map = new Map();

    for(let i=0; i<gems.length;i++){
        if(map.has(gems[i])) map.delete(gems[i]);
        map.set(gems[i],i);

        if(map.size === gemsLength) {
            const temp = [map.values().next().value+1, i+1];
            answer.push(temp);
        }

    }
    answer.sort((a, b) => (a[1]-a[0]) - (b[1]-b[0]));
    return answer[0];
}