[Coding Test][Python][백준] BOJ #11723 집합 (input() vs sys.stdin.readline())

#11723 집합

문제)

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

• add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
• remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
• check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
• toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
• all: S를 {1, 2, ..., 20} 으로 바꾼다.
• empty: S를 공집합으로 바꾼다.

입력)

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

출력)

check 연산이 주어질때마다, 결과를 출력한다.

---

풀이)

M = int(input())

s = set()

for i in range(M):
    line = input()
    if line == 'all':
        s = set([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20])
    elif line == 'empty':
        s = set()
    else:
        operation, num = line.split()
        num = int(num)

        if operation == 'add':
            s.add(num)
        elif operation == 'remove':    
            # remove, pop 모두 element가 없으면 error
            s.discard(num)
        elif operation == 'check':
            print(1 if num in s else 0)
        elif operation == 'toggle':    
            if num in s:
                s.remove(num)
            else:
                s.add(num)

 

위의 코드로 작성하였을 때 시간 초과가 났었습니다.

이는 input()의 동작 방식 때문에 M이 3,000,000에 가까운 Input이 들어왔을 때 시간초과가 났을 것입니다.

따라서 아래처럼 sys 라이브러리를 통해 sys.stdin.readline을 사용하여 입력을 처리해야 시간초과가 나지 않습니다.

input()과 sys.stdin.readline()에 대한 자세한 설명은 아래에 있습니다.

import sys

input = sys.stdin.readline

M = int(input())

s = set()

for i in range(M):
    line = input().strip()
    if line == 'all':
        s = set([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20])
    elif line == 'empty':
        s = set()
    else:
        operation, num = line.strip().split()
        num = int(num)

        if operation == 'add':
            s.add(num)
        elif operation == 'remove':    
            # remove, pop 모두 element가 없으면 error
            s.discard(num)
        elif operation == 'check':
            print(1 if num in s else 0)
        elif operation == 'toggle':    
            if num in s:
                s.remove(num)
            else:
                s.add(num)

 

---

※ input() vs sys.stdin.readline()

• input()
  • 내부적으로 sys.stdin.readline().rstrip("\n") 을 호출하여 개행 문자를 자동으로 제거
  • 하지만 여기서 내부적으로 추가적인 I/O 처리를 포함하여 시간이 오래 걸린다.
  • 입력 버퍼에서 한 줄을 읽고, 문자열 처리를 위한 추가적인 계층이 적용된다.
• sys.stdin.readline()
  • C에서 제공하는 표준 입출력 라이브러리(stdin.h)의 fgets()와 유사한 방식으로 동작
  • 즉, 입력 버퍼에서 한 번에 읽어와 Python 문자열 객체로 변환
  • Python 내부의 추가적인 입력 처리 계층을 거치치 않기 때문에 빠르다
• input() vs sys.stdin.readline().strip()
  • sys.stdin.readline().strip()을 사용하면 input()과 유사하게 동작하지만 더 빠를 가능성이 크다.
  • 왜냐하면 input()은 내부적으로 입력 버퍼에서 데이터를 가져오고 Parsing하는 추가적인 Python 레이어를 거치기 때문에 더 느릴 가능성이 크다.

아래의 코드를 통해 확인할 수 있습니다.

import sys
import time

time.sleep(3)

# sys.stdin.readline()
start = time.time()
for _ in range(1000):
    line = sys.stdin.readline().strip()
end = time.time()
sys_time = end - start


# input()
start = time.time()
for _ in range(1000):
    line = input()
end = time.time()
input_time = end - start

print("sys.stdin.readline().strip() :", sys_time)
print("input() :", input_time)

sys.stdin.readline().strip() : 0.0753941535949707
input() : 0.14739608764648438