[JavaScript] 백준 12933. 오리

우선 자랑부터

2등이긴 하지만 거의 1등과 다름없는 성과가 있었다.

 

문제 설명

"quackquack" 과 같이 오리 녹음소리가 입력으로 주어질 때, 동시에 울고 있는 오리 수를 구하는 문제이다.

 

예를 들어, quackquack은 동시에 울고 있는 오리가 없기 때문에 1마리이다.

quqacukqauackck : 2마리
quackquackquackquackquackquackquackquackquackquack : 1마리
qquuaacckk : 2마리

 

 

오리 녹음 소리가 올바르지 않은 경우는 -1을 리턴한다.

1) 순서대로 아닌 경우 (예. kcauq)
2) 녹음이 끝난 후 오리가 울다가 끝난 경우 (예. qquack)

 

문제 풀이

동시에 울고 있는 오리 수를 어떻게 구할까?

 

기본적인 동작을 먼저 생각해보았다. 

예를 들어,

만약 q가 등장한 경우, cyingDucks를 증가시킨다. 만약 q가 한번 더 등장한 경우 cryingDucks는 2가 될 것이다.

그다음에 u가 등장한 경우, q가 있는 지 검사하여 q > 0이상이면, q-- 하고 u++ 한다.

그다음에 a가 등장한 경우 u가 있는 지 검사하여 u > 0이상이면, u--하고 a++한다.

그다음에 c가 등장한 경우 a가 있는 지 검사하여 a > 0 이면, a-- 하고 c++한다.

마지막으로 k가 등장한 경우, 더 이상 그 오리는 울지 않으므로 cryingDucks를 감소시킨다.

👉 이전 문자의 개수를 -1, 해당 문자의 개수를 +1

 

그럼 정답 변수인, 동시에 우는 오리 수(총 오리수)를 카운트하기 위해서는 어떻게 할까?

"동시에" -> 이런 키워드는 보통 Math.max(최댓값)을 구하면 해결할 수 있다.

예를 들어,

오리가 2마리가 동시에 울다가, 오리가 추가되면 3마리가 울다가, 한 오리가 다울었다면 2마리가 동시에 울게 된다.

즉 cyingDucks= 2 -> 3 -> 2로 변할 때, 총 오리수는 3이다. 따라서 cyringDucks의 최댓값이 총 오리수가 된다.

 

엣지케이스인, 올바른 녹음 소리가 아닌 경우는 

"👉 이전 문자의 개수를 -1, 해당 문자의 개수를 +1 // 직전에 설명한 기본 동작"

에서 이전 문자의 개수가 0이라면, 올바른 녹음 소리가 아닌 것이다. -> 순서대로가 아닌 경우(예. qaukc)

 

또한 엣지케이스 2, 녹음이 끝난 후에도 오리 울음이 끝나지 않은 경우는

q, u, a, c 의 개수가 0이 아닌 것이 있는 경우이다.

 

전체 코드

const fs = require("fs");
const input = fs.readFileSync("./example.txt", "utf8").trim().split("\n");

const str = input[0].split("");
const quack = "quack";

let isValid = true; // 유효한 오리 녹음인지

let ducks = 0; // 정답 변수 (동시에 우는 오리 수 카운트)
const counts = [0, 0, 0, 0, 0]; // q, u, a, c, k의 개수
let cryingDucks = 0; // 현재 울고있는 오리 수

for (const c of str) {
  const idx = quack.indexOf(c);

  // q인 경우
  if (idx === 0) {
    counts[0]++;
    cryingDucks++;
    ducks = Math.max(ducks, cryingDucks); // 동시에 우는 오리 수 업데이트
  } else {
    // 이전 문자가 없는 경우
    if (counts[idx - 1] === 0) {
      isValid = false;
      break;
    }

    counts[idx - 1]--;
    counts[idx]++;

    // k인 경우
    if (idx === 4) {
      cryingDucks--;
    }
  }
}

// 모든 quack이 완성되지 않은 경우
if (counts.slice(0, -1).some((count) => count > 0)) isValid = false;
console.log(isValid ? ducks : -1);

 

요약

cryingDucks 처럼 우는 오리수의 상태를 추적하고, 최댓값을 구하여 ducks에 저장하는 방식으로 문제를 해결할 수 있었다.

동시 접속자 수, 실시간 트래픽, 병렬 프로세스 등 다양한 "동시성" 관련 문제에서 유용하게 적용될 수 있을것같다.

 

 

문제

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