[Java] 백준 18222 투에-모스 문자열

문제

18222번: 투에-모스 문자열 (acmicpc.net)

18222번: 투에-모스 문자열

풀이

반복되는 조건을 어떻게 처리할지가 관건인 문제

문제 조건을 다시 확인해 보자

1. X는 맨 처음에 "0"으로 시작한다. 
2. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다.
3. X의 뒤에 X'를 붙인 문자열을 X로 다시 정의한다. 
4. 2~3의 과정을 무한히 반복한다.

 

문자열 최대 길이 10^18를  일일히 확인하려면 TLE 가 뜬다. 따라서 반복되는 조건을 이용하여 찾아야 한다.

 문제 조건1,2,3 을 반복해서 하다보면, 현재 문자열  X 일때, ( X.len / 2 ) 를 기점으로 좌우 대칭, 반전임을 알 수 있다.즉 현재 위치 K 번째에서 , X length /2 의 왼쪽에 있으면 반전( 0 과 1 ) 을 하지 않고, 오른쪽에 있으면 반전을 주는 식으로 구현해야한다.

 

예시) 

주어진 문자 : 0110 1001 1001 0110

인 덱스         :0123 4567 8/9/10/11 ...

이렇게 있을때 8번째를 찾고 싶다.( 맨 앞에 0 이 0번째라 가정 )

현재 8은 size/ 2 를 기준으로 오른쪽임으로 좌우 반전을 적용하고 왼쪽 위치에서 찾아야한다.

왼쪽 위치에서 0 임으로, 좌우 반전 적용한 1이 정답이다. 

이 과정을 반복한다.

 

 

풀이는 다음과 같다.

1. 초기 배열 [ 1, 0, 0, 1 ] 을 생성한다.
2. 현재 size 절반 기준으로 왼쪽에 있으면 size만 /= 2 적용한다. 
3. 오른쪽에 있으면, idx 를 그만큼 감소시키고, isFlip을 적용시킨다
4. [1,0,0,1]  위치에 flip 을 적용시켜 정답을 출력한다.

 

코드

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
public class Main {

    public static void main(String[] args) throws IOException {
        Main m = new Main();
        m.solution();
    }
    public void solution() throws IOException {
        FastReader fr = new FastReader();
        long N = fr.nextLong()-1;
        long size = 1;
        while(size <= N ){
            size*=2;
            //System.out.println(size+" ,"+N+" ,"+(size<N));
        }

        int arr[] = new int[]{0,1,1,0};
        int isFlip = 0;
        long idx = N;
        while(idx > 3){
            size /=2 ;
            if(idx >= size){
                idx -= size;
                isFlip = (isFlip + 1)%2;
            }
        }


        System.out.println((arr[(int)idx]+ isFlip)%2);
    }


    public static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}