99. 중복 제거 (백준 13701) [JAVA]

 

문제

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

13701번: 중복 제거

문제

문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때,

1. 0 ≤ Ai < 225 = 33554432, i=1,2,…,N.
2. 입력의 개수 N은 1 이상 500만 이하이다.

입력

첫째 줄에 A1, A2, ..., AN이 주어진다.

출력

B1, B2, ..., BN’을 출력한다.

풀이

문제 자체는 간단하지만, 시간과 메모리 조건이 빡빡해서 일반적인 방법으론 해결할 수 없었다.

처음에는 HashMap을 사용했지만, 시간초과가 발생해서

검색해본 결과 비트 벡터인 BitSet을 사용하여 해결하였다.

인덱스 하나당 1bit만을 사용하기 때문에 메모리의 부담이 적다.

입력받은 수에 해당하는 인덱스의 비트를 set으로 true로 설정하고, get을 통해 체크하면 문제는 해결된다.

또 효율적인 입력, 출력 방법으로 System.in, out이 아니라 BufferedReader, Writer를 사용하고

String.split 대신 StringTokenizer로 토큰을 나누는 방법을 사용하여 메모리와 시간을 절약할 수 있다.

코드

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

public class Main {

    static BitSet bs = new BitSet(33554432);
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int size = st.countTokens();
        int cur;

        for(int i=0; i<size; i++){
            cur = Integer.parseInt(st.nextToken());
            if(!bs.get(cur)){
                bs.set(cur);
                bw.write(cur+" ");
            }
        }
        bw.flush();
        bw.close();
    }
}

결과

 

 

전문가가 아니라 정확하지 않은 지식이 담겨있을 수 있습니다.
언제든지 댓글로 의견을 남겨주세요!