[Codeground] 연습문제 - #1. 숫자 골라내기(Java)

 프로그래밍 대회 준비하기 위해서 codeground 사이트를 통해 프로그래밍 연습을 하기 시작했다. 첫 번째로 연습문제인 숫자 골라내기 문제를 풀었다.

[문제 요약]

 - N개의 10진수 중, '홀수' 번만 나타나는 숫자들을 모두 XOR 한 결과 구하기

 - 예를 들어, '2, 5, 3, 3' 이 주어지면, '2' 와 '5'는 1번(홀수 번) 나타나고 '3'은 2번(짝수 번) 나타나므로 홀수 번 나타난 '2'와 '5'를 XOR 한 결과를 구하면 된다

[문제 조건]

 - 제한 시간 : 전체 테스트 케이스는 20개 이하, 전체 수행 시간은 1초 이내(Java 2초 이내)

 - 메모리 사용 제한 : heap, global, static 총계 256MB, stack 1MB

[입력 조건]

 - 입력 파일의 첫째 줄에는 테스트 케이스 개수를 나타내는 자연수 T ( 1 <= T <= 20 )

 - 각 테스트 케이스의 첫째 줄에는 N 개의 수를 나타냄 ( N은 300만 이하의 자연수)

 - 각 테스트 케이스의 두 번째 줄에는 N 개의 숫자들이 공백(빈칸)을 두고 주어짐

 - 각 숫자는 32bit 정수형 변수에 담을 수 있는 음이 아닌 정수

[출력 조건]

 - 각 테스트 케이스의 답을 순서대로 표준 출력

 - 첫 줄에는 "Case # T"를 출력. 이때 T는 테스트 케이스의 번호.

 - 그다음 줄에는 주어진 숫자 중 '홀수' 번만 나타나는 숫자들을 모두 XOR 한 결과를 출력함

---

[오답 문제 풀이]

 - 나는 문제 그대로 해석해서 그대로 코드를 작성하려고 했다. 입력받은 숫자들을 배열에 저장하고, 첫 번째 숫자부터 마지막 숫자까지 그 숫자를 뽑아서 나머지 배열에 있는 수와 비교해서 count 하여 2차원 배열에 집어넣고, 홀수 번 나타난 숫자들을 다시 찾아 XOR 연산한 뒤, 결과를 출력하자는 생각을 했다. 코드 작성하는 과정에서 어려움을 겪어 Stack Overflow 에서 내가 막힌 부분을 찾아서 해결해 보았지만, 오답으로 결과가 나왔다. 입력 조건에 맞춰서 숫자들을 입력하면 결과가 알맞게 나오는데 이상하게 오답으로 나왔다. 내 생각에는 원하는 알고리즘, 또는 풀이 과정이 아녀서 오답 처리한 것 같다.

[정답 문제 풀이]

 - 결국 힌트를 얻기 위해 정답을 맞힌 사람들의 공유 코드를 보았다. 의외로 간단하게 문제를 풀어서 깜짝 놀랐다. XOR 연산의 특징을 이용하면 되는 문제 풀이였다.

 - XOR 연산은 입력값이 같지 않으면 1을 출력하는 연산이다. (기호는 ^)

0 XOR 0 = 0

0 XOR 1 = 1

1 XOR 0 = 1

1 XOR 1 = 0

  이 문제 풀이에서 사용한 XOR 연산의 특징은, 자기 자신과 연산을 하면 0이 되고, 어떤 값과 0을 XOR 하면 결과가 그 어떤 값과 같다는 성질이다. 자기 자신과 연산하는 것은 이 문제에서 '짝수 '번 나타나는, 즉 값이 같은 두 수를 XOR 연산을 하면 0이 된다. 그 0을 다른 값을 가진 수와 XOR연산을 하면 결과가 그 수로 나타난다.

 - 그래서 '짝수' 번이나 '홀수' 번 나타나는 것은 상관이 없다. '짝수' 번 나타나는 숫자들을 다 XOR 연산을 하면 0이 되고, '홀수' 번 나타나는 숫자들은 2 x n + 1 이기 때문에, '홀수' 번 나타나는 숫자들끼리 연산하는 결과를 구하면 답이 되는 것이다. (좀 더 풀어보자면 홀수는 2로 나누면 1이 남기 때문에 '짝수' 번 연산하면 0, 하나 남은 숫자랑 0이랑 연산하면 자기 자신이 나온다)

 - 그러면 받아오는 입력값들의 몇 번 나타나는지 상관없이, 그냥 다 연산하면 되는 것이었다. for 문 돌려서 받아오는 총 개수인 N 번 돌리면서 받아오는 값들을 계속 XOR 연산하여 결과 변수(result)에 저장하고 출력하면 된다.

[소스 코드]

/*
You should use the standard input/output

in order to receive a score properly.

Do not use file input and output

Please be very careful. 
*/
 
import java.util.Scanner;
 
/*
   As the name of the class should be Solution , using Solution.java as the filename is recommended.
   In any case, you can execute your program by running 'java Solution' command.
 */
 
public class Solution {
 
    static int Answer;
 
    public static void main(String args[]) throws Exception {
        /*
         * The method below means that the program will read from input.txt, instead of
         * standard(keyboard) input. To test your program, you may save input data in
         * input.txt file, and call below method to read from the file when using
         * nextInt() method. You may remove the comment symbols(//) in the below
         * statement and use it. But before submission, you must remove the freopen
         * function or rewrite comment symbols(//).
         */
 
        /*
         * Make new scanner from standard input System.in, and read data.
         */
        Scanner sc = new Scanner(System.in);
        //Scanner sc = new Scanner(new FileInputStream("input.txt"));
 
        int T = sc.nextInt();
        for (int test_case = 0; test_case < T; test_case++) {
 
            Answer = 0;
            /////////////////////////////////////////////////////////////////////////////////////////////
            /*
             * Implement your algorithm here. The answer to the case will be stored in
             * variable Answer.
             */
 
            int totalNumber = sc.nextInt();
            
            for(int i = 0; i < totalNumber; i++) {
                int num = sc.nextInt();
                Answer ^= num;
            }
            /////////////////////////////////////////////////////////////////////////////////////////////
 
            // Print the answer to standard output(screen).
            System.out.println("Case #" + (test_case + 1));
            System.out.println(Answer);
        }
    }
 
}

[후기]

 - XOR 연산에 대한 특징을 알았다. 짝수 번 연산하면 0이 되는 성질을 이용하여 홀수 번 연산하면 그 값이 결과로 나온다는 것.

 - 공부 더 해야 한다는 점....