[BOJ] 백준 13701 중복 제거

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

Approach

메모리 제한이 8MB (= 8,000,000 Byte)로 여유롭지 못한 편이다.

중복되는 숫자인지 확인하는 방법 중에는 int arr[n];에서

n이 기존에 등장한 숫자인지 확인하는 것이다.

하지만 n의 범위가 33554432로 1 Byte인 char 타입으로 구현해도

→ 33,554,432 → 대략 34 MB 크기가 필요하다. 

▶ [ps] 알고리즘 문제 풀 때, 메모리 제한? (feat. 구조체 메모리 계산)  

[ps] 알고리즘 문제 풀 때, 메모리 제한? (feat. 구조체 메모리 계산)

 

비트마스크 (Bitmask)를 통해 해결 가능하다.

int 타입은 4byte = 32bit 이므로

1bit에 숫자 하나를 표현한다고 했을 때, 32개의 숫자를 표현 가능하다

비트마스크 (Bitmask)

 

코드 arr[idx] & (1 << shift); 부분을 살펴보자

[N = 3 일 때]

    idx = 0        (= 3 / 32)

    shift = 3      (= 3 % 32)

    arr[0] = 1 << 3 (= 1000b)이 더해진다.

    중복여부 확인시에는 arr[0]에서 4번째 비트가 켜져 있는지 확인하면 된다.

 

[N = 7 일 때]

    idx = 0        (= 7 / 32)

    shift = 7      (= 7 % 32)

    arr[0] = 1 << 7 (= 1000'0000b)이 더해집니다.

    다음에 중복여부 확인시에는 arr[0]에서 8번째 비트가 켜져 있는지 확인하면 됩니다.

→ 현재 누적된 arr[0]은 1000'1000b로 10진수로는 "136" 이다.

 

배열 int 타입으로 32bit까지 담을 수 있기에

원소 한개가 32개의 숫자를 중복 검사할 수 있다.

    0 ~ 31 → arr[0] → 1 × 32 까지 표현

    32 ~ 63 → arr[1] → 2 × 32 까지 표현

    64 ~ 95 → arr[2] → 3 × 32 까지 표현

 

N의 범위는 33,554,432 (= 2^25)까지 32(= 2^5)으로 나누었을 때,

배열 크기가 1,048,576 (= 2^20) 정도의 크기가 필요하다.

비트연산 Ver.

#include <stdio.h>

int arr[(1 << 20) + 2];
int N, idx, shift;

int main()
{
    // freopen("input.txt", "r", stdin);
    while (scanf("%d", &N) != EOF)
    {
        idx = N / 32;
        shift = N % 32;
        
        if (arr[idx] & (1 << shift))
            continue;

        printf("%d ", N);
        arr[idx] += (1 << shift);
    }
}

 

bitset Ver.

비트연산은 STL 중 bitset을 통해서도 구현할 수 있다.

[C++] [STL] bitset

#include <bitset>
#include <iostream>

using namespace std;

const int MAX_N = 33554432;
bitset<MAX_N> bs; // 000....000 (MAX_N bits)

int N;

int main()
{
	// freopen("input.txt", "r", stdin);
	// 입력이 없을 때까지 (EOF)
	while (~scanf("%d", &N))
	{
		//  시켜서 한개라도 1인지 확인
		if (!bs[N])
		{
			printf("%d ", N);
		}
		
		// 중복 표시
		bs[N] = 1;
	}
}