[알고리즘/구현] 12933번 : 오리 - python

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

12933번: 오리

 

---

• 문제
• 소요시간: 44분 18초

---

• 설계하기(접근방법) 

1. 문자열을 입력받는다

2. 구현

 

오리의 울음 소리 : quack

한 번의 울음이 끝났다면 또 울음소리를 낼 수 있다.

 

오리의 수를 duck하고 선언하고

가장 오리가 많았던 순간을 duck_max라고 선언한다

 

오리가 한 번 울음을 마치면 재울음이 가능하다

 

문자열을 순회하면서

오리가 우는 동안에는 (문자열에 'q'가 옴)

 

duck += 1을 해주고

 

오리가 울음을 멈췄을 때는 (문자열에 'k'가 와서 마침)

duck -= 1을 해준다

 

문자열을 순회하는 와중에

duck_max를 계속 갱신시킨다

 

if duck > duck_max: # 오리의 최대치가 갱신되면

    duck_max = duck # 갱신해준다

 

오리의 최대치를 구하는 아이디어는 끝이 났으니 다음은 오류를 잡아내야 한다

flag = 0을 선언하고

flag = -1이 되는 경우, -1을 출력한다

 

오류는 다음과 같다

조건 1) 문자열이 5의배수가 아닌경우

조건 2) 'q', 'u', 'a', 'c', 'k'의 개수가 다른 경우

조건 3) 'q', 'u', 'a', 'c', 'k'이 순서대로 오지 않은 경우

 

조건 1) 문자열이 5의배수가 아닌경우

 

이 경우는 조건 2)에 흡수된다. quack의 개수가 같으면 합이 5의 배수이기 때문이다

 

조건 2) 'q', 'u', 'a', 'c', 'k'의 개수가 다른 경우

 

q == u == a == c == k 인 경우 pass

아닌 경우는 flag = -1

 

조건 3) 'q', 'u', 'a', 'c', 'k'이 순서대로 오지 않은 경우

 

이 조건을 구현하는 경우는 여러가지 방법이 있겠지만 최대한 간단하게 구현했다

 

변수를 총 5개 선언한다

q = 0

u = 0

a = 0

c = 0

k = 0

 

문자열을 순회하며 각각의 문자가 나타나는 경우, 각 += 1을 해준다

예를 들어

quack이면

i = q

q = 1, u = 0, a = 0, c = 0, k = 0

i = u

q = 1, u = 1, a = 0, c = 0, k = 0

i = a

q = 1, u = 1, a = 1, c = 0, k = 0

.......

 

와 같이 더해준다.

 

만약 q보다 u의 숫자가 크다면

예시 : 'quuack'와 같이 오류가 나타난 것이다

q = 1, u = 2 ERROR

 

문자열 순회 시 조건으로

q < u < a < c < k을 추가해주어 다음과 같은 문자열이 나타난 경우

flag = -1후 break해준다

 

이의 조건들을 모두 통과한 후 duck_max를 구한다

 

3. duck_max를 출력한다.

 

 

 

 

 

---

• 코드(출력)

n = input()

duck = 0
duck_max = 0
flag = 0

q = 0
u = 0
a = 0
c = 0
k = 0

for i in n:
    if i == 'q':
        q += 1
    if i == 'u':
        u += 1
    if i == 'a':
        a += 1
    if i == 'c':
        c += 1
    if i == 'k':
        k += 1
    if q < u or u < a or a < c or c < k:
        flag = -1
        break

if q == u == a == c == k:
    pass
else:
    flag = -1

for i in n:
    if i == 'q':
        duck += 1
    if i == 'k':    
        duck -= 1
    if duck > duck_max:
        duck_max = duck

if flag == -1:
    print(-1)
else:
    print(duck_max)

---

• 얻어갈 부분

1. 구현의 아이디어를 잘 낸 것 같다. 하지만 문제를 이해하는데 시간이 좀 오래 걸렸다. 예시를 잘 살펴봐서 문제 해석의 시간을 줄이자