[클라우딩 어플리케이션 엔지니어링 TIL] - DAY 21

투포인터

일차원 배열에 두 개의 포인터를 두고 조작하는 알고리즘, 연속적인 구간 계산을 할때 많이 사용

투포인터 알고리즘 문제 풀기

보석 쇼핑: https://school.programmers.co.kr/learn/courses/30/lessons/67258

 

보석 쇼핑 문제는 모든 보석을 살 수 있는 가장 짧은 진열대 구간을 찾아서 return 하는 문제이기에 일차원 구간에 대한 탐색을 투포인터 알고리즘으로 접근해 풀 수 있다.

 

진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 구간을 찾는 것이 목적이기 때문에 다음과 같이 진행한다.

1. start, end 인덱스를 첫번째 인덱스에 위치시킨다.
2. 두개의 포인터가 가르키는 현재 구간에서 모든 보석을 구매할 수 없다면 end 인덱스를 증가
3. 현재 구간에서 모든 보석을 구매할 수 있다면 구간을 기록하고, start 인덱스 증가

pointer	start,end
index	0	1	2	3	4	5	6	7
gems	DIA	RUBY	RUBY	DIA	DIA	EMERALD	SAPPHIRE	DIA

현재 DIA 1개 밖에 구매할 수 있으므로 end 포인터 증가

pointer	start	end
index	0	1	2	3	4	5	6	7
gems	DIA	RUBY	RUBY	DIA	DIA	EMERALD	SAPPHIRE	DIA

end를 증가시켜도 모든 보석을 구매할 수 없으므로 계속 end 증가

pointer	start						end
index	0	1	2	3	4	5	6	7
gems	DIA	RUBY	RUBY	DIA	DIA	EMERALD	SAPPHIRE	DIA

end를 7까지 증가시켰을 때 DIA 3개, RUBY 2개, EMERALD 1개, SAPPHIRE 1개로

모든 종류를 구매할 수 있음. 따라서 현재 구간 (0, 6) 저장 후 start 포인터 증가

pointer		start					end
index	0	1	2	3	4	5	6	7
gems	DIA	RUBY	RUBY	DIA	DIA	EMERALD	SAPPHIRE	DIA

DIA가 1개 줄어 구매할 수 있는 보석은 DIA: 2, RUBY: 2, EMERALD: 1, SAPPHIRE: 1

아직 모든 종류의 보석을 구매할 수 있으므로 구간 (1, 6) 갱신 후 start 증가

pointer			start				end
index	0	1	2	3	4	5	6	7
gems	DIA	RUBY	RUBY	DIA	DIA	EMERALD	SAPPHIRE	DIA

RUBY가 1개 줄어서 구매할 수 있는 보석은 DIA: 2, RUBY: 1, EMERALD: 1, SAPPHIRE: 1

아직 모든 종류의 보석을 구매할 수 있으므로 구간 (2, 6) 갱신 후 start 증가

pointer				start			end
index	0	1	2	3	4	5	6	7
gems	DIA	RUBY	RUBY	DIA	DIA	EMERALD	SAPPHIRE	DIA

RUBY가 1개 더 줄어서 구매할 수 있는 보석은 DIA: 2, RUBY: 0, EMERALD: 1, SAPPHIRE: 1

모든 종류의 보석을 구매할 수 없으므로 end 증가

 

이런식으로 투포인터 알고리즘으로 구간을 탐색하면서 문제를 풀 수 있다.

참고로 문제의 구간은 1부터 시작하므로 구간을 반환할 때 인덱스 + 1을 해야한다.

 

풀이 코드

 

function solution(gems) {
  let start = 0;
  let end = 0;
  let answer = [start + 1, gems.length]; // 가장 긴 길이로 초기화

  const gemKinds = new Set(gems).size; // 보석의 종류
  const collect = new Map(); // 보석을 담아둘 변수
  collect.set(gems[0], 1); // 첫번째 보석을 담고 개수 하나 증가

  while (start < gems.length && end < gems.length) { // 두 포인터가 끝에 도달한다면 종료
    if (collect.size === gemKinds) { // 모든 보석 종류를 구매할 수 있다면
      if (end - start < answer[1] - answer[0]) { // 저장된 구간보다 짧을 때
        answer = [start + 1, end + 1]; // 구간 갱신
      }

      collect.set(gems[start], collect.get(gems[start]) - 1); // start에 위치한 보석 한개 빼기
      if (collect.get(gems[start]) === 0) { // 보석의 개수가 0개면
        collect.delete(gems[start]); // 담아둔 보석 공간 제거
      }
      start += 1; // start 포인터 증가
    } else { // 모든 보석을 구매할 수 없다면
      end += 1; // end 포인터 증가
      collect.set(gems[end], 1 + (collect.get(gems[end]) || 0)); // 보석을 추가한다.
    }
  }
  return answer;
}