Programming/백준
[백준] 13701번 : 중복 제거
조용한고라니
2021. 3. 24. 01:47
반응형
13701번: 중복 제거
문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때, 0 ≤ Ai < 225 = 33554432, i=1,2,…,N. 입력의 개수 N은 1
www.acmicpc.net
[Collection 사용]
사실 이 문제의 알고리즘 카테고리는 '비트마스킹'이지만,,, 비트마스킹으로 어떻게 풀어야할지 몰라 3가지 방법으로 풀었다.
1) Set
2) boolean[]
3) Map
방법은 간단하다. 각 자료구조에 특정 값이 없다면 추가하고, 특정 값이 있다면 스킵한다.
# Code </>
1) Set
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Set<Integer> set = new HashSet<>();
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
while(st.hasMoreTokens()){
int val = Integer.parseInt(st.nextToken());
if(set.add(val))
sb.append(val).append(' ');
}
System.out.println(sb.toString());
}2) Array
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
boolean[] visit = new boolean[1 << 25];
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
while(st.hasMoreTokens()){
int val = Integer.parseInt(st.nextToken());
if(!visit[val]) {
visit[val] = true;
sb.append(val).append(' ');
}
}
System.out.println(sb.toString());
}3) Map
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Map<Integer, Integer> map = new HashMap<>();
StringBuilder sb = new StringBuilder();
int idx = 0;
StringTokenizer st = new StringTokenizer(br.readLine());
while(st.hasMoreTokens()){
int val = Integer.parseInt(st.nextToken());
if(!map.containsKey(val)) {
map.put(val, idx++);
sb.append(val).append(' ');
}
}
System.out.println(sb.toString());
}반응형