10816: 숫자 카드2

문제 링크: https://www.acmicpc.net/problem/10816

 

유튜브 해설:https://youtu.be/uGyJZPWrPlY

 

 

 

---

Q&A

질문

import os

import io

reader = list(io.BufferedReader(io.FileIO(0),1<<17))

problem1,problem2 = reader[1],reader[3]

for i in problem1:

    print(i)

이렇게 하면 이상한 값들이 나오는데 왜 그런거지?

 

답변

작성하신 코드는 표준 입력(0)에서 데이터를 읽어올 때 일반적인 문자열(String)이 아니라 바이트(Bytes) 형태로 데이터를 가져오기 때문입니다.

 

io.FileIO(0)와 io.BufferedReader를 사용해 읽어온 데이터(예: problem1)는 b'hello\n'와 같은 바이트 객체(Bytes object)가 됩니다.

 

파이썬에서 바이트 객체를 for 문으로 순회(for i in problem1:)하면, 각 문자가 그대로 출력되는 것이 아니라 해당 문자의 아스키코드(ASCII) 정수값 🔢 (예: 65, 97 등)을 하나씩 반환합니다.

데이터를 문자열로 바꿀 때는 .decode()를 사용하는 것이 맞습니다.

---

 

질문

import sys

reader = sys.stdin.readline

n=input()

problem1=input().split()

m=input()

problem2=input().split()

보다 빠른가?

 

답변
io 모듈 방식 (첫 번째 방식): 운영체제 수준에서 한꺼번에 큰 덩어리(chunk)로 데이터를 읽어오기 때문에 파이썬에서 사용할 수 있는 가장 빠른 입력 방식 중 하나입니다. 중간 단계 없이 통째로 가져오기 때문에 속도가 극대화됩니다.

 

sys.stdin.readline 방식 (두 번째 방식): 줄바꿈 문자 기준으로 한 줄씩 읽어오는 방식입니다. 기본 input()보다는 훨씬 빠르며, 대부분의 알고리즘 문제에서 시간 초과를 피하기 위한 가장 표준적이고 읽기 쉬운 방식으로 쓰입니다.

 

결론적으로 데이터를 읽어오는 절대적인 속도 자체는 질문자님이 작성하신 첫 번째 io 모듈 방식이 더 빠릅니다. 불필요한 변수(n, m)를 할당하지 않고 인덱스로 바로 접근하는 것도 효율적이고요.

 

---

질문
decode로 바꾸고 나중에 출력할 때 encode()를 하더라도 이게 더 빠르다는거지?

 

답변
decode()와 encode() 과정을 거치는데도 더 빠른 이유는 파이썬에서 입출력 속도를 늦추는 가장 큰 원인이 '데이터 변환' 자체가 아니라 '한 줄씩 반복해서 읽어오는 작업(오버헤드)'이기 때문입니다.

 

sys.stdin.readline: 매번 줄바꿈 문자(\n)를 찾으며 한 줄씩 파이썬의 문자열 객체로 처리합니다. 10만 줄의 데이터라면 이 무거운 작업을 10만 번 반복해야 합니다.

 

io 모듈 (바이트 통째로 읽기): 운영체제에서 아주 큰 덩어리의 데이터를 한 번에 메모리로 가져온 뒤, 덩어리째로 decode()를 단 한 번(또는 소수)만 수행합니다. 이 과정은 내부적으로 C 언어 레벨에서 고도로 최적화되어 한 번에 처리되므로 매우 빠릅니다.

 

---

질문
어떻게 io.BufferedReader(io.FileIO(0),1<<17)로 바이트로 받는것보다 read()가 더 빠를 수가 있지?

 

답변

순수하게 데이터를 메모리로 가져오는 속도(I/O) 자체만 놓고 보면, 질문자님이 처음에 쓰셨던 바이트로 읽어오는 방식이 가장 빠릅니다. 📦 운영체제에서 문자열 변환(디코딩) 없이 날것 그대로 가져오기 때문입니다.

 

하지만 알고리즘 문제에서는 데이터를 통째로 가져오는 것으로 끝나지 않고, 공백을 기준으로 숫자들을 잘라내서 리스트로 만들어야(파싱) 합니다. 여기서 최종 속도의 차이가 발생합니다. ⚙️

 

