[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 13701번 _ 중복 제거

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

13701번: 중복 제거

[문제]

문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때,

1. 0 ≤ Ai < 225 = 33554432, i=1,2,…,N.
2. 입력의 개수 N은 1 이상 500만 이하이다.

[입력]

첫째 줄에 A1, A2, ..., AN이 주어진다.

[출력]

B1, B2, ..., BN’을 출력한다.

 

[아이디어]

1) 풀었다기 보다는 비트마스킹의 개념을 이해하기 위해 다른 사람의 코드를 공부했다.

-> 집합의 원소 위치를 이진수로 표현하고 비트 연산(& or |)을 통해 원소의 등장 여부를 판단할 수 있다. 꼭 이진수로 하지 않더라도 int 표현과 비트 연산자로도 동일한 표현이 가능해보인다.

2) 본래 C++을 위해 설계된 문제로, 파이썬으로 풀기에 적합하지 않다.

3) 아이디어 자체는 동일한데, 비트 연산을 활용해 배열의 한 칸에 하나의 숫자를 관리하는 것이 아니라 복수의 수의 등장 여부를 저장하여 메모리를 아끼는 것이 핵심이다. 다른 블로그의 설명을 통해 이해했다. (참고)

 

s=map(int,input().split())
p=2**5
t=[0]*(2**25//p)
for x in s:
    idx=x//p
    val = 1 << (x % p)
    if not (t[idx]&val):
        t[idx]+=val
        print(x,end=' ')

로직은 대충 위와 같은데, 통과되는 코드는 아니다. 32로 나눈 몫이 같은 32개의 정수를 idx 위치의 값으로 트래킹하며, 비트연산 &가 0이 아닌 경우 동일한 정수가 재등장했다고 판단한다. 통과가 되지 않는 이유는 파이썬이 파일을 읽어오는 방식 때문이라고 하는데, 억지로 풀기 위해서는 강제로 비트 단위로 읽어올 수 있도록 제어해줘야한다고 한다. 이 부분은 상세히 다 이해하지는 못했고, 그냥 이런게 있구나 보는 정도로 만족했다.

import sys
import os

def read_word():

    unstdin = os.fdopen(sys.stdin.fileno(), 'rb', buffering=1000000)
    ch = unstdin.read(1)
    while True:
        num = 0
        while not (ch == b'\n' or ch == b'' or (ch >= b'0' and ch <= b'9')):
            ch = unstdin.read(1)
        if ch == b'\n' or ch == b'':
            break
        while ch >= b'0' and ch <= b'9':
            num = num * 10 + int(ch)
            ch = unstdin.read(1)
        yield num

def set_bit(n):
    nn = n // 8
    nr = n % 8

    ret = (bits[nn] & (1 << nr)) == 0

    bits[nn] |= (1 << nr)

    return ret

if __name__ == '__main__':
    bits = bytearray(4194304)

    try:
        sys.stdin = open("13701_input.txt")
    except FileNotFoundError:
        pass

    for num in read_word():
        if set_bit(num) == True:
            print(num, end=" ")
    print()

메모리 제한을 지키기 위해 한 글자씩 읽어오도록 강제한 것이 인상적이다. 그냥 빡고수,,