[백준/G4] 13144 List of Unique Numbers

https://www.acmicpc.net/problem/13144

시간복잡도

O(N)

풀이

1 2 3 1 2 일 때,

1(idx 0)까지 탐색 set (1): [1]
2(idx 1)까지 탐색 set (1,2): [2], [1, 2]
3(idx 2)까지 탐색 set (1,2,3) : [3], [2, 3], [1, 2, 3]
1(idx 3)까지 탐색 set (2,3,1) : [3, 1], [2, 3, 1], [1]
2(idx 4)까지 탐색 set (3,1,2) : [3, 1, 2], [1, 2], [2]

처음에는 이중 for문으로 set을 매번 생성하고 업데이트 하는 방법을 썼지만 메모리 초과가 자꾸 일어남
그래서 인덱스를 활용하는 방법으로 하나의 set을 두고 조건대로 업데이트 하는 방법으로 변경함

set.size : 해당 set의 길이 만큼 더해진다 (위 예시 참고)

최종코드

function getNum(N, arr) {
  let cnt = 0;
  let left = 0;
  let right = 0;
  let temp = new Set();

  while (right < N) {

	// 현재 숫자가 이미 Set에 있는지 확인해서 없을때까지 arr의 왼쪽값 삭제
    while (temp.has(arr[right])) {
			temp.delete(arr[left]);
      left += 1;
    }
    // 새롭게 더함
    temp.add(arr[right]);

	cnt = temp.size
    right += 1;

  }

  return cnt;
}

// 배열의 연속된 일부를 뽑았을 때 에서 다 다른수가 등장하는 경우의 수
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./13144.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = parseInt(input[0]);
const arr = input[1].split(" ").map(Number);

let answer = getNum(N, arr);

console.log(answer);

뭔가 억지로 조건을 찾는 과정에서 굉장히 헤맸는데
set을 쓰는 것도 메모리 초과가 났던 처음 풀이에서나 의미가 있었지
사실 배열의 연속된 일부를 뽑는다는 점에서 인덱스로 체크한다 이게 핵심인거 같다.

24140kb 236ms