백준 13701번 : 중복 제거 (Python)

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

import sys
arr = bytearray(2**22)
s = ""
while True :
    c = sys.stdin.read(1)
    if c.isnumeric() :
        s += c
    else :
        n = int(s)
        d = n // 8
        r = n % 8
        if not arr[d] & (1 << r) :
            print(n, end=' ')
            arr[d] |= 1 << r
        s = ""
        if c != " " :
            break

크게 입력과 중복 확인, 두 파트로 나누어 문제를 해결한다.

 

1. 입력

8mb인 메모리 제한과 최대 500만개의 입력값 때문에 입력을 한번에 받을 수 없다.
따라서 sys.stdin.read(1)을 사용해 문자 1개씩 쪼개서 입력받는다.
c에는 (문자 형태의) 정수, 공백, 혹은 마지막에 줄바꿈 문자가 입력된다.
c.isnumeric()으로 정수가 입력되는지 확인해서 s에 순서대로 저장한다.

 

2. 중복 확인
정수 입력이 끝났으면 n = int(s)가 앞에서 들어온 숫자인지 확인한다.
문제의 태그가 알려주듯 비트마스킹으로 입력 받은 숫자의 집합을 표시해야 하는데, 
그냥 1 << n 으로 확인하려면 2^25이라는 범위 때문에 메모리 초과가 발생한다.
먼저 길이 2^22 인 bitarray를 생성.
bitarray 자료형에는 각 인덱스마다 0 <= x < 256(=2^8) 범위의 정수를 담을 수 있다.(=1bit)
즉 전체 bitarray는 2^22 * 8 = 2^25까지의 숫자 집합을 표시할 수 있음
arr[0]에는 0부터 7까지 값이 들어왔는지 저장, arr[1]에는 8부터 15까지 ... 이런 식으로
따라서 n을 8로 나눠 몫을 d, 나머지를 r이라 하면,
d는 n이 들어갈 bitarray 인덱스, r은 해당 칸에서 n의 위치가 된다.
arr[d]에 r이 있는지 확인해서 없으면 n을 출력하고 1 << r로 넣어준다.
마지막으로 입력 받은 값이 정수도, 공백도 아니라면 마지막의 줄바꿈 문자이므로 break를 넣어준다.