13701번: 중복 제거

Skele·2025년 2월 20일

algorithm bitmasking

알고리즘 문제 풀이

목록 보기

4/21

13701번: 중복제거

N개의 정수 A1, A2, ..., AN (0 ≤ Ai < 2^25 = 33554432, i=1,2,…,N)가 주어진다.
반복되는 수를 제외하고 남은 M개의 수 B1, B2, ..., BM 을 입력된 순서대로 출력
시간제한 5초
메모리 제한 8MB(자바 768MB)

접근

메모리제한

메모리 제한이 굉장히 빡빡하기 때문에 Collection의 Set을 사용하면 당연히 터질 것을 예상할 수 있다.

시간제한

시간 제한은 5초로 널널한 편이지만, 그럼에도 문제에서 주어지는 길이가 상당히 길기 때문에 시간복잡도가 N으로 리니어해야한다.

비트 마스킹

시간복잡도가 N이어야하기 때문에 숫자가 중복되었는지 탐색 또한 O(1)이어야한다.
하지만, Set에 숫자를 넣거나 2^25크기의 배열을 생성하면 메모리가 초과된다.
따라서 비트마스킹을 통해 Integer의 비트를 또다른 배열로 활용하여 배열의 크기를 줄인다.

아래와 같이 비트마스킹을 활용하면 Integer는 32bit로, 32크기의 배열로 사용할 수 있다.
1. 배열의 index를 숫자 Ai를 32로 나눈 값으로 지정한다.
2. 해당 index값의 int 값의 비트를 Ai를 32로 나눈 몫으로 마스킹 한다.

예를 들어, 34 라는 숫자는 32로 나누었을 때 몫이 1이고 나머지가 2이다.
그렇다면 arr[1]의 값에 2번째 비트 값을 1로 만들어주는 것이다.

이렇게 한다면, 2^20 크기의 int 배열을 이차원 배열로 사용하면서, O(1) 의 시간에 값이 존재하는지 확인이 가능하다.

코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		solve(in);
	}
	
	public static void solve(BufferedReader in) throws IOException {
		StringTokenizer tokens = new StringTokenizer(in.readLine());
		
		StringBuilder str = new StringBuilder();
		
		// 최대 2^25제곱 길이의 입력이 들어오고, 각 int가 32비트로 값당 2^5까지 저장가능하다.  
		int[] mark = new int[1 << 20]; // 따라서 배열의 길이는 2^20이면 충분하다.
		
		while(tokens.hasMoreTokens()) {
			int num = Integer.parseInt(tokens.nextToken());
			
			int quotient = num/32; // 숫자값의 몫이 배열의 idx가 된다.
			int remainder = num%32; // 숫자의 나머지가 해당 idx 값의 비트 값이 된다.
			// 결과적으로 일차원 배열을 이차원 배열로 사용한다.
			
			if((mark[quotient] & (1 << remainder)) == 0) {
				mark[quotient] |= (1 << remainder);
				str.append(num).append(" ");
			}
		}
		
		System.out.println(str.toString());
	}
}