[BOJ][Python3]12933. 오리

문제 유형: 구현

 

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

12933번: 오리

 

퍼포먼스가 낮지 않으면서도 꽤 특이한 풀이를 작성했다고 생각해서 공유하고자 한다.

문제에서 묻는 건 오리의 수인데, q,u,a,c,k 이렇게 오리가 순서대로 운다. 다만 중첩해서 울 수도 있는데(qquuaacckk) 이런 경우는 오리가 두 마리 있는 경우다. 다만 invalid한 quack이 있을 수 있다. 순서가 맞지 않거나 글자가 하나 빠진 경우가 있기 때문이다.

 

대강 젤리코코라는 플래시게임을 상상하면 된다. 위에서 qqquuauaackcckk 이 내려오고 하나씩 받아서 q, u, a, c, k 씩 모아 정리해주는 개념이다. 

젤리코코 플래시게임

다른 사람의 풀이를 보니 input string에서 q, u, a, c, k의 개수를 각각 카운트해서 뒤 문자가 앞 문자의 개수보다 많아지면 invalid하다고 처리했다.

 

오리가 아무리 많아야 500마리기 때문에 0으로 채워진 배열을 만들고 시작했다. 나는 비트마스킹을 이용했는데, q,u,a,c,k를 11111 로 보고 각 자리를 채웠다. 즉 q가 들어오면 10000 으로 첫 번째 자리를 1로 만들어줬다. 그 다음에 u 가 들어오면 10000(2), 즉 16을 찾고 11000으로 만들어줬다. k까지 들어와서 11111(2) 즉 31이 채워지면 pop 했다, 마지막에 31의 개수를 세는 방식을 취했다.

 

python의 find() 함수를 사용해서 해당하는 첫 번째 수를 리턴하도록 했는데, 여기서 없는 경우 -1을 출력하게 했다.

 

한 번 틀렸는데, quac 처럼 완결이 되지 않는 경우를 핸들링하지 않아서 그랬다. 마지막에 31과 0의 개수를 모두 세서 duck의 사이즈와 동일한지 체크해줘서 미완성인 quack이 있다면 -1을 출력했다.

 

def find_duck(duck, target):
    # duck array에서 target보다 큰 값을 찾는다
    return duck.index(target) if target in duck else -1

def sol(q, duck):
    for i in range(len(q)):
        # quack를 분리하려고 할때 필요한 최소 스택의 수는?
        t = -1
        if q[i] == 'q':
            # 10000 이면 16
            t = find_duck(duck, 31)
            if t == -1:
                t = find_duck(duck, 0)
            duck[t] = 16

        if q[i] == 'u':
            # 11000 이면 24
            t = find_duck(duck, 16)
            duck[t] = duck[t] | 8

        if q[i] == 'a':
            # 11100이면 28
            t = find_duck(duck, 24)
            duck[t] = duck[t] | 4

        if q[i] == 'c':
            # 11110 이면 30
            t = find_duck(duck, 28)
            duck[t] = duck[t] | 2

        if q[i] == 'k':
            # 11111 이면 31
            t = find_duck(duck, 30)
            duck[t] = duck[t] | 1

        if t == -1:
            return -1

    c = duck.count(31)
    z = duck.count(0)

    if c + z == len(duck) :
        return c
    return -1

q = input()

# 오리의 최대 수는 500마리. 실버 문제는 이런 식으로 max size를 미리 계산하면 쉽게 풀리는 경우가 많다.
duck = [0 for _ in range(501)]


print(sol(q, duck))