[백준 Gold 3] 13701 중복 제거 - Java

문제링크 : https://www.acmicpc.net/problem/13701

13701번: 중복 제거

 

접근 과정 : 

• 얼마전에 알게된 BitSet을 이용해서 이전에 입력된 숫자를 저장했다.
• 숫자값에 따른 존재여부를 확인하는 것은 HashSet보다 BitSet이 빠를것이라고 생각했다.

+ 배열과 비트마스킹을 이용한 풀이도 있기에 시도해보았다. (다른사람의 풀이를 참고.)

 

 

소스 코드 및 결과 :

package BOJ;

/* 
    중복 제거
    
    BitSet
*/

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

public class BOJ13701 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        BitSet set = new BitSet();

        StringBuilder sb = new StringBuilder();
        while (st.hasMoreTokens()) {
            String s = st.nextToken();
            int a = Integer.parseInt(s);
            if (!set.get(a)) {
                set.set(a);
                sb.append(s).append(" ");
            }
        }

        bw.write(sb.toString().trim());
        bw.flush();

    }
}

 

package BOJ;

/* 
    중복 제거
    
    배열 + 비트마스킹
    
    number[a/32]에 비트값으로 나머지를 저장. 

*/

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

public class BOJ13701_copy {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[] number = new int[1 << 20];

        StringBuilder sb = new StringBuilder();
        while (st.hasMoreTokens()) {
            String s = st.nextToken();
            int a = Integer.parseInt(s);
            int x = a / 32;
            int y = a % 32;
            if ((number[x] & (1 << y)) != (1 << y)) {
                number[x] |= (1 << y);
                sb.append(s).append(" ");
            }
        }

        bw.write(sb.toString().trim());
        bw.flush();
    }
}

 

P.S 

중복 제거이기에, 당연히 set를 이용하려고 했다.

아마 BitSet을 모르고 HashSet을 사용했으면, 많은 시간이 소모되었을 것이다..

사실 해당 문제는 두번째 방법처럼 접근하는데 정답이지 않을까 싶다.