이번에 풀어본 문제는
백준 18222번 투에-모스 문자열 입니다.

📕 문제 링크

❗️코드

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

public class Main {
    static long [] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long K = Long.parseLong(br.readLine());
        map = new long[65];
        map[0] = 1;
        for(int i = 1; i < 65; ++i)
        {
            map[i] = map[i-1] * 2;
        }
        System.out.print(get(K));
    }
    static long get(long k)
    {
        if(k == 1) return 0;

        for(int i = 0; i < 65; ++i)
        {
            if(k <= map[i]) return 1- get(k - map[i-1]);
        }
        return 0;
    }

}

📝 풀이

0이라는 문자열이 있을 때, 문자열 전체를 0 또는 1로 반전시켜 문자열의 끝에 더해주는 규칙을 가진 문제입니다.
0
01
0110
01101001
이런식으로 진행됩니다.
위 규칙으로 만들어진 문자열에서, 입력받은 K번째 자리에 존재하는 숫자를 출력하는 문제입니다.
먼저 입력값의 범위에 유의하여 자료형을 선언해주고, 복사된 문자열의 길이는 당연히 계속 2배가 되므로 2의 제곱수가 됩니다. 인덱스 값에 따라 해당 시점의 자릿수를 담고있는 map을 만든 후, 재귀함수를 돌립니다.
get함수의 반복문 내에서는 0번째 인덱스부터 값을 탐색하여 현재 찾고자하는 위치(k)를 생성한 이전 문자열의 길이를 담은 map의 인덱스를 구해줍니다.
이전 문자열의 길이를 구하는 이유는,
만약 10번째 자리의 K를 구하고 싶다 했을 때 10번째 자리를 포함한 문자열이 생성되기 이전에는 8자리의 문자열이 존재했을 것이고, 10번째 자리에서 그 8자리를 역순으로 돌아가게 되면 10번째 자리의 값을 반전시킨 숫자가 존재하는 원리입니다. 따라서 해당 숫자를 구해 반전시킨다는 의미로 1에서 해당 값을 빼주면 됩니다. 최종적으로 k가 1까지 도달했을 때, 0을 리턴하면서 앞서 호출됐던 함수들의 결과가 딱딱 맞춰지며 최종 결과를 구할 수 있습니다.

📜 후기

겉으로만 봤을때는 쉬워보였는데, 그대로 구현하기가 너무 힘들어서 풀이를 찾아야 했습니다. 풀이를 보고도 이해하는데 생각보다 오래걸렸던 문제입니다..