[프로그래머스] LV.3 보석 쇼핑 (JS)

KG·2021년 5월 4일

알고리즘

목록 보기

40/61

문제

개발자 출신으로 세계 최고의 갑부가 된 어피치는 스트레스를 받을 때면 이를 풀기 위해 오프라인 매장에 쇼핑을 하러 가곤 합니다.
어피치는 쇼핑을 할 때면 매장 진열대의 특정 범위의 물건들을 모두 싹쓸이 구매하는 습관이 있습니다.
어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 아래 목적을 달성하고 싶었습니다.
진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매

진열대 번호 순서대로 보석들의 이름이 저장된 배열 gems가 매개변수로 주어집니다. 이때 모든 보석을 하나 이상 포함하는 가장 짧은 구간을 찾아서 return 하도록 solution 함수를 완성해주세요.

가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며, 만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.

제한

gems 배열의 크기는 1 이상 100,000 이하입니다.
- gems 배열의 각 원소는 진열대에 나열된 보석을 나타냅니다.
- gems 배열에는 1번 진열대부터 진열대 번호 순서대로 보석이름이 차례대로 저장되어 있습니다.
- gems 배열의 각 원소는 길이가 1 이상 10 이하인 알파벳 대문자로만 구성된 문자열입니다.

입출력 예시

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]

풀이

2020 카카오 인턴십에서 출제된 문제이다. 정확성과 효율성을 동시에 테스트하기 때문에 시간복잡도를 고려해야 한다. 일반적인 접근 방법으로 이중 반복문을 통해 구간을 검사하는 방법을 떠올릴 수 있지만 이 경우 최대 10만 x 10만의 시간복잡도로 최대 O(100억)이 소요될 수 있기에 효율성을 통과하기 힘들 것이다. 따라서 O(N)의 시간복잡도로 풀 수 있는 방법으로 접근해보자.

매핑(Mapping)

문제에서 요구하는 것은 모든 보석을 포함하는 가장 짧은 구간이다. 따라서 진열된 보석은 여러 종류의 보석이 중첩되어 있을 수 있다. 가장 짧은 구간은 배치된 보석의 순서에 따라 보석이 중복될 수도 있고 하나씩만 담을 수도 있을 것 이다.

그러므로 주어진 gems 크기만큼 반복문을 돌면서 각 보석의 인덱스 값을 매핑해보자. 이때 각 보석의 모든 인덱스를 매핑할 필요는 없다. 만약 동일한 보석이 들어오는 경우엔 기존의 인덱스를 지우고, 현재 인덱스의 위치로 갱신하도록 하자.

// { 보석 : index } 의 형태로 저장하기 위해 Map 구조 사용
const shoppingBag = new Map();

for(let i = 0; i < gems.length; i++) {
  // 기존에 보석의 인덱스가 매핑되어 있다면 이를 지우고
  shoppingBag.delete(gems[i]);
  // 현재 index+1 값으로 다시 매핑
  // +1을 하는 이유는 리턴될 구간 좌표가 1부터 시작되기 때문
  shoppingBag.set(gems[i], i+1);
}

그렇다면 기존의 인덱스 정보는 버리고 새로운 인덱스 정보로 갱신하는 이유가 무엇인지 살펴보자.

최소 구간

문제에서 요구하는 것은 모든 보석을 포함하는 최소 구간이다. 가장 이상적인 경우는 각 보석을 한 개씩 중복없이 포함하는 구간이 될 것 이다.

이때 위의 매핑 과정에서 처럼, 기존에 매핑된 보석의 인덱스가 있었을 경우 제거하면서 새로 갱신하는 방식으로 모든 매핑을 진행한다면, 매핑값을 가지고 있는 변수의 크기는 모든 보석의 종류의 개수를 초과하지 않는다. 즉 보석의 종류가 4개라면, shoppingBag의 크기 역시 4를 초과할 수 없다.

