[백준/js]12933. 오리

눈사람·2024년 7월 18일

코테 서바이벌 스터디에서 내가 풀어보자고 고른 구현 문제인데, 귀엽고 만만해 보여서 골랐으나, 40분이 지나도록 문제를 잘못 이해하고 있던 문제이다...^^

12933. 오리🦆

🥈실버2

분류: 구현

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	5480	1804	1372	33.480%

문제

오리의 울음 소리는 "quack"이다. 올바른 오리의 울음 소리는 울음 소리를 한 번 또는 그 이상 연속해서 내는 것이다. 예를 들어, "quack", "quackquackquackquack", "quackquack"는 올바른 오리의 울음 소리이다.
영선이의 방에는 오리가 있는데, 문제를 너무 열심히 풀다가 몇 마리의 오리가 있는지 까먹었다.
갑자기 영선이의 방에 있는 오리가 울기 시작했고, 이 울음소리는 섞이기 시작했다. 영선이는 일단 울음소리를 녹음했고, 나중에 들어보면서 총 몇 마리의 오리가 있는지 구해보려고 한다.
녹음한 소리는 문자열로 나타낼 수 있는데, 한 문자는 한 오리가 낸 소리이다. 오리의 울음 소리는 연속될 필요는 없지만, 순서는 "quack"이어야 한다. "quqacukqauackck"과 같은 경우는 두 오리가 울었다고 볼 수 있다.
영선이가 녹음한 소리가 주어졌을 때, 영선이 방에 있을 수 있는 오리의 최소 개수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

문제 이해

❌ 처음에 문제를 잘못 이해해서 'quackqquuaacckk이면 3 아닌가?' 하고 있었다. 3 아니고 2이다. 나는 오리가 각각 한 번씩만 울고, 오리가 총 몇 마리인지 구하는 문제인 줄 알았다. 하지만 알고보니 최소 오리 수를 구하는 문제였다.

✅ 오리 한 마리는 여러번 꽥꽥(quackquack) 거릴 수 있다. 그래서 quackquack이면 오리는 최소 한 마리이다. 하지만 한 마리가 한 번에 여러번 꽦괙(qquuaacckk) 수는 없다. 그래서 qquuaacckk이면 오리는 최소 두 마리이다. 한 마리가 quack거리는 동안 몇 마리나 quack거리는지 보고 동시에 우는 오리 수의 최댓값을 찾으면 된다.
그렇다면 q[i]와 k[i] 사이에 있는 q의 개수+1 중 제일 큰 수를 구한다면 최소 그 이상의 오리가 있을 것이다.

문제 풀이

먼저 잘못 녹음된 경우를 빠르게 걸러주기 위해 문자열의 길이가 5의 배수가 아닌 경우부터 제외하고 시작한다. (5의 배수가 아니라면 녹음 자체가 잘못된 것이지만, 사실 제외하지 않아도 정답 처리되는 것 같다.)

그럼 문자열이 5의 배수인 녹음본이 남는다.
q, u, a, c, k이라는 배열을 만들고 문자열에 대해 q, u, a, c, k의 index를 찾아 각각의 배열에 저장한다.
예시) 입력: quackquack
q = [0, 5]
u = [1, 6]
a = [2, 7]
c = [3, 8]
k = [4, 9]
내가 찾고자하는 요소와 일치하는 배열의 모든 요소의 index를 출력해주는 함수가 내장되어 있으면 좋겠지만, 없으니까 아래와 같이 함수를 정의해줘야한다.

function findString(arr, value) {
    let stringIndex = [];
    arr.forEach((element, index) => {
        if(element === value)
            stringIndex.push(index);
        }
    )
    return stringIndex;
}

forEach 함수를 사용해서 배열의 요소가 찾고자하는 값과 일치하면 인덱스 배열에 push하고, 마지막에 인덱스 배열을 반환하는 함수이다.

나는 이런식으로 풀었지만 체크한 문자는 q, u, a, c, k를 제외한 다른 문자(b, d 등)로 치환하는 방법도 좋은 것 같다.

여기까지 왔으면 거의 다 풀었다.
for문을 사용해서 오리 머릿수 만큼 돌린다.
q[i], u[i], a[i], c[i], k[i]의 값을 비교해서 순서가 안 맞으면 for문 탈출하고 -1을 출력한다. (ex. qauckquack -> 첫 울음소리가 이상하다.)

순서가 잘 맞는다면 q[i]와 k[i] 사이에 있는 q의 개수+1 중 제일 큰 수를 찾아서 출력하면 된다.

정리

문자열이 5의 배수가 아닐 경우
quack은 5글자라 녹음본의 문자열은 5의 배수여야 한다. 문자열이 5의 배수가 아닐 경우에는 -1을 출력하고 끝.
문자열이 5의 배수일 경우
문자열에 대해 q,u,a,c,k의 index를 찾아 각각 배열에 저장한다
q[0], u[0], a[0], c[0], k[0]에 대해 각각의 값(=순서)을 비교한다.
(1) quack 순서가 안 맞는 경우는 for문 탈출하고 -1 출력
(2) 순서가 맞다면 q[0]와 k[0] 사이에 있는 q 개수 찾고, 그동안 찾은 개수보다 크다면 result에 집어넣는다. (q[i]와 k[i] 사이에 있는 q의 개수+1의 최댓값 찾기)
1,2,3,4,...에 대해서도 비교하고 result 출력🦆

코드

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

function findString(arr, value) {
    let stringIndex = [];
    arr.forEach((element, index) => {
        if(element === value)
            stringIndex.push(index);
        }
    )
    return stringIndex;
}

let num = sound.length/5;
if(num % 1 !== 0) { //5의 배수가 아님
    result = -1;
} else {
    let q = findString(sound,"q");
    let u = findString(sound,"u");
    let a = findString(sound,"a");
    let c = findString(sound,"c");
    let k = findString(sound,"k");

    for(let i = 0 ; i < num; i++) {
        if(q[i] < u[i] && u[i] < a[i] && a[i] < c[i] && c[i] < k[i]) {
            let cnt = 0;
            for (let j = i; j < num; j++) { // q[i]보다 같거나 크고 k[i]보다 작은 index를 가진 q 개수 세기
                if (q[j] < k[i])
                    cnt++;
            }
            if (cnt > result) // result는 max 값
                result = cnt;
        }
        else {
            result = -1; //순서가 안맞는 경우 바로 for문 탈출
            i = num;
        }
    }
}
console.log(result);