[ 백준 ] 12933 오리 - JavaScript

문제

오리의 울음 소리는 "quack"이다. 올바른 오리의 울음 소리는 울음 소리를 한 번 또는 그 이상 연속해서 내는 것이다. 예를 들어, "quack", "quackquackquackquack", "quackquack"는 올바른 오리의 울음 소리이다.

 

영선이의 방에는 오리가 있는데, 문제를 너무 열심히 풀다가 몇 마리의 오리가 있는지 까먹었다.

 

갑자기 영선이의 방에 있는 오리가 울기 시작했고, 이 울음소리는 섞이기 시작했다. 영선이는 일단 울음소리를 녹음했고, 나중에 들어보면서 총 몇 마리의 오리가 있는지 구해보려고 한다.

 

녹음한 소리는 문자열로 나타낼 수 있는데, 한 문자는 한 오리가 낸 소리이다. 오리의 울음 소리는 연속될 필요는 없지만, 순서는 "quack"이어야 한다. "quqacukqauackck"과 같은 경우는 두 오리가 울었다고 볼 수 있다.

 

영선이가 녹음한 소리가 주어졌을 때, 영선이 방에 있을 수 있는 오리의 최소 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 영선이가 녹음한 소리가 주어진다. 소리의 길이는 5보다 크거나 같고, 2500보다 작거나 같은 자연수이고, 'q','u','a','c','k'로만 이루어져 있다.

출력

영선이 방에 있을 수 있는 오리의 최소 수를 구하는 프로그램을 작성하시오. 녹음한 소리가 올바르지 않은 경우에는 -1을 출력한다.

 

입출력 예시

입력 1

quqacukqauackck

 

출력 1

2

 

입력 2

kcauq

 

출력 2

-1

 

 

---

 

 

풀이

'use strict';
const fs = require('fs');

// 백준 제출 할 때 주석 제거
// const readFileSyncAddress = '/dev/stdin';

// VSC 테스트 할 때 주석 제거
const readFileSyncAddress = 'input.txt';

const input = fs.readFileSync(readFileSyncAddress).toString().trim().split('\n');

let stack = [];

function findAndDelete(search) {
  const index = stack.indexOf(search);

  if (index !== -1) {
    stack.splice(index, 1);
    return true;
  }

  return false;
}

function solution(input) {
  let result = 0;
  let isSound = true;

  input.forEach(sound => {
    switch (sound) {
      case 'q':
        if (!findAndDelete('k')) result += 1;
        break;

      case 'u':
        if (!findAndDelete('q')) {
          isSound = false;
          return;
        }
        break;

      case 'a':
        if (!findAndDelete('u')) {
          isSound = false;
          return;
        }
        break;

      case 'c':
        if (!findAndDelete('a')) {
          isSound = false;
          return;
        }
        break;

      case 'k':
        if (!findAndDelete('c')) {
          isSound = false;
          return;
        }
        break;
    }

    stack.push(sound);
  });

  if (!isSound || stack.some(sound => sound !== 'k')) return -1;
  return result;
}

console.log(solution([...input[0]]));

💡 핵심 아이디어

"quack"은 반드시 q → u → a → c → k의 순서를 따라야 하며, 이 순서가 어긋나거나 일부가 빠지면 올바른 울음으로 간주할 수 없다.

 

또한 "quackquack"처럼 여러 번 연속된 울음도 한 마리의 울음으로 처리해야 하므로, 단순히 "quack"의 개수를 세는 것이 아닌, 동시에 울고 있는 오리의 흐름을 정확히 추적하는 것이 중요하다.

 

이를 위해 각 문자가 진행 중인 울음소리의 어느 단계에 있는지를 배열로 관리했는데,

예를 들어, u가 들어오면 앞서 등장한 q를 찾아 제거하고, a가 들어오면 u를 제거하는 식으로, 각 문자가 기존 울음의 연속인지, 혹은 새로운 울음의 시작인지를 판단한다.

 

 

알고리즘 흐름

1. 문자열을 한 글자씩 순회하면서

2. 현재 글자가 "quack" 중 어느 위치에 해당하는지를 판단

3. 이전 단계의 글자가 존재한다면 해당 글자를 스택에서 제거 (findAndDelete)

4. 없다면 울음소리의 순서가 틀렸으므로 isSound = false

5. k까지 완성된 후에도 해당 k는 스택에 남겨두고, q가 다시 오면 재사용 -> 여러 번 연속된 울음도 한 마리의 울음으로 처리 가능

6. 모든 글자를 다 돈 후, 유효하지 않은 상태가 남아있다면 -1 반환