[백준 4335] 숫자 맞추기

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

4335번: 숫자 맞추기

 

풀이 설명

스탠이 거짓말을 하는지 판별하는 알고리즘입니다.

스탠의 발언(?)을 스택에 저장하고 스택에서 값을 꺼내서 그중 거짓이 있는지 판별합니다.

스탠의 발언은 크다(too high), 작다(too low), 같다(right on) 세가지입니다.그래서 정답보다 큰 수를 위한 스택 하나, 작은 수를 위한 스택 하나를 총 두개의 스택으로 거짓말을 판별합니다.자세한 로직은 아래의 소스코드 참고

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Stack;

public class BOJ4335 {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		Stack upper = new Stack<Integer>(); // 정답보다 큰 수들을 담을 스택
		Stack lower = new Stack<Integer>(); // 정답보다 작은 수를 담을 스택
			
		while(true) {
			int number = Integer.parseInt(br.readLine());
			if(number==0) return; // 입력이 0이면 함수 종료
			String sign = br.readLine();
			
			if(sign.equals("too high")) { // 정답보다 큰 수인 경우
				upper.push(number);			
			}else if (sign.equals("too low")){ // 정답보다 작은 수 인 경우
				lower.push(number);
			}else { // right on이 입력 되었을 경우
								
				boolean isFake = false; // 거짓말을 했는지 판별하는 불리언 변수
				while(!upper.isEmpty()) {
					int x = (int) upper.pop();
					if(number >= x) { // 스택에서 다 꺼내서 정답보다 크거나 같은 수만 있는지 확인
						isFake = true;
						break;
					}
				}
				
				if(!isFake) {
					while(!lower.isEmpty()) {
						int x = (int) lower.pop();
						if(number <= x) { // 스택에서 다 꺼내서 정답보다 작거나 같은 수만 있는지 확인
							isFake = true;
							break;
						}	
					}
				}
				
				if(isFake) {
					// 두 while문에서 잘못 말한 것이 하나라도 검출되면 강제종료 되므로
					// 다음의 케이스들에 대한 검증을 위해 배열을 비워줌
					upper.clear();
					lower.clear();
					System.out.println("Stan is dishonest");
				}
				// 둘다 false인 경우는 둘다 완전히 비워질 때까지 거짓말이 없었다는 것이므로 초기화 필요 X
				else System.out.println("Stan may be honest");
				
			}						
		}
	}
}