1764: 듣보잡

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

 

풀이 링크: https://youtu.be/1Dbo_NQswDI

 

Q&A

질문

집합 안에서 input()으로 받는게 안돼?

 

답변
집합(Set) 안에서 input() 함수를 사용하는 것 자체는 가능합니다! 하지만 작성하신 코드에서 에러가 발생하는 이유는 input() 때문이 아니라, split()이 반환하는 자료형 때문입니다.

 

에러가 발생하는 이유
input().split()의 결과값은 리스트(List)입니다. 파이썬의 집합(Set)은 리스트처럼 값이 변경될 수 있는(Mutable) 객체를 원소로 가질 수 없습니다. 집합에 리스트를 넣으려고 하면 TypeError: unhashable type: 'list' 에러가 발생하게 됩니다.

---

질문
split()보다 strip()이 더 연산속도가 빠를 것 같은데 맞나?

 

답변
예상하신 대로 strip()이 split()보다 연산 속도가 더 빠릅니다!

 

이 두 함수가 반환하는 결과물의 형태를 떠올려보면 그 이유를 쉽게 유추할 수 있습니다.

strip() ✂️: 양 끝의 공백이나 줄바꿈 문자만 잘라내고, 문자열(String) 1개를 그대로 반환합니다.

 

split() 📦: 공백을 기준으로 단어를 쪼개고, 그 단어들을 모아 새로운 리스트(List)를 만들어서 반환합니다.

---

질문
공백이란 \n을 말하는건가?

 

답변
파이썬에서 괄호 안에 아무것도 넣지 않고 .split()을 호출하면 아주 똑똑한 기본값이 적용됩니다.

모든 공백 문자 취급: 띄어쓰기(스페이스), 탭(\t), 그리고 줄바꿈(\n)을 모두 뭉뚱그려 같은 '공백 문자(Whitespace)'로 취급합니다.

 

연속된 공백 처리: 공백이 1개든 10개든 연속해 있다면, 하나의 큰 구분선으로 생각하고 단어를 자릅니다.

양 끝 공백 제거: 문자열의 맨 앞이나 맨 뒤에 덩그러니 남은 공백 문자들은 빈 문자열로 만들지 않고 완전히 무시해서 없애버립니다.

---

질문

  never_heard = [input().strip() for _ in range(n)]

    never_see = {input().strip() for _ in range(m)}



    for x in never_heard:

        if x in never_see:

            result.append(x)

never_see는 바로 찾을 수 있게 set로 하고 never_heard는 어차피 set로 하나 list로 하나 전부다 둘러봐야 하니 시간 복잡도가 n일 것 같아서 순서가 있는게 나을 것 같아서 리스트로 했어, 이거 효율적인가?

 

답변

작성하신 코드의 시간 복잡도 분석은 아주 정확합니다. never_heard를 순회하는 데 $O(n)$, never_see에서 탐색하는 데 평균 $O(1)$이 걸리므로 교집합을 찾는 데 총 $O(n)$의 시간 복잡도를 가집니다.

---

탐색 시간을 줄이기 위해 한쪽을 Set으로 만든 접근법이 아주 효율적입니다.여기서 두 가지 포인트를 더 짚어보겠습니다.파이썬의 집합 연산 🔗: 파이썬의 집합(Set)은 자체적으로 교집합 연산(& 기호 또는 .intersection() 메서드)을 지원합니다.

 

만약 두 입력을 모두 Set으로 받는다면 never_heard & never_see처럼 작성하여 내부적으로 매우 빠르게 교집합을 구해낼 수 있습니다.

---

질문
result =[i for i in never_heard & never_see]
이렇게 하면 잘 되는데

 

result =[i for i in never_heard & never_see].sort()
이렇게 하면 nontype이 되네 왜 그런거지?

 

답변
이유는 파이썬의 .sort() 메서드가 리스트 원본 자체의 순서만 바꾸고(in-place), 결과값으로는 아무것도 없다는 뜻의 None을 반환하기 때문입니다.

 