바이트로 읽은 후 직접 자르기: 가져온 바이트 안에서 파이썬 for 문 등으로 공백을 일일이 찾아 자르는 코드를 작성하면, 파이썬 언어 자체의 반복문 실행 속도(오버헤드) 때문에 오히려 전체 실행 시간이 길어집니다.

 

sys.stdin.read().split() 사용하기: 바이트를 문자열로 변환하는 시간은 약간 추가되지만, 데이터를 자르는 .split() 기능이 내부적으로 C 언어로 고도로 최적화되어 있습니다. 그래서 파이썬 레벨에서 직접 바이트를 다루는 코드를 짜는 것보다 훨씬 빠르고 깔끔하게 숫자들을 분리해 냅니다.

 

---

 

질문

[3, 0, 0, 1, 2, 0, 0, 2]

Traceback (most recent call last):

File "/tmp/main.py", line 2, in <module>

import user_code

File "/tmp/user_code.py", line 21, in <module>

solve(problem1,problem2)

File "/tmp/user_code.py", line 18, in solve

sys.stdout.write(' '.join(answer))

^^^^^^^^^^^^^^^^

TypeError: sequence item 0: expected str instance, int found

이거 왜 안돼?

 

 

답변
answer 리스트 [3, 0, 0, 1, 2, 0, 0, 2]를 보면 안의 값들이 모두 따옴표가 없는 정수(Integer)입니다. 문자열이 아니기 때문에 join 함수가 합치지 못하고 에러를 발생시킨 것입니다.

 

---

 

질문
왜 dict_problem의 값이 str이 아닌거지? 입력 받으면 str로 받잖아 나는 이걸 int로 변경한 적이 없는데?

 

답변

.count() 함수에 숨어있습니다. 🔍 파이썬의 problem1.count(x)는 리스트 안에 특정 문자열이 '몇 개' 있는지 세어주는 역할을 하죠. '개수'를 세는 것이기 때문에 이 함수의 결과값은 태생적으로 정수(int) 🔢가 될 수밖에 없습니다.

 

 

---

 

질문

 for i in problem2:

        if i in dict_problem1.keys():

            answer.append(dict_problem1[i])

        else :

            answer.append(0)

    sys.stdout.write(' '.join(list(map(str,answer))))

    return 

     for i in problem2:

        if i in dict_problem1.keys():

            answer.append(str(dict_problem1[i]))

        else :

            answer.append('0')

    sys.stdout.write(' '.join(answer))

    return 

둘 중 뭐가 더빠르지?

 

 

답변
값을 찾을 때마다 문자열로 바로 리스트에 넣고 마지막에 한 번만 합치는(join) 두 번째 방식이 코드를 두 번 도는 map 함수 사용보다 미세하게 더 빠르고 직관적입니다.

 

tip:
파이썬 딕셔너리에서 특정 키가 존재하는지 확인할 때 .keys()를 굳이 호출하면 불필요한 함수 호출(오버헤드)이 발생합니다.
그냥 if i in dict_problem1: 이라고 쓰는 것이 더 빠르고 자연스러운 문법

 

---

 

질문
if i in dict_problem1 이렇게 하면 i는 key랑 비교 되나 value랑 비교 되나?

그리고 if문으로 하는 것 보다get()이 더 빠른가?

 

답변

if i in dict_problem1:을 사용하면 i는 딕셔너리의 키(Key)와 비교됩니다.

 

파이썬의 딕셔너리는 키를 기준으로 데이터를 아주 빠르게 찾도록 만들어진 해시 테이블(Hash Table) 🗄️ 구조이기 때문에, in 연산자는 기본적으로 키(Key) 공간만 검색합니다.

 

속도 측면에서도 .get() 메서드를 사용하는 것이 더 유리합니다! ⚡ 그 이유는 '탐색 횟수'에 있습니다.

작성하셨던 if-else 방식을 살펴보겠습니다.

 

if i in dict_problem1: (키가 존재하는지 1차 탐색)

dict_problem1[i] (존재한다면 값을 꺼내기 위해 2차 탐색)

이렇게 같은 키를 찾기 위해 딕셔너리를 두 번 뒤져야 하는 불필요한 과정(오버헤드)이 발생합니다.

 

