[SW Expert Academy, SWEA 9843] 촛불 이벤트 (java)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXGBKzuaPOoDFAXR

SW Expert Academy

---

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

728x90

---

아... 이 문제 굉장히 날 화나게 만들었다.

이분 탐색만 알고 있다면 문제 자체는 그렇게 어렵지 않은 편인데,,, 출력할 때 조심해야 한다.

 

100000개의 테스트케이스를 통과해야 하는데, 99999개만 맞고 마지막 테케가 계속 fail이 떴다...

아무리 생각해도 알고리즘에는 문제가 없는데, 예외 찾으려고 진짜 별 짓 다했다.

정답 코드랑도 크게 다른게 없는데,,,, 하면서 몇 시간 동안 고민하다가 결국 문제를 찾았다....

 

나는 SWEA 문제 풀 때, 보통 StringBuilder에 담아서 테스트케이스가 끝나면 한 번에 출력해주는데,

sb.append("#" + t + " " + result + "\n");

로 담고, 테이스 케이스가 끝난 후

System.out.println(sb);

로 출력했다.

이랬을 때 fail이 떴고 println을 print로 바꿔주니 pass 뜸....

여태까지 다른 문제는 계속 println을 썼는데 이 문제만 오류가 떠서 저게 문제인지 진짜 몰랐다...

 

그냥... 시간 낭비한게 너무 화나서 끄적여봄,,

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Solution {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int TC = Integer.parseInt(br.readLine());
        for (int t = 1; t <= TC; t++) {
            long N = Long.parseLong(br.readLine());

            /*
            N = (K(K+1)/2 이므로
            2N = K(K + 1)
            1 ~ N 사이의 수 중 K(K+1) = 2N을 만족하는 K를 이분 탐색으로 찾으면 된다.
             */

            // 이분 탐색
            long start = 1;
            long end = (long)Math.sqrt(N * 2);

            long result = -1;
            while(start <= end) {
                long K = (start + end) / 2;
                long num = K * (K + 1) / 2;

                if(num == N) {
                    result = K;
                    break;
                }
                else if(num > N) {
                    end = K - 1;
                }
                else {
                    start = K + 1;
                }
            }

            sb.append("#" + t + " " + result + "\n");
        }

        System.out.print(sb);
    }
}