문자열 게임 2 (백준 20437)

문제

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

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

2
superaquatornado
2
abcdefghijklmnopqrstuvwxyz
5

예제 출력 1

4 8
-1

첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다.

두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다.

예제 입력 2

1
abaaaba
3

예제 출력 2

3 4

---

🚀문제 접근

먼저 3번 조건을 충족하지 않으면 4번 조건도 충족할 수 없다. 때문에 문자열을 이루는 어떤 문자들도 k번 이상 사용되지 않았다면 -1을 반환하도록 구현한다.

 

1. 문자열을 순회하면서 문자가 사용된 갯수를 map 자료형에 저장한다. 이 때 인덱스 정보를 저장한다.

2. 사용된 갯수가 k 미만인 key는 map에서 제거한다. map의 size가 0이 된다면 ret에 -1을 저장한다.

3. map에 저장된 인덱스 배열을 k개씩 묶어서 문자열의 길이를 구해 strArr에 저장한다. 정확히 k개를 가지고 있어야하므로 k개씩 묶어야한다.

4. strArr을 오름차순으로 정렬한다. 그리고 맨 처음 요소와 마지막 요소를 배열로 묶어 ret에 저장한다.

5. ret를 형식에 맞게 출력한다.

🛠코드

let input = require('fs').readFileSync(0).toString().trim().split('\n');
let n = Number(input[0]);
let tests = [];
while (n) {
  tests.push(input.splice(1, 2));
  n--;
}

tests = tests.map(([str, k]) => [str.trim(), Number(k)]);

function solution() {
  let ret = [];
  for (const [str, k] of tests) {
    let strArr = [];
    let map = new Map();
    [...str].forEach((c, idx) => {
      if (map.has(c)) map.set(c, [...map.get(c), idx]);
      else map.set(c, [idx]);
    });

    // 문자가 사용한 횟수가 k개 미만이면 map의 key를 지운다.
    for (const c of map.keys()) {
      if (map.get(c).length < k) map.delete(c);
    }
    if (map.size === 0) {
      ret.push(-1);
      continue;
    }

    // k개씩 묶어서 문자열의 길이를 구한다.
    for (const c of map.keys()) {
      let arr = map.get(c);
      for (let i = arr.length - 1; i >= k - 1; i--) {
        let j = i - k + 1;
        strArr.push(arr[i] - arr[j] + 1);
      }
    }

    // strArr 정렬 후에 0번째와 맨 마지막 요소를 ret에 넣어준다.
    strArr.sort((a, b) => a - b);
    ret.push([strArr[0], strArr[strArr.length - 1]]);
  }
  return ret.map((elem) => (Array.isArray(elem) ? elem.join(' ') : elem)).join('\n');
}

console.log(solution());