백준 13701번 중복제거 구현해보기

---

```

백준 13701번 중복제거 구현해보기

```

이번 글을 통해 배워갈 내용

1. 백준 13701번 풀이

---

https://www.acmicpc.net/problem/13701

13701번: 중복 제거

 

백준 13701번 숫자 제거는

난이도 실버 등급의 문제로서

 

1 이상 500만 이하의 개수의 33554432(2^25) 이하의 숫자가 주어질 때

중복되는 숫자를 제외하고 남은 숫자를 출력하면 되는 문제입니다.

 

시간제한 5초에

메모리 제한 8MB입니다.

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

 

Boolean [] 은 boolean 값 하나당 약 4-20 bytes을 사용
boolean [] 은 boolean 값 하나당 약 1 bytes을 사용

BitSet은 boolean 값 하나당 약 1 bit 을 사용
하기 때문에 BitSet을 사용하였으며

입출력이 매우 많기 때문에 String Builder를 사용하였습니다.

물론 StringBuilder는 메모리를 먹기 때문에

Java 8: 768 MB의 메모리 제한을 참조하였습니다.

 

 

각 숫자를

비트 셋에 있으면 무시하고

없으면 출력할 스트링에 넣고 비트셋에 넣어주면 되는 문제입니다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.BitSet;
import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/13701

public class Main {

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

        BitSet bitSet = new BitSet();

        while (st.hasMoreTokens()) {
            final int nextNum = Integer.parseInt(st.nextToken());
            if (!bitSet.get(nextNum)) {
                bitSet.set(nextNum);
                sb.append(nextNum + " ");
            }
        }

        sb.setLength(sb.length() - 1);
        System.out.print(sb);
    }
}

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

---