[JavaScript/node.js] 백준 20437번 - 문자열 게임 2

[문제]

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

20437번: 문자열 게임 2

 

[풀이]

어떤 문자를 a라고 한다면 정확히 K개를 포함하며, 첫 번째와 마지막 글자가 모두 a인 문자열의 길이를 구해야 합니다.

따라서 for문으로 문자열W을 순회하며 K개 이상 포함된 문자를 찾아야합니다.

 

1. Map을 활용하여 key = 문자 , value = [문자의 개수, index1, index2, ... ] 의 형태로 저장해 주었습니다.

 

2. 완성된 Map을 순회하며 value의 0번째 값, 즉 문자의 개수가 K이상인 key값에 대해서만 문자열의 길이를 구합니다.

 

3. value의 1번째값~마지막값 까지 문자의 위치들이 오름차순으로 정렬되어 있기 때문에 K개씩 묶어서 길이를 구합니다.

 

4. 구해진 문자열의 길이들을 words배열에 넣고, sort연산을 통해 정렬해 가장 짧은 값과 가장 긴 값을 출력합니다.
만약, words의 배열이 비어있다면 만들수 있는 문자열이 없기 때문에 -1을 출력합니다.

 

 

1. 위와 같은 방법으로 예제 1번의 T1을 구해보면 Map은 다음과 같습니다.

문자열 = superaquatornado
K = 2

Map(12) {
  's' => [ 1, 0 ],
  'u' => [ 2, 1, 7 ],
  'p' => [ 1, 2 ],
  'e' => [ 1, 3 ],
  'r' => [ 2, 4, 11 ],
  'a' => [ 3, 5, 8, 13 ],
  'q' => [ 1, 6 ],
  't' => [ 1, 9 ],
  'o' => [ 2, 10, 15 ],
  'n' => [ 1, 12 ],
  'd' => [ 1, 14 ]
}

 

2. Map을 순회하며 K개 이상 문자를 가지고 있는 값을 뽑아내면 다음과 같습니다.

 

Map(12) {
  'u' => [ 2, 1, 7 ]
  'r' => [ 2, 4, 11 ],
  'a' => [ 3, 5, 8, 13 ]
  'o' => [ 2, 10, 15 ]
}

 

3. K개를 가진 문자열의 길이를 value배열의 1번째 이후 index들을 K 간격으로 빼서 구합니다.

예를 들어, 'u'는 [1, 7] 에 위치하므로 길이는 7 - 1 + 1 = 6입니다.

 

4. 구해진 문자열의 길이를 저장한 배열 words을 오름차순으로 정렬한 결과는 다음과 같습니다.

[ 4, 6, 6, 7, 8 ]

 

따라서 최소값 4, 최대값 8을 출력하면 됩니다.

 

[코드]

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split('\n');

const T = Number.parseInt(input[0]);

const findWord = (W, K) => {
    const map = new Map();
    const words = [];

    for(let i=0;i<W.length;i++) {
        if(!map.has(W[i])) {
            map.set(W[i], [1, i]);
        } else {
            const arr = [...map.get(W[i]), i];
            arr[0] += 1;
            map.set(W[i], arr);
        }
    }

    map.forEach((v, k) => {
        if(v[0] >= K) {
            for(i=v.length-1;i>=K;i--) {
                words.push(v[i] - v[i-K+1] + 1);
            }
        }
    });
    if(words.length === 0) {
        console.log(-1);
    } else {
        words.sort((a,b) => a-b);
        console.log(words[0] + " " + words[words.length-1]);
    }
}

for(let i=1;i<=T*2;i+=2) {
    const W = input[i];
    const K = Number.parseInt(input[i+1]);
    findWord(W,K);
}