BOJ 13701 중복 제거

By kuper0201

Published in 알고리즘

2023-05-25

1 min read

문제

입력

풀이

문제

BOJ 13701 중복 제거 바로 가기

N개의 정수 $A_{1}, A_{2}, ..., A_{N}$ 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 ${N}'$ 개의 수 $B_{1}, B_{2}, ..., B_{{N}'}$ 을 입력된 순서대로 출력하시오. 이때,

$0 ≤ A_{i} < 2^{25} = 33554432, i=1,2,…,N.$
입력의 개수 N은 1 이상 500만 이하이다.

입력

첫째 줄에 $A_{1}, A_{2}, ..., A_{N}$ 이 주어진다.

풀이

$A_{i}$ 에 입력 가능한 숫자의 크기는 $2^{25}$ 이므로 32bit인 정수형으로 나타 낼 수 있다. 입력의 개수는 500만 이하라고 하였으므로 32bit를 기준으로 약 20MB의 메모리가 필요하다는 것을 알 수 있다. 하지만 해당 문제의 메모리 제한은 8MB이므로 20MB의 메모리를 사용하게 되면 메모리 초과가 발생할 것이다.

이러한 문제를 해결하기 위해서 비트 마스킹(Bit Masking)이라는 기법을 이용해야 한다.

비트 마스킹이란 하나의 숫자를 하나의 비트에 대응시켜 표현하는 것을 말한다.

예를 들어 정수 10을 16bit 자료형으로 나타내면 아래와 같다.

0b0000000000001010

하나의 정수를 나타내는데 하나의 16bit 자료형을 사용해야 한다.

하지만 16bit 자료형의 10번째 비트만을 1로 바꾸어 저장하게 되면 아래와 같이 하나의 비트만을 이용해 10이라는 정수를 표현 할 수 있게 된다.

0b0000001000000000

위와 같이 표현하면 하나의 16bit 자료형을 이용해 16개의 정수를 표현 할 수 있다.

입력 가능한 최대값은 33,554,432이므로 이를 32bit로 나누면 1,048,576개의 int가 필요하다. 이는 약 4MB로 메모리 제한을 충족하며 모든 수를 나타낼 수 있다.

코드 보기(Java)

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        // 33,554,432 / int(32bit)
        int[] bit = new int[1048576];

        String[] s = br.readLine().split(" ");
        for(String str : s) {
            int M = Integer.parseInt(str);
            int idx = M / 32; // 배열의 idx번째
            int sft = (1 << (M % 32)); // idx번째 배열의 sft번째 비트

            // 존재하지 않으면 출력, 비트 설정
            if((bit[idx] & sft) == 0) {
                sb.append(str + " ");
                bit[idx] |= sft;
            }
        }

        System.out.println(sb);
    }
}

코드 보기(C++)

#include <iostream>

#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
#define endl '\n'

using namespace std;

int main() {
    fastio;
    
    // 33,554,432 / int(32bit)
    int bit[1048576] = {0, };
    
    int M;
    while(cin >> M) {
        int idx = M / 32; // 배열의 idx번째
        int sft = (1 << (M % 32)); // idx번째 배열의 sft번째 비트

        // 존재하지 않으면 출력, 비트 설정
        if((bit[idx] & sft) == 0) {
            cout << M << " ";
            bit[idx] |= sft;
        }
    }
    
    return 0;
}

코드 보기(Kotlin)

fun main(args: Array<String>) = with(System.`in`.bufferedReader()) {
    var sb = StringBuilder()

    // 33,554,432 / int(32bit)
    var bit = Array<Int>(1048576, {0})
    
    var s = readLine().split(" ")
    for (str in s) {
        var M = str.toInt()
        var idx = M / 32 // 배열의 idx번째
        var sft = (1 shl (M % 32)) // idx번째 배열의 sft번째 비트

        // 존재하지 않으면 출력, 비트 설정
        if((bit[idx] and sft) == 0) {
            sb.append(str +" ")
            bit[idx] = bit[idx] or sft
        }
    }
    
    println(sb)
}

코드 보기(Python)

Python을 이용하여 로직을 구현하면 정상적인 구현임에도 불구하고 메모리 초과가 발생한다.
Python의 입력 함수는 입력 데이터를 한 번에 모두 읽지 않고 사용자가 엔터 키를 누를 때까지 입력을 버퍼에 저장하고, 그 후에 한 줄씩 읽어온다.
이러한 동작을 버퍼링이라고 한다. 버퍼링을 수행하면 효율적인 입력이 가능하지만 입력을 받기 전에 버퍼에 모든 데이터를 저장해야 하므로 메모리를 사용한다.
따라서 해당 문제를 해결하기 위해서는 버퍼의 크기를 조절해 주어야 한다.
아래의 코드는 표준 입력을 파일 스트림으로 변환해 입력 함수의 버퍼 크기를 1000바이트로 조절한 코드이다.

import os
import sys

# 33,554,432 / int(32bit)
bit = [0] * 1048576

def setBit(M):
    global bit
    idx = M // 32  # 배열의 idx번째
    sft = (1 << (M % 32))  # idx번째 배열의 sft번째 비트

    # 존재하지 않으면 출력, 비트 설정
    if (bit[idx] & sft) == 0:
        print(M, end=' ')
        bit[idx] = bit[idx] | sft

def main():
    # 버퍼 크기를 1000바이트로 설정
    reader = os.fdopen(sys.stdin.fileno(), 'rb', 1000)
    while True:
        M = 0
        while True:
            ch = reader.read(1)
            if b'0' <= ch <= b'9':
                M = 10 * M + int(ch)
            elif ch == b' ':
                break
            else:
                setBit(M)
                exit()

        setBit(M)

if __name__ == "__main__":
    main()

코드 보기(Swift)

import Foundation

func main() {
    // 33,554,432 / int(32bit)
    var bit = [Int](repeating: 0, count: 1048576)
    
    var s = readLine()!.split(separator: " ")
    for str in s {
        var M = Int(str)!
        var idx = M / 32 // 배열의 idx번째
        var sft = (1 << (M % 32)) // idx번째 배열의 sft번째 비트

        // 존재하지 않으면 출력, 비트 설정
        if((bit[idx] & sft) == 0) {
            print(str, terminator: " ")
            bit[idx] = bit[idx] | sft
        }
    }
}

main()