반면 .get(키, 기본값)을 사용하면 딕셔너리를 단 한 번만 탐색합니다. dict_problem1.get(i, 0)이라고 작성하면, "키 i를 찾아서 값을 돌려주고, 만약 키가 없다면 기본값인 0을 돌려줘"라는 작업을 한 번의 과정으로 끝내버리죠. 4줄짜리 코드가 깔끔하게 한 줄로 줄어드는 것은 덤입니다.

 

---

 

질문

    for i in problem2:

        answer.append(str(dict_problem1[i]) if dict_problem1.get(i) else '0')

    sys.stdout.write(' '.join(answer))

이렇게 하는게 빨라 아니면

answer.append(str(dict_problem1.get(i,0)))

이렇게 하는게 빨라?

 

답변

두 번째 방식인 answer.append(str(dict_problem1.get(i, 0)))이 속도도 더 빠르고 훨씬 깔끔한 파이썬 스타일(Pythonic) 코드입니다!

 

두 번째 코드는 파이썬 내부의 고도로 최적화된 C 언어 엔진을 통해 '탐색'과 '기본값 할당'을 단 한 번의 연산으로 끝냅니다. 반면 if-else를 쓰면 파이썬 언어 레벨에서 조건문을 한 번 더 평가해야 하므로 연산 단계가 늘어나 미세하게 더 느려집니다.

 

---

 

질문
내장함수로 처리하는게 웬만해서는 빠른 것 같네

 

답변
정확한 통찰입니다! 파이썬의 내장 함수와 표준 라이브러리들은 내부적으로 C 언어로 고도로 최적화되어 있기 때문에, 파이썬에서 직접 반복문을 짜는 것보다 압도적으로 빠르게 동작합니다

 

이 문제에 사용할 수 있는 내장 함수는 바로 collections 모듈의 Counter 라는 클래스입니다! 🧮

이름 그대로 리스트 안의 데이터가 각각 몇 개씩 있는지 순식간에 세어서, 우리가 그토록 원했던 딕셔너리 형태로 한 번에 만들어주는 마법 같은 도구죠.

 

작동 원리는 아주 단순하면서도 강력합니다. 리스트를 처음부터 끝까지 딱 한 번만 순회하면서(O(N) 속도) 개수를 셉니다. 아까 우리가 걱정했던 50만 번 × 50만 번의 악몽 같은 탐색 시간을 단 50만 번으로 확 줄여주는 일등 공신이에요. 내부적으로 C 언어로 최적화되어 있어 속도도 엄청나게 빠릅니다.

 

예시

from collections import Counter

cards = ['A', 'B', 'A', 'C', 'B', 'A']
card_counts = Counter(cards)

# 결과: Counter({'A': 3, 'B': 2, 'C': 1})

 

 

---

나의 정답

import sys


reader = sys.stdin.read().split('\n')
problem1,problem2 = reader[1].split(),reader[3].split()

def solve(problem1,problem2):
    from collections import Counter
    answer=[]
    dict_problem1=Counter(problem1)


    for i in problem2:
        answer.append(str(dict_problem1.get(i,0)))
    sys.stdout.write(' '.join(answer))
    return 

solve(problem1,problem2)

---

다른 사람의 풀이

import sys

sys.stdin.readline() 
input_data = map(int,sys.stdin.readline().rstrip().split(" "))
sys.stdin.readline() 
count_data = map(int,sys.stdin.readline().rstrip().split(" "))

card_dict = {}

for n in input_data:
    if n in card_dict:
        card_dict[n]+=1
    else:
        card_dict[n]=1


result = ""

for c in count_data:
    if c in card_dict:
        sys.stdout.write(str(card_dict[c]))
        sys.stdout.write(" ")
    else:
        sys.stdout.write("0 ")

---

다른 사람의 풀이2

N = int(input())
A=[0] * 20000000
a=list(map(int,input().split()))
for i in range(len(a)):
  A[a[i]]=A[a[i]]+1

M = int(input())
b=list(map(int,input().split()))
B=[]
for i in range(len(b)):
  B.append(A[b[i]])
for i in range(len(B)):
  print(B[i],end=" ")

 

 

---