[python] 백준 4335. 숫자 맞추기

문제

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

 

스탠과 올리는 정수 맞추기 게임을 하고 있다. 스탠은 1과 10사이의 정수 하나를 생각하고, 올리는 스탠이 생각한 수를 맞춰야 한다. 올리가 수를 말할 때마다 스탠은 올리가 말한 수가 큰지, 작은지, 일치하는지를 말해준다. 게임이 몇 번 진행된 후 올리는 스탠이 거짓말을 하고 있다는 생각을 하게 되었다. 즉, 올리는 수를 말할때 마다 스탠이 자신이 생각한 수를 바꿀수도 있다는 생각을 했다. 이런 일이 실제로 벌어지는지 알아내기 위해서, 올리는 게임이 진행되면서 자신이 외친 수와 스탠이 말한 답변을 모두 적어놓았다.

올리가 외친 수와 스탠의 답변이 주어졌을 때, 스탠이 거짓말을 했는지 아닌지 알아내는 프로그램을 작성하시오.

입력

입력은 여러 개의 게임으로 이루어져 있다. 각 게임은 올리가 외친 수와 스탠의 답변으로 이루어져 있으며, 계속해서 번갈아가면서 주어진다.

올리가 외친 수는 1보다 크거나 같고, 10보다 작거나 같은 자연수이고, 스탠의 답변은 "too high", "too low", "right on" 중 하나이다.

"too high"는 올리가 외친 수가 스탠이 생각한 수보다 클 때, "too low"는 작을 때, "right on"은 일치할 때이다.

스탠의 답변이 "right on"이면, 게임이 끝난 것이다.

입력의 마지막 줄에는 0이 주어진다.

출력

각각의 게임에 대해서, 스탠이 거짓말을 한 적이 있다면 "Stan is dishonest"를, 없다면 "Stan may be honest"를 출력한다.

---

풀이

아이디어는 맞았는데 구현을 못해서 시간 내에 못풀었던 문제...

 

상황에 맞춰 최댓값과 최솟값을 지정해줘서 올리가 외친 수 중 "right on"이 나올때 수가 지금까지 지정해준 최댓값과 최솟값 사이에 있는 값이면 스탠이 정직한거고, 아니면 거짓말을 친거다.

 

이때, 주의해야하는 점은, 애초에 올리가 잘못 숫자를 외쳤을때인데 이 경우를 방지하기 위해서 max와 min을 사용해주자.

import sys
input = sys.stdin.readline

while True:
    maxNum = 10
    minNum = 1
    while True:
        n = int(input().strip())
        if n == 0:
            break
        ans = input().strip()
        if ans == 'right on':
            if n >= minNum and n <= maxNum:
                result = 'Stan may be honest'
            else:
                result = 'Stan is dishonest'
            break
        elif ans == "too high":
            maxNum = min(maxNum, n-1)
        elif ans == "too low":
            minNum = max(minNum, n+1)
    if n == 0:
        break
    print(result)

 

짜잔. 답 코드인데... 아까 위에서 주의하자고 했던 대로, maxNum에는 min으로 이미 있었던 maxNum과 불렀던 숫자보다 -1한 값을 비교해서 더 작은 값을 넣어준다. 여기서 -1을 하는 이유는...

 

만약 9!라고 외치고 "too high"라는 답을 들은 거라면, 9까지는 너무 크단 뜻. 그러니까 1~8까지 가능하다는 이야기다.

 

이런 식으로 right on이 나올때까지 반복하다가 right on이 나오면 비교하고 답을 출력한다.

그러고 만약 n이 0이라면 첫번째 while문에서 나오고 그리고 두번째 while문에서도 빠져나와서 결과를 출력하도록 하였다.

 

두번째 while문은 0이 나올때까지 계속 되어야하는데 right on이 나오고 난 이후는 초기화가 되어야하기 때문이다. 

그래서 스탠이 정직했는지 아닌지에 대한 여부가 출력된 이후, maxNum은 10으로, minNum은 1로 초기화되고... n이 0이 아니라면 다시 게임이 진행된다고 생각하면 된다.

 

시간 복잡도

몇일까... 지피티 피셜은 게임 횟수를 m이라고 했을때, m번 반복하기 때문에 O(m)이라고 하는데... 사실 잘 모르겠다..ㅎㅎ..

 

어마무시하게 헤맸던 흔적..ㅎㅎ