[백준][슬라이딩 윈도우] 1593 문자해독 NodeJs 구현

     

목차

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

문제

 

문제 구현 방향

슬라이딩 윈도우는 너무 오랜만이라 많이 헤멨다...

나는 문자를 idx로 쓰기 위해 map을 통해 풀었다. 

 

 

문제 풀이

1. 단어 W 길이만큼 map에 키, 값으로 설정해 준다. ex) c 1 A 1 d 1 a 1

2. 단어 W 길이만큼 S에서 인덱스 0부터 탐색한 뒤 값이 존재하면  map 값을 감소 시킨다. AbrA -> c 1 A -1 d 1 a 1

3. 슬라이딩 윈도우를 통해 빠지는 문자는 ++value를 해주고 추가하는 문자는 --value 해준다.

4. 모든 value가 0보다 작거나 같으면 ans++ 해준다.

 

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let A = input[1].trim();
let B = input[2].trim();
let Amap = new Map();

//order에 따라 반환 or 추가 조작
function addToMap(a, order) {
  if (Amap.has(a)) {
    if (order) Amap.set(a, Amap.get(a) - 1);
    else Amap.set(a,Amap.get(a) + 1);
  }
}

// 모든 value가 0보다 작거나 같으면 조건 만족
function isValid() {
  for (let i of Amap.values()) {
    if (i > 0) return false;
  }
  return true;
}

//초기 map 설정
for (let i = 0; i < A.length; i++) {
  if (!Amap.has(A[i])) {
    Amap.set(A[i], 1);
  } else {
    Amap.set(A[i], Amap.get(A[i]) + 1);
  }
}

let ans = 0;

//0 부터 길이까지 우선 탐색
for (let i = 0; i < A.length; i++) {
  addToMap(B[i], true);
}


if (isValid()) ans++;

//슬라이딩 윈도우를 통한 나머지 탐색
for (let i = A.length; i <B.length; i++) {

  addToMap(B[i], true);
  addToMap(B[i - A.length], false);
  if(isValid())ans++;
}

console.log(ans);