[백준] 12933번 오리

park geonwoo·2024년 10월 25일

목록 보기

28/32

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

문제는 오리의 울음 소리를 분석하여 방 안에 있는 오리의 최소 수를 구하는 문제입니다. 오리의 울음 소리는 "quack"이며, 여러 오리가 동시에 울 경우 소리가 섞일 수 있습니다. 주어진 소리를 통해 올바른 오리의 울음 소리인지 판단하고, 최소 몇 마리의 오리가 있었는지를 계산해야 합니다. 만약 주어진 소리가 올바르지 않은 경우에는 -1을 출력해야 합니다.

문제 이해

문제 요약

목표: 주어진 소리 문자열이 여러 오리가 동시에 울면서 만들어진 것이라면, 그 소리를 만들 수 있는 오리의 최소 수를 구합니다. 만약 주어진 소리가 올바르지 않다면 1을 출력합니다.
올바른 오리의 울음 소리:
- "quack"을 한 번 이상 연속해서 내는 것.
- 예: "quack", "quackquack", "quackquackquack" 등.
소리의 특성:
- 여러 오리가 동시에 울 경우 소리가 섞일 수 있음.
- 각 오리는 "quack"의 순서를 반드시 지켜야 함.
- 동일한 오리의 울음은 중복 없이 순차적으로 이어져야 함.
올바르지 않은 경우:
- "quack"의 순서가 지켜지지 않거나, 모든 오리가 "quack"을 완료하지 못한 경우.
- 예: "quackqauckquack" (두 번째 "quack"이 올바르지 않음).

예제 분석

예제 입력 1:

quqacukqauackck

예제 출력 1:

해석:

두 마리의 오리가 동시에 울면서 소리가 섞인 것으로 해석.
첫 번째 오리: q -> u -> q -> a -> c -> u -> k
두 번째 오리: q -> a -> u -> a -> c -> k -> c -> k

예제 입력 2:

kcauq

예제 출력 2:

-1

해석:

"kcauq"는 "quack"의 순서가 지켜지지 않으므로 올바르지 않은 소리.

해결 방법

접근 방식

오리의 울음 소리를 분석하여 최소 몇 마리의 오리가 있었는지 파악하기 위해, 각 오리의 현재 상태를 추적하는 방식을 사용합니다. 오리의 상태는 "quack"의 각 문자에 따라 다음에 어떤 문자를 기대하는지를 나타냅니다.

상태 정의:
- 0: 'q'를 기다리는 상태
- 1: 'u'를 기다리는 상태
- 2: 'a'를 기다리는 상태
- 3: 'c'를 기다리는 상태
- 4: 'k'를 기다리는 상태 (울음이 완료된 상태)

알고리즘 단계

오리의 상태 추적:
- 각 오리의 현재 상태를 추적하기 위해 상태별 카운터를 사용합니다.
- counts = [0, 0, 0, 0, 0] 배열을 사용하여 각 상태별로 현재 몇 마리의 오리가 그 상태에 있는지를 저장합니다.
소리 문자열 순회:
- 소리 문자열을 처음부터 끝까지 순회하면서, 각 문자를 해당 상태에 맞는 오리에게 할당합니다.
- 'q'일 경우:
  - 울음을 완료한 (k 상태에 있는) 오리가 있으면 그 오리를 재사용하여 새로운 울음을 시작합니다.
  - 재사용할 수 있는 오리가 없다면, 새로운 오리를 추가합니다.
- 'u', 'a', 'c', 'k'일 경우:
  - 해당 문자를 기대하고 있는 오리가 있는지 확인합니다.
  - 없다면, 올바르지 않은 소리이므로 1을 출력합니다.
  - 있으면, 그 오리의 상태를 다음 상태로 업데이트합니다.
완료 상태 검증:
- 소리 문자열을 모두 처리한 후, 모든 오리가 울음을 완료한 (k 상태) 상태인지 확인합니다.
- 그렇지 않다면, 올바르지 않은 소리이므로 1을 출력합니다.
결과 출력:
- 유효한 경우, 사용된 오리의 총 수를 출력합니다.
- 유효하지 않은 경우, 1을 출력합니다.

구현 세부 사항

상태별 카운터:
- counts = [q_count, u_count, a_count, c_count, k_count]
오리의 추가 및 상태 업데이트:
- 'q'가 등장하면:
  - k_count가 1 이상이면, k_count에서 1을 빼고 q_count를 증가시킵니다.
  - 없다면, q_count를 증가시키고 total_ducks를 1 증가시킵니다.
- 'u', 'a', 'c', 'k'가 등장하면:
  - 해당 상태 이전의 카운터가 1 이상이어야만 해당 상태로 이동할 수 있습니다.
  - 그렇지 않으면, 올바르지 않은 소리이므로 1을 출력합니다.

코드 구현

아래는 위의 접근 방식을 구현한 파이썬 코드입니다.

import sys

