[백준] 꿀 아르바이트, 블로그, DNA 비밀번호 (javascript)

 

 

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

12847번: 꿀 아르바이트

 

 

🤔 해결방법

1. 초기값 = 처음부터 m개의 합
2. 슬라이딩 윈도우로 앞에 하나 빼고 뒤에 하나 더하기
3. 그 값을 profit에 push
4. 2,3번 반복
5. profit에서 가장 큰 값 출력

 

 

🔑 풀이

const input = require("fs")
    // .readFileSync("/dev/stdin")
    .readFileSync(__dirname + "/input.txt")
    .toString()
    .trim()
    .split("\n");

  const [n, m] = input[0].split(" ").map(Number);
  const t = input[1].split(" ").map(Number); // 일급
  let profit = []; // 얻을 수 있는 이익
  let value = 0;

  // 초기값
  for (let i = 0; i < m; i++) {
    value += t[i];
  }
  profit.push(value);

  for (let i = 0; i < n; i++) {
    if (i + m < n) {
      value -= t[i]; // 앞의 수 빼기
      value += t[i + m]; // 뒤의 수 더하기
      profit.push(value);
    }
  }

  console.log(Math.max(...profit));

 

슬라이딩 윈도우를 처음 알게 되었다.

슬라이딩 윈도우는 투포인터와 개념이 비슷한데, 투포인터는 구간 넓이가 유동적으로 변하지만 슬라이딩 윈도우는 구간의 넓이가 항상 고정된다는 차이가 있다.

따라서 for문에서 맨 앞의 수는 빼고 뒤의 수는 하나 더해주면서 윈도우 크기를 유지하며 풀어야 한다.

 

출처:https://velog.io/@hysong/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0-vs-%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9-%EC%9C%88%EB%8F%84%EC%9A%B0

 

 

 

 

 

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

21921번: 블로그

 

 

🤔 해결방법

1. 초기값 = 처음부터 x개의 합
2. 슬라이딩 윈도우로 앞에 하나 빼고 뒤에 하나 더하기
3. 그 값을 visitNumbers에 push
4. 2,3번 반복
5-1. visitNumbers에서 가장 큰 값이 0이면 SAD
5-2. 가장 큰 값이 0이 아니면 최대값과 개수 출력

 

 

🔑 풀이

const input = require("fs")
    // .readFileSync("/dev/stdin")
    .readFileSync(__dirname + "/input.txt")
    .toString()
    .trim()
    .split("\n");

  const [n, x] = input[0].split(" ").map(Number);
  const visit = input[1].split(" ").map(Number); // 방문자 수
  let visitNumbers = []; // x일 동안의 방문자 수 합
  let value = 0;

  // 초기값
  for (let i = 0; i < x; i++) {
    value += visit[i];
  }
  visitNumbers.push(value);

  for (let i = 0; i < n; i++) {
    if (i + x < n) {
      value -= visit[i]; // 앞의 수 빼기
      value += visit[i + x]; // 뒤의 수 더하기
      visitNumbers.push(value);
    }
  }

  let max = Math.max(...visitNumbers); // 최대값
  if (max === 0) {
    console.log("SAD");
  } else {
    let count = visitNumbers.reduce((cnt, e) => cnt + (max === e), 0); //최대값 개수
    console.log(max + "\n" + count);
  }

 

꿀 아르바이트 문제와 거의 흡사한 방식이라 슬라이딩 윈도우를 사용하여 쉽게 풀 수 있었다.

 

 

 

 

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

12891번: DNA 비밀번호

 

🤔 해결방법

1. DNA 문자열 (A, C, G, T)과 각 DNA 문자열의 개수를 객체로 만들기
2. 각 DNA 문자열의 출현 횟수를 기록할 strCount 객체 초기화
3. 첫 번째 슬라이딩 윈도우를 초기화하고, 해당 윈도우 내에서 각 DNA 문자열이 몇 번 출현하는지 카운트
4. 만약 strCount 객체 내의 각 DNA 문자열의 출현 횟수가 dna 객체 내의 각 DNA 문자열의 개수보다 많거나 같다면, 답의 개수를 하나 증가
5. 슬라이딩 윈도우를 오른쪽으로 한 칸씩 이동시키며 위의 과정을 반복

이때, 윈도우에서 빠지는 요소의 카운트를 감소시키고, 윈도우에 들어오는 요소의 카운트를 증가시킵니다.
6. 답의 개수 출력

 

 

🔑 풀이

const input = require("fs")
    // .readFileSync("/dev/stdin")
    .readFileSync(__dirname + "/input.txt")
    .toString()
    .trim()
    .split("\n");

  const str = input[1];
  const [strLength, subStrLength] = input[0].split(" ").map(Number);
  const dnaStr = ["A", "C", "G", "T"];
  const dnaStrNum = input[2].split(" ").map(Number);
  const dna = dnaStr.reduce((obj, key, index) => {
    obj[key] = dnaStrNum[index];
    return obj;
  }, {});
  let answer = 0;

  let strCount = { A: 0, C: 0, G: 0, T: 0 }; // 부분 문자열 내에 각 DNA 문자열이 몇 번 나타나는지

  for (let i = 0; i < subStrLength; i++) {
    // 첫 번째 윈도우 초기화
    if (str[i] in dna) strCount[str[i]]++;
  }
  // strCount가 dna의 각 요소보다 크거나 같다면 answer +1
  if (Object.keys(dna).every((key) => dna[key] <= strCount[key])) answer++;

  for (let i = subStrLength; i < strLength; i++) {
    // 슬라이딩 윈도우
    strCount[str[i - subStrLength]]--; // 윈도우에서 빠지는 요소 감소
    strCount[str[i]]++; // 윈도우에 들어오는 요소 증가

    if (Object.keys(dna).every((key) => dna[key] <= strCount[key])) answer++;
  }

  console.log(answer);

  // 시간초과
  // function solution(str, dna) {
  //   for (let i = 0; i < str.length - subStrLength; i++) {
  //     let subStr = str.slice(i, i + Number(subStrLength)); // 부분문자열

  //     // 각 문자 개수 세기
  //     let strCount = { A: 0, C: 0, G: 0, T: 0 };
  //     for (let s of subStr) {
  //       if (s in dna) strCount[s]++;
  //     }

  //     // 조건 만족하면 answer++
  //     if (Object.keys(dna).every((key) => dna[key] <= strCount[key])) {
  //       answer++;
  //     }
  //   }
  //   return answer;
  // }

  // console.log(solution(str, dna));

 

처음에 슬라이딩 윈도우를 모를 때 그냥 이중for문으로 풀었던 것은 시간초과가 떴었다.

대충 이 3문제 정도 푸니 슬라이딩 윈도우 풀이 방법 감이 잡힌 것 같다!!