[백준] 12933번 오리 - python (실버3) 😩

연기리·2023년 6월 30일

백준 백준python

Algorithm

목록 보기

3/3

💦 서두

하하.. 실버3이라고 얕보지말아야지.. 싶었던 문제였다
대체 어떤 입출력에서 잘못된건지 예제 계속 테스트해봤던.. 그러고 대체 왜 잘못됐는지 무한 디버깅해봤던... (그래도 난 문자열 문제가 좋아🩵)

1번 풀이를 엎고
2번 아하! 싶었던 과정을 풀어보려한다

⚔️ 문제

오리의 울음 소리는 "quack"이다. 올바른 오리의 울음 소리는 울음 소리를 한 번 또는 그 이상 연속해서 내는 것이다. 예를 들어, "quack", "quackquackquackquack", "quackquack"는 올바른 오리의 울음 소리이다.

영선이의 방에는 오리가 있는데, 문제를 너무 열심히 풀다가 몇 마리의 오리가 있는지 까먹었다.

갑자기 영선이의 방에 있는 오리가 울기 시작했고, 이 울음소리는 섞이기 시작했다. 영선이는 일단 울음소리를 녹음했고, 나중에 들어보면서 총 몇 마리의 오리가 있는지 구해보려고 한다.

녹음한 소리는 문자열로 나타낼 수 있는데, 한 문자는 한 오리가 낸 소리이다. 오리의 울음 소리는 연속될 필요는 없지만, 순서는 "quack"이어야 한다. "quqacukqauackck"과 같은 경우는 두 오리가 울었다고 볼 수 있다.

영선이가 녹음한 소리가 주어졌을 때, 영선이 방에 있을 수 있는 오리의 최소 개수를 구하는 프로그램을 작성하시오.

핵심 입출력 ⭐️

🤨 풀이 과정 aka.생각의 흐름 ➿

1️⃣ 그저.. 각 문자의 순서만 맞으면 되는 줄 알았음 (시도)

문제를 제대로 안읽은게 보이는 점이.. quack말고 다른 문자는 안나온다했는데, 대놓고 예제를 "quuaick" 써놓은거 봐라 😡
그래서 작성한 input인 quqacukqauackck 는

quqacuk qauackck 로 2인줄 알았다 ^__^

그래서 cnt = 0 으로 초기세팅하고, 다음 문자 만날때마다 cnt 증가해주다가 cnt == 4 가 된다면 ans += 1, cnt = 0 해주는 방식으로 하려했다 (⬅️ 혼자 뿌듯해했던 나 .. 너무 수치스러워 😣)

이를 그대로 구현한 코드이다 ㅎㅎ..

코드

# 차례대로 q, u, a, c, k가 나오는 경우 (겹쳐서를 고려하지 않음))
ori = list(input())

cnt = 0
ans = 0

for i in range(len(ori)):
    if cnt == 0 and ori[i] == "q":
        cnt += 1
    elif cnt == 1 and ori[i] == "u":
        cnt += 1
    elif cnt == 2 and ori[i] == "a":
        cnt +=1 
    elif cnt == 3 and ori[i] == "c":
        cnt += 1
    elif cnt == 4 and ori[i] == "k":
        cnt = 0
        ans += 1
    else:
        continue

if(ans == 0):
    print(-1)
else:
    print(ans)

백준에 답안 제출해보니 퍼센트 올라가지도 않고 틀렸다하길래 입출력예제 밑에 있는 (핵심 입출력) 아이들도 보니까... 에?????? 왜 이게 돼???? ⬅️ ㅋㅋㅋ ㅠㅠ

2️⃣ 알고보니.. "겹치는 오리를 고려한 오리의 마리 수"를 구하기 (정답)

예제 3,4번은 Okay다 이말이야.. 근데 예제 5번은 아무리봐도 왜 오리가 3마리인지 이해가 안가서 직접 출력을 도출해봤다 (밑에 그림 참고)

결론은 겹치지 않고 소리를 내는 오리의 마리 수 이게 Key Point 였던 것이다..

그래서 머리가 아니라 콤퓨타의 시각으로 이걸 어떻게 판별하지.. 하다가 2차원배열에 차곡차곡 쌓아야하나? 싶었다.
근데 이렇게하게되면 quack 이 꽉 찼는지, u, a, c, k는 어떻게 배치할지(인덱스 작은거부터 탐색?) 뭔가 머리로는 두루뭉실하게 알겠지만 2차원 list로 구현을 하자고 생각해보니 고려할 것도 너무 많아서 비효율적이라는 직감이 들었다.