def main():
    S = sys.stdin.read().strip()
    quack_sequence = "quack"
    # 상태별 카운터: q, u, a, c, k
    counts = [0, 0, 0, 0, 0]
    total_ducks = 0

    for char in S:
        if char == 'q':
            if counts[4] > 0:
                # 이미 울음을 완료한 오리를 재사용
                counts[4] -= 1
                counts[0] += 1
            else:
                # 새로운 오리 추가
                counts[0] += 1
                total_ducks += 1
        elif char == 'u':
            if counts[0] > 0:
                counts[0] -= 1
                counts[1] += 1
            else:
                print(-1)
                return
        elif char == 'a':
            if counts[1] > 0:
                counts[1] -= 1
                counts[2] += 1
            else:
                print(-1)
                return
        elif char == 'c':
            if counts[2] > 0:
                counts[2] -= 1
                counts[3] += 1
            else:
                print(-1)
                return
        elif char == 'k':
            if counts[3] > 0:
                counts[3] -= 1
                counts[4] += 1
            else:
                print(-1)
                return
        else:
            # 유효하지 않은 문자
            print(-1)
            return

    # 모든 오리가 울음을 완료했는지 확인
    if any(counts[i] > 0 for i in range(4)):
        print(-1)
    else:
        print(total_ducks)

if __name__ == "__main__":
    main()

코드 분석

1. 함수 정의

`main()`

목적: 문제의 입력을 처리하고, 올바른 오리의 수를 계산하여 출력합니다.
세부 동작:
1. 입력 읽기:
  - sys.stdin.read().strip()을 사용하여 전체 입력을 한 번에 읽어옵니다.
  - 입력 문자열 S는 오리들이 내는 소리입니다.
2. 상태 초기화:
  - counts = [0, 0, 0, 0, 0] 배열을 사용하여 각 상태별 오리의 수를 추적합니다.
  - total_ducks를 0으로 초기화하여 사용된 오리의 총 수를 기록합니다.
3. 소리 문자열 순회 및 상태 업데이트:
  - 소리 문자열 S를 처음부터 끝까지 순회합니다.
  - 각 문자에 따라 오리의 상태를 업데이트합니다.
4. 올바른 소리 여부 검증:
  - 모든 오리가 울음을 완료했는지 (k 상태) 확인합니다.
  - 그렇지 않다면, 1을 출력합니다.
5. 결과 출력:
  - 올바른 소리인 경우, 사용된 오리의 수를 출력합니다.
  - 올바르지 않은 경우, 1을 출력합니다.

2. 주요 변수 및 자료구조

counts 배열:
- 인덱스 0: 'q' 상태의 오리 수
- 인덱스 1: 'u' 상태의 오리 수
- 인덱스 2: 'a' 상태의 오리 수
- 인덱스 3: 'c' 상태의 오리 수
- 인덱스 4: 'k' 상태의 오리 수 (울음을 완료한 상태)
total_ducks 변수:
- 사용된 오리의 총 수를 기록합니다.

3. 상태 업데이트 로직

'q'일 경우:
- counts[4] > 0인 경우:
  - 이미 울음을 완료한 오리를 재사용하여 새로운 울음을 시작합니다.
  - counts[4]를 1 감소시키고, counts[0]을 1 증가시킵니다.
- counts[4] == 0인 경우:
  - 새로운 오리를 추가하여 울음을 시작합니다.
  - counts[0]을 1 증가시키고, total_ducks를 1 증가시킵니다.
'u', 'a', 'c', 'k'일 경우:
- 해당 상태 이전의 오리가 있어야만 상태를 업데이트할 수 있습니다.
- 예를 들어, 'u'일 경우 'q' 상태의 오리가 있어야 합니다.
- 만약 해당 상태 이전의 오리가 없다면, 올바르지 않은 소리이므로 1을 출력하고 종료합니다.
그 외의 문자일 경우:
- 유효하지 않은 문자이므로 1을 출력하고 종료합니다.

4. 완료 상태 검증

모든 오리가 울음을 완료했는지 (k 상태)에 대한 검증을 수행합니다.
counts[0]부터 counts[3]까지가 모두 0이어야 합니다.
하나라도 0이 아니면, 올바르지 않은 소리이므로 1을 출력합니다.

5. 시간 복잡도

전체 시간 복잡도: O(L)
- L은 소리 문자열 S의 길이입니다.
- 각 문자를 한 번씩 순회하면서 상태를 업데이트하므로, 선형 시간 복잡도를 가집니다.
구체적 분석:
- 소리 문자열을 한 번 순회하면서, 각 문자에 대해 상수 시간 내에 상태를 업데이트합니다.
- 최종 검증 또한 상수 시간 내에 수행됩니다.
따라서, 전체 알고리즘의 시간 복잡도는 O(L)입니다.
- 주어진 문제의 제한 조건 (L ≤ 2500) 내에서 매우 효율적입니다.

6. 공간 복잡도

counts 배열: O(1) 공간
기타 변수: 상수 공간
전체 공간 복잡도: O(1)
- 소리 문자열을 한 번에 읽어오므로, 입력 크기에 비례하는 추가 공간은 필요하지 않습니다.

7. 알고리즘 및 자료구조 설명

알고리즘: 상태 추적 및 시뮬레이션
- 오리의 울음 소리를 순차적으로 처리하면서, 각 오리의 현재 상태를 추적합니다.
- 이를 통해 오리를 재사용하거나 새로운 오리를 추가하여 최소한의 오리 수를 계산합니다.
자료구조: 배열
- counts 배열을 사용하여 각 상태별 오리의 수를 효율적으로 관리합니다.
- 배열 인덱스를 통해 각 상태에 빠르게 접근하고 업데이트할 수 있습니다.

park geonwoo

이전 포스트

[백준] 21606번 아침 산책

다음 포스트