[백준 - 10464번] XOR - Java //Wello Horld //

 

이번에는 BOJ의 10464번 문제 "XOR" 을 풀어보도록 하자

 

 

입력으로 첫 번째 줄에 테스트 케이스의 개수 T가 주어지고, 그 다음 T줄만큼 두개의 정수 S와 F가 주어진다.

출력으로는 각 테스트 케이스마다 S에서 F까지의 모든 정수를 XOR한 값을 출력하면 된다.

 

이번 문제는 아래와 같이 그냥 루프에다가 S, F 를 넣어서 하나씩 계산하게 만들면, 시간초과가 나오게 된다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        for(int i = 0; i < T; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken());
            int F = Integer.parseInt(st.nextToken());
            int a = S;
            for(int j = S + 1; j <= F; j++){
                a = a ^ j;
            }
            bw.write(a + "\n");
        }

        bw.flush();
        br.close();
        bw.close();
    }
}

 

 

m부터 n까지의 XOR에 관한 연산을 생각해서 답을 도출하면 된다.

 

먼저, 예시로 1부터 10까지를 이진수 형식으로 표현해 보면

 

0001 - 1
0010 - 2
0011 - 3
0100 - 4
0101 - 5
0110 - 6
0111 - 7
1000 - 8
1001 - 9
1010 - 10

이 된다.

 

먼저, 1 과 2를 XOR 연산 해보면, 0011 - 3이 나온고,
1과 3은 0000 - 0,
1과 4는 0100 - 4,
1과 5는 0001 - 1,
1과 6은 0111 - 7,
1과 7은 0000 - 0,

여기까지 해보고, "????????????,,,,, 반복패턴이 있네??" 했다.

1과 8은 1000 - 8,
1과 9는 0001 - 1,
그러면, 1과 10은 1011 - 11

 

그러고 나서, 2와 3을 XOR 연산 해보면, 

2와 3은 0001 - 1,
2와 4는 0101 - 5,
2와 5는 0000 - 0,
2와 6은 0110 - 6,
2와 7은 0001 - 1,
2와 8은 1001 - 9,
2와 9는 0000 - 0,
2와 10 은 1010 - 10

이 된다.

뭔가 함정 카드에 걸린 것 같아서, 3까지 해봤다.

3과 4는 0111 - 7,
3과 5는 0010 - 2,
3과 6은 0100 - 4,
3과 7은 0011 - 3,
3과 8은 1011 - 11,
3과 9는 0010 - 2,
3과 10은 1000 - 8,

1이랑 2만 비교했을 때는 1과 0 이 많이 나와서 하나의 식으로 표현 할 수 있는 줄 알았는데, 그게 아닌가 보다.

그렇게 노가다 한 결과, m이 짝수일 때랑 홀수일 때, 아래와 같이 결과가 달라진다는 걸 알았고,

if(m % 2 == 0)
	pattern = new int[] {n, 1, n^1, 0};
else
	pattern = new int[] {m, m^n, m-1, (m-1)^n};

 

성공한 코드는 아래와 같다.

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        for(int i = 0; i < T; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken());
            int F = Integer.parseInt(st.nextToken());
            bw.write(calcXOR(S, F) + "\n");
        }

        bw.flush();
        br.close();
        bw.close();
    }
    static int calcXOR(int m, int n) {
        int[] pattern;
    
        if(m % 2 == 0)
            pattern = new int[] {n, 1, n^1, 0};
        else
            pattern = new int[] {m, m^n, m-1, (m-1)^n};
    
        return pattern[(n-m) % 4];
    }
}

 

 

문제 : https://www.acmicpc.net/problem/10464

10464번: XOR

 

 

혹시 코드에 이상한 부분이나 틀린 부분이 있던지, 이해가 안가는 부분이 있다면 댓글로 알려주세요