[백준] 12933번 오리(python)

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

12933번: 오리

 

1. 난이도 실버 3

 

2. 내가 작성한 코드

 

사실 문제 자체는 어렵지 않은데 반례를 못 잡아서 그걸 해결하는 부분에서 오~~랜 시간이 걸렸다.

 

오죽하면 백준 질문게시판에 반례 문의를 남길 정도,,

 

놓치기 쉬운 부분은 "오리가 울다가 멈췄을 때"인 거 같긴 한데

 

내가 틀린 이유는 k로 끝난 오리가 있는 여부를 True or False로만 확인했다는 점이다.

 

이렇게 하면 quack로 끝난 울음소리(최소 오리의 수) 2개 이상이고, 새로운 울음의 시작이 2개 이상일 경우 중복으로 체킹되어 잡아내질 못한다.

 

너무 조금만 생각하면 찾을 수 있는 문제였는데,, 으구 

 

 

문제 해결 알고리즘

 

- check 라는 list에 q,u,a,c,k 각각의 개수를 체크한다 => 마지막에 개수가 다른 게 있으면 -1

 

- check_k 라는 변수에 한 마리가 여러 번 울 수 있는 경우를 확인한다 => k로 끝났을 때 +=1, q로 시작했을 때 -=1

 

- check리스트에서 앞 인덱스에 위치한 알파벳의 출연(?) 횟수가 자신의 출연 횟수보다 적으면 소리의 순서가 올바르지 않은 경우라 -1을 출력한다.

 

ducks = input()

check = [["q", 0], ["u", 0], ["a", 0], ["c", 0], ["k", 0]]
cnt = 0  # 오리 수
check_2 = 0  # 끝이 k로 끝나서 오리의 수를 증가시키지 않고 새로운 시작이 가능한 경우

for duck in ducks:
    for i in range(5):  # q,u,a,c,k중 무엇인지 파악
        if check[i][0] == duck:  # q,u,a,c,k의 index확인
            break

    check[i][1] += 1  # q,u,a,c,k의 개수 갱신

    if i == 0:  # 현재가 q
        if check_2 > 0:
            check_2 -= 1
        else:
            cnt += 1  # k로 끝난 오리가 없으면 새로운 오리가 낸 것

    elif check[i - 1][1] < check[i][1]:  # 소리의 순서가 올바르지 않은 경우 종료
        print(-1)
        exit()

    if i == 4:  # k로 끝난경우 True로 변경
        check_2 += 1

for i in range(5):
    if check[i][1] != check[i - 1][1]:  # q,u,a,c,k의 개수가 모두 같지 않은 경우 -1
        print(-1)
        exit()

print(cnt)

 

ㅋ_ㅋ 문제를 맞힌 사람이 708밖에 안돼서 정보를 넘나리 찾기 힘들었다.