[JS] 보석 쇼핑: 효율성을 어거지로 통과하는 방법

어제 했던 등산 코스 문제를 보고나니 이문제.. 정말 선녀네요.

길게 말할 것도 없습니다. 그냥 가볼까요?

---

문제 요약

어피치는 너무 부자라서 보석을 사러가면 진열대의 특정 구간의 모든 보석을 싹쓸이합니다.

이 때 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매합니다.

가장 짧은 구간을 찾아 return해주세요.

 

예를 들어 아래 진열대는 4종류의 보석(RUBY, DIA, EMERALD, SAPPHIRE) 8개가 진열된 예시입니다.

진열대 번호	1	2	3	4	5	6	7	8
보석 이름	DIA	RUBY	RUBY	DIA	DIA	EMERALD	SAPPHIRE	DIA

진열대의 3번부터 7번까지 5개의 보석을 구매하면 모든 종류의 보석을 적어도 하나 이상씩 포함하게 됩니다.

 

테스트케이스

gems	result
["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]	[3, 7]
["AA", "AB", "AC", "AA", "AC"]	[1, 3]
["XYZ", "XYZ", "XYZ"]	[1, 1]
["ZZZ", "YYY", "NNNN", "YYY", "BBB"]	[1, 5]

 

접근 방법

이 문제의 핵심은 가장 짧은 구간을 찾는 것입니다.

예를 들면 테스트케이스 #1에서 마지막에 "RUBY"가 추가된다면 어떻게 될까요?

 

진열대 번호	1	2	3	4	5	6	7	8	9
보석 이름	DIA	RUBY	RUBY	DIA	DIA	EMERALD	SAPPHIRE	DIA	RUBY

 

정답은 [6, 9]를 return하게 됩니다.

set()을 이용해서 중복되지 않은 gems를 구하고,

set의 갯수에 맞는 배열에 index를 관리해주면 금방 찾을 것 같네요.

예를 들면, 이런 식입니다.

 

// 1.set으로 중복 제거.
set(gems) => [DIA, RUBY, EMERALD, SAPPHIRE];

// 2. set에 맞는 index 배열 생성
gemIndex => [0, 0, 0, 0];

//3. 반복문을 돌면서, 초기화
진열대 번호가 3일때 => gemIndex = [1, 3, 0, 0];
진열대 번호가 5일때 => gemIndex = [5, 3, 0, 0];
진열대 번호가 7일 때 => gemIndex = [5, 3, 6, 7];
진열대 번호가 9일 때 => gemIndex = [8, 9, 6, 7];

// 4. 최솟값과 최댓값을 return!  => [6, 9];

 

정답 코드

function solution(gems) {
    const uniqueGems = [...new Set(gems)];
    const gemMap = new Map();
    const gemIndexMap = new Map();
    let count = 0;
    const cursorArea = Array(uniqueGems.length).fill(0);
    let index = 1;
    let minDiff = Infinity;
    const result = [];
    
    uniqueGems.forEach((gem, i) => {
        gemMap.set(gem, 0);
        gemIndexMap.set(gem, i);
    });
    
    for (const gem of gems) {
        const gemValue = gemMap.get(gem);
        if (gemValue === 0) {
            gemMap.set(gem, gemValue + 1);
            count++;
        }
        cursorArea[gemIndexMap.get(gem)] = index;
        if (count === uniqueGems.length) {
            const min = Math.min(...cursorArea);
            minDiff = Math.min(minDiff, index - min);
            result.push([min, index]);
        }
        index++;
    }
    
    return result
        .sort((a, b) => a[0] - b[0])
        .filter(v => v[1] - v[0] === minDiff)[0];
}

 

팁 1. 반복문 안에서 index 찾을 땐 그냥 해시맵을 쓰자!

// 시간 복잡도: O(n)
cursorArea[cursurArea.indexof(gem)] = index;

// 시간 복잡도: O(1)
cursorArea[gemIndexMap.get(gem)] = index;

 

여러 번 공유한 팁이죠? 최대한 시간 복잡도를 줄여줍시다!

 

팁 2. min과 max의 함정

if (count === uniqueGems.length) {
    // speard 연산자 ...는 O(n)을 따릅니다.
    // min에만 사용해줍시다. max는 index와 같아요!
    const min = Math.min(...cursorArea);
    minDiff = Math.min(minDiff, index - min);
    result.push([min, index]);
}

 

Math.min과 Math.max는 정말 유용한 내장함수입니다.

다만, 스프레드 연산자가 문제에요. cursorArea는 uniqueGems를 따릅니다. gems의 최대가 200,000 개이므로,

최악의 경우엔 200,000개가 생길 수도 있겠네요.

 

이렇게 고의적으로 많은 데이터를 처리하도록 하는 경우에선 언제나 조심.. 또 조심해야합니다.

 

 

이건 진짜 쉽네요. 레벨 2 상위권 정도 될듯?

후딱후딱 해보자구요!

그럼 이만!