또한 shoppingBag의 크기가 보석의 종류 개수와 동일하게 되는 경우가 바로 모든 보석을 포함하는 구간이 될 것 이다. 이때 각 보석에 인덱스의 위치를 매핑시켜 놓았기 때문에, 이 값을 이용하여 구간값을 구할 수 있을 것이다.

이때 우리는 기존 보석의 인덱스는 제거하면서 매핑을 진행했기 때문에, 매핑값에 가장 첫번째에 위치한 보석이 구간의 첫번째 자리를 차지하게 된다. 따라서 우리는 Map 자료구조를 사용해서 매핑을 진행했고, 해당 자료구조는 Iterative 하기 때문에 첫번째 원소의 값을 가져올 수 있다. 즉 최소 구간이 될 수 있는 위치는 매핑된 값 중 가장 첫번째 요소의 인덱스 - 현재 반복문의 인덱스 값 + 1이 될 것이다.

// 최소 구간을 담을 배열
const list = [];
// 보석 종류의 개수
const kinds = new Set(gems).size;

...

for(let i = 0; i < gems.length; i++) {
  ...
  if(kinds === shoppingBag.size) {
    // shoppingBag.values() => 매핑된 값들만 가져오고
    // .next() => 그 중에서 가장 첫 원소부터 접근
    // 이때 { value : ..., done : true or false } 를 리턴
    // 따라서 value로 접근하여 인덱스 값에 접근
    list.push([shoppingBag.values().next().value, i+1]);
  }
}

정답 리턴

list에 담기는 구간은 여러개가 될 수 있다. 왜냐하면 shoppingBag의 크기가 보석 종류의 개수와 동일하게 되는 순간 이후에도 탐색할 보석이 남아있다면 계속 동일한 크기를 유지하기 때문이다.

또한 처음에 탐색한 보석의 구간이 항상 최소 구간이라고 보장할 수 없다. 뒤에 탐색할 보석이 남아있기 때문에 최소 구간의 위치가 변경될 수 있기 때문이다.

따라서 위에서 구한 list를 문제의 조건에 맞게 정렬하여 최소 구간을 리턴하도록 해야한다. 다음의 조건들을 고려해주자.

각 구간의 차(diff)가 서로 동일한 경우
- 모두 동일한 간격의 최소 구간이다.
- 이때 문제 조건에 맞게 시작 진열대 번호가 가장 작은 구간을 리턴해야 한다
- 따라서 시작 인덱스 값을 기준으로 오름차순 정렬
각 구간의 차(diff)가 서로 다른 경우
- 최소 간격을 가진 구간을 맨 앞으로 배치하자
- 따라서 구간의 차를 기준으로 오름차순 정렬

list.sort((a, b) => a[1]-a[0] === b[1]-b[0] ? a[0]-b[0] : (a[1]-a[0]) - (b[1]-b[1]));

// 따라서 정답은 항상 list의 첫 번째 원소
return list[0];

전체 코드

정석적인 풀이로는 투 포인터를 사용하여 구간을 구하는 방법 역시 가능하다. 다만 해당 문제는 보석의 개수만 맞춰 구간을 구하면 되기에 위와 같은 방식으로 보다 좀 더 간단하게 풀이가 가능하다. 주석을 제외한 전체코드는 다음과 같다.

function solution (gems) {
  const list = [];
  const shoppingBag = new Map();
  const kinds = new Set(gems).size;
  
  for(let i = 0; i < gems.length; i++) {
    shoppingBag.delete(gems[i]);
    shoppingBag.set(gems[i], i+1);
    
    if(kinds === shoppingBag.size) {
      list.push([shoppingBag.values().next().value, i+1]);
    }
  }
  
  list.sort((a, b) => a[1]-a[0] === b[1]-b[0] ? a[0]-b[0] : (a[1]-a[0]) - (b[1]-b[0]));
  
  return list[0];
}