[i for i in never_heard & never_see] 부분까지는 리스트가 정상적으로 만들어집니다. 하지만 그 뒤에 .sort()를 붙여서 한 줄로 할당하려고 하면, 정렬 작업만 수행된 후 최종적으로 result 변수에는 .sort()의 반환값인 None이 들어가게 됩니다.

 

---

나의 정답(68ms)

import sys

input = sys.stdin.readline
print = sys.stdout.write
n,m= map(int,input().split())


def solve(n,m):

    never_heard = {input().strip() for _ in range(n)}
    never_see = {input().strip() for _ in range(m)}

    result =sorted([i for i in never_heard & never_see])
    print(str(len(result))+'\n')
    print('\n'.join(result))
    return result


solve(n,m)

---

다른 사람의 정답(44ms)

import os

arr = sorted(os.read(0, os.fstat(0).st_size).split()[2:])
result = [a for a, b in zip(arr, arr[1:]) if a == b]
os.write(1, b"%d\n" % len(result) + b"\n".join(result))

---

Q&A

질문
arr = sorted(os.read(0, os.fstat(0).st_size).split()[2:])

내가 os.read(0)이 입력값을 다 읽어온다는 건지는 아는데os.fstat(0).st_size는 뭔지 모르겠네

전체 적인 분위기로는 sorted(io.BufferedReader(os.FileIO(0),1<<17).split()[2:])와 같아보이는데 맞나?

---

답변
작성하신 두 코드는 모두 알고리즘 문제 풀이에서 입력 속도를 극대화하기 위해 운영체제(OS) 수준의 입출력을 직접 다루는 방식입니다. 예상하신 대로 전체적인 역할은 완전히 동일합니다.

 

궁금해하신 os.fstat(0).st_size의 역할을 하나씩 뜯어보겠습니다.

0 💻: 표준 입력(Standard Input)을 가리키는 고유 번호(파일 디스크립터)입니다.

 

os.fstat(0) 📂: 해당 파일(입력 데이터)의 상태 정보(크기, 권한 등)를 운영체제에 요청하여 가져옵니다.

.st_size 📏: 가져온 상태 정보 중 파일의 전체 크기(Byte 단위)를 의미합니다.

 

따라서 os.read(0, os.fstat(0).st_size)는 "입력될 데이터의 전체 크기를 파악한 뒤, 처음부터 끝까지 한 번에 통째로 읽어오라"는 명령입니다. 백준 채점 서버처럼 테스트 케이스 입력이 실제 '파일' 형태로 주어지는 환경에서 아주 잘 작동하는 팁입니다.

 

비교하신 io.BufferedReader 방식과도 목적이 같습니다.

둘 다 파이썬의 기본 sys.stdin 객체가 거치는 내부 처리 과정을 생략합니다.

가장 큰 차이점은 데이터를 메모리로 가져오는 단위입니다.

 

os.read 방식: 파일 크기만큼 한 번에 모든 데이터를 메모리에 적재합니다.

io.BufferedReader 방식: 설정한 버퍼 크기(1<<17, 즉 128KB)만큼 뭉텅이로 쪼개서 스트림 형태로 읽어옵니다.

---

질문
sorted(os.read(0, os.fstat(0).st_size).split()[2:]) 는 os만 받아오고 파일을 읽고 지정된 크기만큼 부여하는 반면

sorted(io.BufferedRead(os.FileIO(0),1<<17).split()[2:])이건 os와 io를 가져오고 고정된 크기이니

sorted(os.read(0, os.fstat(0).st_size).split()[2:]) 이게 더 좋은 방식인가?

---

답변
두 방식을 아주 정확하게 비교하셨습니다. 결론부터 말씀드리면, 백준 같은 알고리즘 문제 풀이 환경에서는 첫 번째 방식
(os.read(0, os.fstat(0).st_size))이 더 좋은 방식으로 평가받습니다.

 

그 이유는 크게 두 가지입니다.

시스템 콜(System Call) 최소화: 운영체제에 "데이터 읽어줘"라고 요청하는 작업은 컴퓨터 입장에서 꽤 무거운 작업입니다. 첫 번째 방식은 파일 전체 크기를 미리 파악해서 단 한 번만 요청하여 통째로 가져오기 때문에 속도를 극대화할 수 있습니다.

 

