[백준11332] 시간초과 문제 풀이 - JAVA

[백준11332] 시간초과 문제 풀이 - JAVA

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

11332번: 시간초과

 

문제

유빈이는 코딩을 하다가 시간 초과가 났다. 그래서 시간 복잡도를 계산하기로 했다.

채점 시스템은 1초에 100000000(10^8)가지 동작을 할 수 있다.

여러분들은 유빈이를 도와 시간초과가 나는지 확인하는 프로그램을 작성하라.

입력

 

입력의 첫 번째 줄에는 테스트 케이스들의 수 C가 주어진다.

그 다음 C개의 줄에는 시간 복잡도를 나타내는 문자열 S, 각 테스트 케이스마다 입력의 최대 범위 N, 테스트 케이스의 수를 나타내는 T랑 제한시간(초 단위) 를 나타내는 L이 주어진다. (1 <= C <= 100, 1 <= N <= 1000000, 1 <= T, L <= 10, N, T, L은 정수)

시간 복잡도는 다음과 같은 5개 중 하나로 주어진다.

• O (N)
• O (N^2)
• O (N^3)
• O (2^N)
• O (N!)

출력

각 테스트 케이스들에 대하여 시간 초과가 나면 "TLE!", 시간 초과가 나지 않으면 "May Pass." 를 출력한다.

예제 입력 1 복사

5
O(N) 1000 10 10
O(2^N) 1000 10 10
O(N!) 2 10 10
O(N^3) 1000 1 10
O(N^3) 1001 1 10

예제 출력 1 복사

May Pass.
TLE!
May Pass.
May Pass.
TLE!

문제풀이

• 문제의 요구사항 대로 구현하면된다
• 주의할 점은 연산하다가 data type 별 max value 처리만 조심하면된다
• int 의 경우 32bit 정수형이고 최대값은 21억 정도다, 넘어가면 음수된다.
• long의 경우 64bit 정수형이고 최대값은 9 * 10^18 정도 된다.
•  O(N!), O(2^N) 의 경우 long의 표현범위를 넘어갈 수 있기때문에 주의해야한다
• Max값 해결방법은 A = B * C를 A / C = B 형태로 바꾸면 된다.
• 알고리즘 문제풀이에서 나누기 연산은 금기에 가깝지만 이렇게 한두번 쓰는 건 괜찮다.
• 이 문제에서 또 알아 두면 좋은 점은 cpu clock에 대한 언급이다. 1초동안 연산 가능한 횟수를 1억이라고 언급했는데, 이 것은 통상적으로 시간복잡도를 계산할때 사용하는 방법이다.
• 사실 CPU 성능에 따라 연산횟수가 차이가나는데, 3.2 GHz 짜리 CPU라고치면 연산속도는 1초에 32억회 정도이다.
• 하지만 1초 = 1억 연산 이라고 치환하는 이유는 A = B + C 연산 1회를 한다 치더라도 A,B,C를 메모리에 저장하고 + 연산을 하고 연산한 정보를 A에 반영하는 등 여러 단계를 거치기 때문이다.
• + 연산의 경우 단순하다, -, * ,>> , << 등도 단순하지만 / 연산은 20~30 회의 연산을 거친다 그래서 /는 사용하면 안되는게 국룰이다.
• 여담이지만 나누기 연산은 정확도도 떨어진다. 

 

package time_complexity.B11332;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * https://www.acmicpc.net/problem/11332
 * title : 시간초과
 * @author tempcru
 */
public class Main {

	static int C; //입력 수, [1, 100]
	static String S; // 시간복잡도 문자열
	static int N; // 입력 최대 범위, [1, 1000000]
	static int T; // 테스트 케이스의 수, [1, 10]
	static int L; // 제한시간, [1, 10]
	
	static final String pass = "May Pass.";
	static final String timeout = "TLE!";
	static final int cpu_clock = 100000000; 
	
	static boolean result; // 통과여부
	
	public static void main(String[] args) throws Exception {

//		System.setIn(new FileInputStream("./src/B11332/sample_data"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		C = Integer.parseInt(br.readLine().trim());
		
		StringTokenizer st;
		
		for(int i = 0; i < C; i++) {
			st = new StringTokenizer(br.readLine().trim());
			
			S = st.nextToken();
			N = Integer.parseInt(st.nextToken());
			T = Integer.parseInt(st.nextToken());
			L = Integer.parseInt(st.nextToken());
			
			checkTimeComplexcity();
		}
	}

	private static void checkTimeComplexcity() {

		double caseTime = (L * cpu_clock) / T;
		result = true;
		long temp;
		switch (S) {
		
			case "O(N)":
				if(caseTime >= N) {
					result = true;
				} else {
					result = false;
				}
				break;
				
			case "O(N^2)":
				if((caseTime / N) >= N) {
					result = true;
				} else {
					result = false;
				}
				break;
				
			case "O(N^3)":
				if(((caseTime / N) /N) >= N) {
					result = true;
				} else {
					result = false;
				}
				break;
				
			case "O(2^N)":
				temp = 1;
				for(int i = 0; i < N; i++) {
					temp = temp << 1;
					if(temp > caseTime) {
						result = false;
						break;
					}
				}
				break;
				
			case "O(N!)":
				temp = 1;
				for(int i = 2; i <= N; i++) {
					temp = temp * i;
					if(temp > caseTime) {
						result = false;
						break;
					}
				}
				break;
			default:
				break;
		}
		
		if(result) { // Pass
			System.out.println(pass);
		}else { // tle
			System.out.println(timeout);
		}
	}
}