[자바] 백준 3460번 이진수

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

 

이 문제에는 여러 가지.... 나름의 속임수..?가 좀 있다. 그래서 처음 풀었을 때 에러 나길래 좀 어이가 없었는데 지금 보니까 완전 이해 완료.. 

이 문제는 입력 받은 수에 대해서 1의 위치가 어디에 있는지에 대해서 출력하면 되는 문제였다. 예제가 13이었는데 13의 이진수는 1101이긴 하지만 출력 조건이 "위치가 낮은 것부터" 이기 때문에 1011로 뒤집었을 때의 1의 위치를 출력하면 됐다.

 

나는 인덱스 역할을 하는 하나의 변수를 생성하고, n을 나누면 해당 수를 2로 나눴을 때 나머지가 1일 때에 해당하는 인덱스 역할의 숫자 값을 출력하는 방식으로 구현했다. 문제를 풀 때 입력 형식에 대해서 잘못 이해해버려서 한 줄에 냅다 받는 거로 이해했었는데 알고 보니 한 줄씩 입력 받는 거였다. 이거 때문에 틀린 거 제외하고는 다 괜찮았다는 점!

 

코양이랑 이야기해보다가 시간복잡도와 공간복잡도를 고려한 최적의 풀이를 생각해봤는데 해보니까 StringBuilder와 BufferedWriter를 사용하는 게 가장 시간 복잡도가 낮았고, StringBuilder와 System.out.println 을 사용하는 것이 가장 공간 복잡도가 낮았다.

 

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++){
            int m = Integer.parseInt(br.readLine());
            int j = 0;
            while(m > 0){
                if(m % 2 != 0){
                    sb.append(j + " ");
                }
                m /= 2;
                j++;
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }

}

 

Java로는 둘이 1, 2위에 등극했다. 근데.. 주석을 넣으니까 시간 복잡도가 낮아지는 이상한 현상을 발견했다... 대신 공간 복잡도가 엄청엄청 늘어난다.. 매우 이상....😓

그리고 int 보다 StringBuilder를 먼저 선언하면 공간 복잡도가 줄어드는 대신 시간 복잡도가 늘어나고... 바꾸면 시간 복잡도가 줄어들고 공간 복잡도가 늘어난다... 복잡도의 세계는 멀고도 험하구나,,,,