아,, 우선 q부터 찾자 !

q부터 찾으면 내가 알아서 하겠지 ⬅️ 진짜 안좋은 마인드인걸 이젠 깨달아서 생각이란걸 좀 해봤다

q를 찾는다
q를 찾고 해당 q의 다음 인덱스부터 나머지 uack를 찾자
만약 k를 만나면 ans += 1 해주고, 이어지는 오리를 찾자
나머지 uack를 찾자 (3,4번을 입력받은 리스트 길이만큼 수행)
다시 1로 돌아간다

2️⃣-1️⃣ 새로운 오리 / 기존 오리에 구별 부재

이렇게 생각을 해보고 코드로 옮겼다.
하지만 이렇게 구현한 코드에는 새로운 오리/기존 오리에 대한 판별이 없을 뿐더러,
3번의 '이어지는 오리 찾기' 가 'u'부터 찾아지는 모순이 생긴다. ⬅️ 근데 이 부분은 다시 또 not visited된 q를 찾아주기 때문에 결과만 보면 맞아보일 수 있다는 점

코드

# 이렇게 하면 quackquack은 한마리로 인지하는 것이 아닌, 2마리로 인식됨
sound = list(input())
visited = [ 0 ] * len(sound)
ans = 0

if sound[0] != "q"  or  sound[-1] != "k" or len(sound) % 5 :
    print(-1)
    exit()

def find_uack(start) :
    uack = "uack"
    j = 0
    global ans 
    for i in range(start, len(sound)):
        if sound[i] == uack[j] and not visited[i]:
            visited[i] = 1
            if sound[i] == "k":
                ans += 1
                j = 0
                continue    # j 때문에 continue로 꼭 끊어줘야함
            j += 1

for i in range(len(sound) - 4):     # 어차피 q 뒤에는 무조건 uack이 와야하므로 -4를 해준다
    if sound[i] == "q" and not visited[i]:
        visited[i] = 1
        find_uack(i + 1)

if ans :
    print(ans)
else :
    print(-1)

2️⃣-2️⃣ 새로운 오리 / 기존 오리에 구별 + 모순 해결 (찐 정답)

q를 찾는다
q를 찾고 해당 q의 인덱스부터 quack를 찾고, 찾으면 0으로 바꿔주자
만약 k를 만나면 ans += 1 해주고, 이어지는 (오리)q를 찾자
나머지 uack를 찾자 (3,4번을 입력받은 리스트 길이만큼 수행)
다시 1로 돌아간다

2-1과 비슷해보이지만 2-1의 문제점을 해결했다.
우선 q와 uack를 따로 찾고 있었던 모순을 uack이 아닌 quack으로 찾는 점으로 해결했고(2번),
새로운 오리와 기존 오리를 판별하기위해 new_ori 변수를 설정해서 true이면 새로운 오리로 설정하라는 의미(ans ++), false일 경우엔 기존 오리이므로 ans을 추가하지 않아도 된다는 의미로 코드를 짰다.

마지막으로 기존에는 visited 배열을 사용했는데, 디버깅할 때 보기 불편해서 ㅎ
그리고 어차피 탐색한 애들을 가지고 뭘 써먹는게 아니라, 탐색 했던 애들은 탐색을 안하려는 의도이므로 배열 요소를 0으로 바꿔주었다(2번)

📝 정답 코드

sound = list(input())
ans = 0

if sound[0] != "q"  or  sound[-1] != "k" or len(sound) % 5 :
    print(-1)
    exit()

def find_quack(start) :
    quack = "quack"
    j = 0
    global ans 
    new_ori = True      # 새로운 오리로 생성하라는 flag
    for i in range(start, len(sound)):
        if sound[i] == quack[j]:
            if sound[i] == "k":
                if new_ori:     # 새로운 오리일 경우, 오리(ans) 추가
                    ans += 1
                    new_ori = False     # k값으로 끝났으니 새로운 오리를 생성하지 말라는 flag          
                j = 0           # 이어지는 "q" 탐색 - 새로운 오리가 아님 (현재 오리)
                sound[i] = 0           
                continue        
            j += 1
            sound[i] = 0


for i in range(len(sound) - 4):     # 어차피 q 뒤에는 무조건 uack이 와야하므로 -4를 해준다
    if sound[i] == "q" :
        find_quack(i)


if any(sound) or ans == 0 :
    print(-1)
else :
    print(ans)