[백준] 문자열 게임 2 - JavaScript 풀이

💙 문제 설명

 

작년에 이어 새로운 문자열 게임이 있다. 게임의 진행 방식은 아래와 같다.

1. 알파벳 소문자로 이루어진 문자열 W가 주어진다.
2. 양의 정수 K가 주어진다.
3. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.
4. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.

위와 같은 방식으로 게임을 T회 진행한다.

 

💛 입력

 

문자열 게임의 수 T가 주어진다. (1 ≤ T ≤ 100)

다음 줄부터 2개의 줄 동안 문자열 W와 정수 K가 주어진다. (1 ≤ K ≤ |W| ≤ 10,000) 

 

💚 출력

 

T개의 줄 동안 문자열 게임의 3번과 4번에서 구한 연속 문자열의 길이를 공백을 사이에 두고 출력한다.

만약 만족하는 연속 문자열이 없을 시 -1을 출력한다.

 

🚫 제한사항

• 1 ≤ T ≤ 100
• 1 ≤ K ≤ |W| ≤ 10,000
• 시간제한 : 1 s

---

❤️ 문제 풀이 방법

 

여러차례의 시도 끝에 맞았다..

 

삽질 1 : 처음에는 문자열 제한 사항을 잘 못 보고 단순 반복문으로 해결하려다가 절대 안된다는 것을 깨달았다.

삽질 2 : 다른 분들의 풀이를 참고해서 문자열 index를 저장하면 된다는 것을 알게 됐는데, Object에 저장할 때 아래처럼 적었다가 계속 에러가 났다.

strObj[char] = strObj[char] ? strObj[char].push(j) : [j];

 

왜 이렇게 적었는지 지나고 나니까 이해가 안된다 ㅋㅋㅋ 암튼 이거 때문에 오래 걸렸다.

 

1️⃣ 인덱스 저장 후 슬라이딩 윈도우

 

우선 문자열 길이가 최대 1만이니까 반복문으로 두번이상 돌면 안된다는 점에 주의해야 한다. => 직접 돌면서 비교 불가 !!!

그러면 어떻게 같은 문자열들을 확인할 수 있을까 ??

 

객체 타입을 활용해서 문자열마다 등장하는 인덱스를 저장해둔다. 이렇게 하면 한번의 반복문 사용으로 문자들의 위치를 모두 알 수 있다.

 

이 객체를 활용해서, 횟수 k번 등장 기준 가장 작거나 큰 길이를 확인하면 된다.

 

const fs = require("fs");
const input = fs.readFileSync("test.txt", "utf-8").trim().split("\n");

function solution() {
  const t = Number(input[0]);
  const rest = input.slice(1);
  const strArr = rest.filter((_, idx) => idx % 2 === 0).map((v) => v.trim());
  const k = rest.filter((_, idx) => idx % 2 === 1).map(Number);

  for (let i = 0; i < strArr.length; i++) {
    let strObj = {};
    for (let j = 0; j < strArr[i].length; j++) {
      let char = strArr[i][j];
      if (!strObj[char]) {
        strObj[char] = [];
      }
      strObj[char].push(j);
    }

    let minLen = Number.MAX_SAFE_INTEGER;
    let maxLen = 0;

    for (let char in strObj) {
      if (strObj[char].length < k[i]) continue;
      for (let d = 0; d < strObj[char].length - k[i] + 1; d++) {
        let diff = strObj[char][d + k[i] - 1] - strObj[char][d] + 1;

        if (minLen > diff) minLen = diff;
        if (maxLen < diff) maxLen = diff;
      }
    }

    console.log(maxLen === 0 ? "-1" : minLen + " " + maxLen + "");
  }
}

solution();