백준 11332. 시간초과

문제 링크

난이도	정답률(_%)
Silver 4	25.995%

설계

• 총 테스트 케이스 C
• 내부 입력 최대 범위 N
• 내부 테스트 케이스 횟수 T
• 내부 케이스 제한시간 L

시간 복잡도

C, 최대 100번. O(1)

공간 복잡도

• BigInteger를 사용했는데 내부적으로 int형 배열을 사용해서 큰 수를 저장할 수 있다.
• 정확히 배열을 어떻게 써서 저장하는지는 잘 모르겠지만 한 칸에 2^32 크기만큼 저장되는 것으로 보임. 따라서 공간 복잡도는 연산의 결과 값 / 2^32 개 😕

풀이

• 연산 횟수를 계산해서 L * 100000000번을 넘으면 TLE로 처리했다.
• 다만 팩토리얼의 경우 계산 횟수가 너무 많아질 수 있으므로, 중간에 L * 100000000 을 넘을 경우 계산은 중단하고 결과를 출력하도록 했다.

새롭게 알게된 것

• 동료의 코드리뷰 덕분에 Java7부터 Switch문으로 String 비교를 할 수 있게 됐다는 것을 알게 되었다.
  • 또한 if-else문 보다 더 효율적인 바이트 코드가 생성되어 성능에도 더 나은 모습을 보인다고 한다.
  • 하지만 if문의 경우 "string".equals(input)으로 null에 대한 방지를 할 수 있지만 switch의 경우 string 타입 case만 허용하기 때문에 내부에서 null 처리를 할 수 없다. 따라서 해당 위치에 null이 들어오지 않는지 확인해야한다는 주의점이 있다.
  • String in Switch Case in Java

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int testCase = Integer.parseInt(br.readLine());

        for (int i = 0; i < testCase; i++) {
            String[] situation = br.readLine().split(" ");

            if (isTimeout(situation)) {
                bw.write("TLE!\n");
            } else {
                bw.write("May Pass.\n");
            }

        }

        bw.flush();
        bw.close();
    }

    private static boolean isTimeout(String[] inputs) {
        String bigO = inputs[0];
        BigInteger inputLength = new BigInteger(inputs[1]);
        BigInteger executeCount = new BigInteger(inputs[2]);
        BigInteger timeLimit = BigInteger.valueOf(Integer.parseInt(inputs[3]) * 100000000);

        switch (bigO) {
            case "O(N)":
                if (inputLength.multiply(executeCount).compareTo(timeLimit) == 1) {
                    return true;
                }
                break;
            case "O(N^2)":
                if (inputLength.pow(2).multiply(executeCount).compareTo(timeLimit) == 1) {
                    return true;
                }
                break;
            case "O(N^3)":
                if (inputLength.pow(3).multiply(executeCount).compareTo(timeLimit) == 1) {
                    return true;
                }
                break;
            case "O(2^N)":
                if (BigInteger.valueOf(2).pow(inputLength.intValue()).multiply(executeCount)
                        .compareTo(timeLimit) == 1) {
                    return true;
                }
                break;
            case "O(N!)":
                int n = inputLength.intValue();

                while (n-- > 1) {
                    inputLength = inputLength.multiply(BigInteger.valueOf(n));

                    if (inputLength.compareTo(timeLimit) == 1) {
                        return true;
                    }
                }

                if (inputLength.multiply(executeCount).compareTo(timeLimit) == 1) {
                    return true;
                }

                break;
        }

        return false;
    }
}