[백준] 18222 : 투에-모스 문자열 - 자바(JAVA)

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

18222번: 투에-모스 문자열

 

문제 해석

0과 1로 이루어진 길이가 무한한 문자열 X가 있다.

문자열 X는 다음과 같은 과정으로 만들어진다.

 

1. X는 맨 처음에 0으로 시작한다.

2. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다.

3. X의 뒤에 X'을 붙인 문자열을 X로 다시 정의한다.

4. 2~3의 과정을 무한히 반복한다.

 

입력

첫 번째 줄에 자연수 k (1 ≤ k ≤ 10^18)가주어진다.

 

출력

첫 번째 줄에 k번쨰에 오는 문자를 출력하라.

 

문제 풀이 전 설계

k값의 범위가 int형을 초과하므로 long으로 입력받는다.

logn의 시간복잡도를 찾거나 특정 조건식을 찾아 k번째 오는 문자를 출력해야 한다.

 

1. 투에-무스 문자열을 생성한다 ( 길이를 특정해야 함)

1 -> 2 -> 4 -> 8 -> 16 -> ,,,, 크기로 문자열이 커짐

따라서 k의 크기에 따라 2^k 보다 크거나 같은 문자열을 생성해야 함.

 

2. 투에-무스 문자열을 10^(n-k)로 나누고 나머지 연산 10을 하면 k번째 오는 문자가 출력된다.

2. 그냥 StringBuilder.charAt(k-1) 메서드 사용하면 됨

 

문자열로 다루어 보려고 했으나 시간 복잡도 O(n)으로 시간 초과 

 

실패 코드

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

public class Main_18222_투에모스문자열 {

	static StringBuilder thueMorse = new StringBuilder();
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br=  new BufferedReader(new InputStreamReader(System.in));
		long k = Long.parseLong(br.readLine());
		int index = (int) k-1;
		int iter = 0;
		int sum = 1;
		while(sum <= k) {			
			sum *= 2;
			iter ++;
		}
		// k=0 -> iter = 0
		// k=2 -> iter = 2
		// k=4 -> iter = 3
		// k=5 -> iter = 3
		
		
		thueMorse.append("0");
		for(int i=0; i<iter; i++) {
			makeThueMorseString();
		}
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		bw.write(thueMorse.charAt(index) + "\n");
		bw.flush();
		bw.close();
		
		
	}
	
	private static void makeThueMorseString() {
		// 0을 1로 1을 0으로 만든 문자열 hi
		//StringBuilder temp = new StringBuilder();
		int length = thueMorse.length();
		for(long i =0; i< length; i++) {
			if(thueMorse.charAt( (int) i) == '0') {
				thueMorse.append('1');
				continue;
			}
			thueMorse.append('0');
		}
		
		
	}

}

 

점화식 도출

 

성공 코드

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

public class Main_18222_투에모스문자열 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long k = Long.parseLong(br.readLine());
		System.out.println(rec(k - 1));
	}

	private static int rec(long k) {
		if (k == 0)
			return 0;
		if (k == 1)
			return 1;
		if (k % 2 == 0)
			return rec(k / 2);
		return 1 - rec(k / 2);
	}

}