투포인터 알고리즘(two pointers)

슬라이딩 윈도우 알고리즘(Sliding Window)

고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘을 말한다.
교집합의 정보를 공유하고, 차이가 나는 양쪽 끝 원소만 갱신한다.
배열이나 리스트의 요소의 일정 범위의 값을 비교할 때 사용하면 유용하다.

투포인터 알고리즘(two pointers)

1차원 배열에서 어떤 특정 조건을 만족하는 연속 구간 구할 때,
각자 다른 원소를 가리키는 2개의 포인터로 구간의 길이를 가변적으로 조작하며 조건을 충족하는 구간을 찾는 알고리즘이다.

투포인터 알고리즘 문제의 유형

• 포인터 2개가 같은 방향으로 진행하는것
• 포인터 2개가 양끝에서 시작하여 반대로 진행하는 것
• 포인터 하나는 한쪽 방향으로만 진행하고, 다른 포인터는 양쪽으로 이동하는 것

투 포인트 알고리즘은 구간의 넓이가 조건에 따라 유동적으로 변하며,
슬라이딩 (윈도우) 알고리즘은 항상 구간의 넓이가 고정되어 있다는 차이점이 있다

투 포인터 알고리즘 문제

(라고 해서 풀었는데 맞는 지 모르겠다😓)

프로그래머스 [2020 카카오 인턴십] 보석 쇼핑

• 두 포인터 모두 오른쪽으로 이동하는 유형

진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서
가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 해야한다.
만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.

제한사항

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

입출력 예

let answer = solution([ "DIA", "RUBY", "RUBY", "DIA", "DIA" "EMERALD", "SAPPHIRE", "DIA" ]);
console.log(answer); // [3, 7]
answer = solution(["AA", "AB", "AC", "AA", "AC"]);
console.log(answer); // [1, 3]
answer = solution(["XYZ", "XYZ", "XYZ"]);
console.log(answer); // [1, 1]
answer = solution(["ZZZ", "YYY", "NNNN", "ZZZ", "BBB"]);
console.log(answer); // [1, 5]

풀이를 위해 알아야하는 Map의 메소드

Map 은 등록된 순서를 기억해서 순서대로 순회하는 이터러블 객체이다.

let newMap = new Map([["AA", 0], ["AB", 1]]);
console.log(newMap); // Map(2) { 'AA' => 0, 'AB' => 1 }
console.log(newMap.values()); // [Map Iterator] { 0, 1 }

// 이터레이터 객체에는 순회 결과 객체를 반환하는 next( ) 메서드가 있다.
// 순회 결과 객체에는 다음 순회 값이 있으면 그 값을 보유하는 value 프로퍼티가 있다. {value: 이터레이터 값, done: false }
console.log(newMap.values().next()); // { value: 0, done: false }
console.log(newMap.values().next().value); // 0;


// next() 메서드를 계속 호출하면 다음과 같다.
let valuesIterator = newMap.values();

let 첫번째_호출 = valuesIterator.next();
let 두번째_호출 = valuesIterator.next();
console.log(두번째_호출); // { value: 1, done: false }
let 세번째_호출 = valuesIterator.next();
console.log(세번째_호출); // { value: undefined, done: true }

풀이

1. 모든 보석 종류(중복 없이)의 개수를 구한다.
2. 보석 {key = 보석 이름, value = 보석의 인덱스} 를 Map으로 저장한다.
3. 동일한 보석이 있는 경우 삭제하고 다시 등록하여 보석 Map의 보석 순서를 문제의 배열의 인덱스 순서와 동일하게 유지
4. 처음 구한 중복 없는 보석 종류의 size와 보석 Map 요소의 size가 같다면,
   Map의 value인 [시작 인덱스 번호 + 1, 끝 인덱스 번호 + 1]를
   새로운 배열 gemLengths의 배열의 요소로 넣는다.
5. 이렇게 모인 gemLengths 요소들을 길이가 짧은 순서대로, 길이가 같은 건 시작 진열대 번호가 작은 순서대로 정렬
6. 정렬된 gemLengths 배열의 첫 번째 요소 리턴 (길이가 가장 짧고, 시작 번호가 가장 작은 구간)
   

function solution(gems) {
  let gemsSize = new Set(gems).size;
  const gemsMap = new Map();
  const gemLengths = [];
  gems.forEach((el, i) => {
    gemsMap.delete(el);
    gemsMap.set(el, i);
    if (gemsMap.size === gemsSize) {
      gemLengths.push([gemsMap.values().next().value + 1, i + 1]);
    }
  });
  gemLengths.sort((a, b) => {
    // 배열의 길이 같다면 시작하는 인덱스가 작은 게 앞에 오도록
    if ((a[1] - a[0]) === (b[1] - b[0])) {
      return a[0] - b[0];
    }
    // 길이가 짧은 배열이 앞에 오도록
    return (a[1] - a[0]) - (b[1] - b[0]);
  });
  return gemLengths[0];
}

참고: 슬라이딩 윈도우 알고리즘(Sliding Window) (feat. 투 포인트)
Sliding Window
코드2 (카카오 인턴쉽 2020 : 보석 쇼핑)