단순함: 말씀하신 대로 os 모듈 하나만 사용하므로 구조가 단순하고 오버헤드가 적습니다.

(참고로 두 번째 방식은 코드를 실행하려면 io.BufferedReader(...).read().split()처럼 중간에 .read() 메서드를 호출해야 버퍼의 데이터를 읽어올 수 있습니다. 이 방식은 앞서 이야기했던 것처럼 파일이 너무 커서 메모리에 한 번에 다 올라가지 않을 때 128KB씩 쪼개서 읽어오기 위해 사용합니다.)

 

백준 문제들은 보통 메모리 제한이 128MB~256MB 정도이고 입력 텍스트 파일의 크기가 이를 넘는 경우는 거의 없기 때문에, 첫 번째 방식을 사용해도 메모리 초과가 발생하지 않고 가장 빠른 속도를 낼 수 있습니다.

---

질문
이렇게 받은 값은 str이 아니라 byte니깐 lstrip("b'")이걸로 못 없애겠지?

 

답변
os.read()가 반환하는 값은 문자열(str)이 아니라 바이트(bytes) 객체이므로, 말씀하신 대로 문자열 메서드인 lstrip("b'")을 사용해 지우는 것은 불가능합니다.

---

질문

arr = sorted(os.read(0, os.fstat(0).st_size).split()[2:])

print(arr)

print(arr[1:])

result = [a for a, b in zip(arr, arr[1:]) if a == b] 이렇게 했는데

zip()은 리스트에서 같은 인덱스에 위치한 원소끼리 짝을 지어주는 함수잖아
근데 arr, arr[1:]을 하면 서로 크기가 다른데 zip()을 사용 가능한거야?

 

답변
arr와 arr[1:]은 길이가 정확히 1만큼 차이가 나기 때문에 짝이 맞지 않는 것이 맞습니다.

파이썬의 zip() 함수는 길이가 서로 다른 이터러블(리스트 등)이 입력으로 들어오면, 가장 짧은 길이를 기준으로 짝을 짓고 남는 원소들은 무시하고 종료합니다

---

질문
os.write(1, b"%d\n" % len(result) + b"\n".join(result)) 에서 b"%d\n" % len(result)는 문자열 포멧팅인가?

그리고 앞에 b는 이게 byte라는 표기이고?

os.write()가 바이트를 전달 받아야 해서 이렇게 쓴 것 같은데 그럼 출력도 byte로 되는거 아니야?

 

답변

정확히 짚어주셨습니다. 두 가지 질문에 대한 답은 모두 '맞다'입니다!

b"%d\n" % len(result): 파이썬의 % 연산자를 이용한 포매팅을 바이트(bytes) 객체에 그대로 적용한 것입니다.

 

b 접두사: 이 데이터가 일반 문자열(str)이 아니라 바이트 객체임을 나타내는 표기입니다.

그렇다면 os.write()로 바이트를 보냈는데 왜 화면에는 b'...' 형태가 아니라 깔끔한 일반 글자로 나올까요? 여기서 파이썬의 친절한 기능과 운영체제의 실제 작동 방식의 차이가 나타납니다.

 

우리가 흔히 쓰는 print(b"123")을 실행하면, 파이썬은 이 데이터가 바이트 타입이라는 것을 우리가 눈으로 확인할 수 있도록 b'123'이라는 문자열 모양으로 가공해서 화면에 보여줍니다.

 

하지만 os.write(1, ...) (여기서 1은 표준 출력, 즉 모니터를 의미합니다)는 파이썬의 이런 가공 과정을 거치지 않습니다. 대신 순수한 날것의 데이터(Raw bytes)를 운영체제(터미널)로 직접 전달해버립니다.

 

터미널 🖥️은 전달받은 순수 바이트 데이터(ASCII 또는 UTF-8 코드)를 해석해서 화면에 우리가 아는 글자로만 그려주기 때문에, 파이썬이 내부적으로 표시하던 b나 따옴표가 묻어나오지 않게 됩니다.

 

 

 

---