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

문제

녹음한 소리로부터 존재할 수 있는 최소 오리의 수를 찾습니다.

구현

오리의 울음 소리 'quack'의 길이는 5입니다. 따라서 녹음한 소리가 5의 배수가 아니라면 올바르지 않은 소리라는 것을 의미합니다.
이 부분 먼저 빠르게 exit 해줍시다.

if (sound.length % 5 !== 0) {
  console.log(-1);
  return;
}

이후 과정을 투포인터로 구현하면 97%에서 시간초과를 맞습니다ㅋ
입력의 최대 길이가 2500, 최대 500마리를 찾는다고 가정하면.. 아무튼 포기하고 다른 방법을 찾았습니다.

아래 코드는 오리의 울음소리(이하 sound)를 돌면서 'q', 'u', 'a', 'c', 'k'을 적절한 배열에 추가하는 방식입니다.

예제1을 예로 들면

quqacukqauackck

[
  [
    'q', 'u', 'a', 'c',
    'k', 'q', 'u', 'a',
    'c', 'k'
  ],
  [ 'q', 'u', 'a', 'c', 'k' ]
]

두 마리네요.
그러나 다음 예제처럼 어딘가 잘린 quack이 들어있을 수도 있습니다

quackqauckquack

[
  [
    'q', 'u', 'a', 'c',
    'k', 'q', 'u', 'a',
    'c', 'k'
  ],
  [ 'a', 'u' ],
  [ 'c' ],
  [ 'k' ],
  [ 'q' ]
]

따라서 마지막으로 duck[]을 돌면서 result를 세다가
잘린 배열이 나오면 -1를 출력합니다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const sound = require('fs').readFileSync(filePath).toString().trim();
let result = 0;

const quack = ['q', 'u', 'a', 'c', 'k'];
const duck = [[]];

if (sound.length % quack.length !== 0) {
  console.log(-1);
  return;
}

for (let i = 0; i < sound.length; i++) {
  let flag = false;
  for (let j = 0; j < duck.length; j++) {
    if (quack[duck[j].length % quack.length] === sound[i]) {
      duck[j].push(sound[i]);
      flag = true;
      break;
    }
  }
  if (!flag) {
    duck.push([sound[i]]);
  }
}

for (let i = 0; i < duck.length; i++) {
  if (duck[i].length % 5 === 0) {
    result += 1;
  } else {
    result = -1;
    break;
  }
}

console.log(result);