[백준 알고리즘] Q8741 이진수합 (규칙성 찾기)

1. Java 구현

       
import java.io.*;
import java.math.BigInteger;
import java.util.*;

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));
      StringBuilder sb = new StringBuilder();
      int n = Integer.parseInt(br.readLine());
      
      for(int i = 0; i < n; i++) 
         sb.append("1");
         
      for(int i = 0; i < n - 1; i++) 
         sb.append("0");
         
      bw.write(sb.toString());
      bw.close();
   }
}

2. 코드설명

 처음에 이 문제를 접했을 때 Integer.toBinaryString(int i) 로 변환해서 풀면되지 않을까? 라는 생각을 했다. 하지만 입력이 10^6 까지 가능하다. 

 BigInteger를 통해 문제를 풀어야하는데, 그렇다면 시간초과가 반드시 날 것이다. 이렇게 입력이 큰 경우는 규칙성만 찾으면 간단히 해결이 가능하다.

 수학적으로 규칙성을 발견이 안된다면, 적당한 크기의 입력값(n = 10)으로 결과값을 확인하고, 그 결과값을 바탕으로 찾으면 쉽게 문제를 풀 수 있다.

 내가 찾은 규칙성은 이렇다. arr[n - 1] * 2 를 한 다음에 2 * n - 2 번째 자리에 1을 추가하면 된다.

 이렇게 들으면 규칙성이 보이지 않는다. n = 10 까지 출력한 결과를 보자!

 문자열의 길이는 (자리수 * 2 - 1) 이고, 문자열에서 끝에 0이 들어가는 갯수는 (자리수 - 1)이다. 이 규칙성을 프로그래밍 하면된다.

 그리고 이 문제에서는 문자열을 결합을 할 때, '+'로 문자열을 붙이는 것보다 StringBuilder를 권장한다. '+'로 결합해도 좋지만 속도가 15배이상 차이났다.

 그 이유는, '+'로 결합하면 문자열을 뒤에 붙이는 것이 아니라, 새로운 문자열을 계속 생성하기 때문에 힙 메모리 공간도 많이 사용할 뿐만 아니라,

 속도도 저하된다. 

3. Pain Point

 규칙성을 발견하는 것이 어려웠다. 수학적으로는 완벽하게 찾아내지는 못했지만, 몇가지 숫자를 예제로 비교하다 보니 발견할 수 있었다.

 쉽지 않았다.... 그래도 이전보다는 빨리 찾고 있다. 잘 하고 있다.?