28278:스택 2

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

유튜브:https://youtu.be/Hoai8QJuh3g

 

 

---

Q&A

질문
reader =os.read(0,os.fstat(0).st_size).split()랑 reader =os.read(0,os.fstat(0).st_size)의 reader의 내용물이 바뀌는데
split()은 그냥 공백을 제거하고 리스트로 바꿔주는 거일 텐데 왜 print(i)의 값이 바뀌는 거지?

 

답변
s.read() 함수는 데이터를 일반 문자열(str)이 아닌 바이트 객체(bytes) 형태로 반환합니다. 이 데이터 타입의 특성 때문에 두 코드의 출력 결과가 완전히 달라집니다.

 

split()을 사용한 경우: reader는 바이트 객체들이 담긴 리스트(list)가 됩니다 ([b'9', b'4', ...]). 리스트를 for문으로 순회하면 리스트 안의 요소인 바이트 객체 덩어리 자체가 그대로 출력됩니다. 📦

 

split()을 사용하지 않은 경우: reader는 쪼개지지 않은 하나의 거대한 바이트 객체(b'9\n4\n...')입니다. 파이썬에서 단일 바이트 객체를 for문으로 한 글자씩 순회하게 되면, 해당 문자가 가진 아스키코드(ASCII) 정수값을 반환하도록 설계되어 있습니다. 🔢

---

질문
result가 리스트고 reader가 리스트일 때

result.append(reader[i+1])

이렇게 하면 시간 복잡도가 O(reader[i+1])인가?

,즉 i+1 = n 이면 시간 복잡도가 O(n)이 되는거지 맞아?

 

답변
결론부터 말씀드리면, 해당 코드의 시간 복잡도는 $O(n)$이 아니라 $O(1)$ (상수 시간)입니다. ⏱️

이 한 줄의 코드는 사실 두 가지 동작으로 이루어져 있습니다.

하나씩 쪼개서 살펴보겠습니다.인덱싱 (reader[i+1]): 파이썬 리스트에서 특정 인덱스에 있는 값을 가져오는 작업입니다.
리스트는 데이터가 연속적으로 저장되어 있기 때문에, 찾고자 하는 인덱스 번호($i+1$)가 아무리 크더라도 단번에 해당 위치를 찾아갈 수 있어 항상 $O(1)$의 시간이 걸립니다.

 

추가하기 (result.append(...)): 리스트의 맨 마지막 끝에 요소 하나를 덧붙이는 작업입니다.
이 역시 기존 데이터들의 위치를 이동시킬 필요 없이 끝자리에 하나를 추가하기만 하면 되므로 평균적으로 $O(1)$의 시간이 소요됩니다.따라서 $i+1$의 값이 $n$이든, 100만이든 상관없이 이 두 작업의 조합에 걸리는 시간은 일정합니다.

---

질문
그럼 reader.pop(i) 도 시간복잡도가 O(1)인가?

 

답변
결론부터 말씀드리면, reader.pop(i)의 시간 복잡도는 일반적으로 $O(n)$입니다.
(단, 맨 마지막 요소를 뽑을 때인 reader.pop()은 예외적으로 $O(1)$입니다.)

 

파이썬의 리스트를 일렬로 빈틈없이 연결된 기차 칸 🚃이라고 상상해 보겠습니다.
중간에 있는 i번째 칸을 쏙 빼내면(pop(i)), 그 자리에 빈 공간이 생기게 됩니다.

 

리스트는 데이터가 연속적으로 이어져 있어야 하므로, 이 빈 공간을 채우기 위해 i번째 뒤에 있는 모든 기차 칸들을 앞으로 한 칸씩 당겨와야 합니다.

만약 뒤에 옮겨야 할 데이터가 100만 개라면 100만 번의 이동 작업이 필요하겠죠.

그래서 전체 데이터의 개수 $n$에 비례하여 시간이 늘어나는 $O(n)$이 되는 것입니다.

---

질문
입력이 1 2 3

reader =os.read(0,os.fstat(0).st_size)

이렇게 하면 result.append(reader[0]) 하고 또 reuslt.append(reader[0])을 하면 result=[b'1',b'2'] 가 들어 가잖아? 그럼 시간 복잡도가 어떻게 돼? 이건 스트림을 읽어오는 거니깐 O(1)인가?

 

답변
스트림(stream)의 개념과 메모리 접근 방식을 연결해서 생각해 볼 수 있는 중요한 질문입니다.먼저 os.read(0, os.fstat(0).st_size)의 동작 방식을 정확히 짚고 넘어갈 필요가 있습니다.

 

이 코드는 입력 스트림에서 데이터를 읽어오지만, 그 결과를 reader라는 변수에 한 번에 모두 저장해 버립니다. 즉, reader는 더 이상 한 글자씩 소비되는 흐르는 스트림이 아니라, 메모리에 고정된 하나의 거대한 바이트 객체(배열과 유사함)가 됩니다. 💾

 

따라서 reader[0]은 이미 메모리에 저장된 데이터의 특정 인덱스를 찾아가는 단순한 작업이므로 시간 복잡도는 생각하신 대로 $O(1)$이 맞습니다.

 

⏱️그런데 결과값이 [b'1', b'2']가 될 것이라고 예상하신 부분에는 함정이 숨어 있습니다. reader는 이미 값이 고정된 데이터이기 때문에, reader[0]을 아무리 여러 번 호출해도 다음 데이터로 알아서 넘어가지 않고 계속 같은 첫 번째 위치만 가리키게 됩니다.

 

---

질문
reader =open(0)은

이렇게 했을 때 [b'1', b'2']가 되나?

 

답변
open(0)을 사용하면 상황이 완전히 달라집니다! 결론부터 말씀드리면 [b'1', b'2']가 되지 않을 뿐만 아니라, 코드를 실행하면 에러가 발생합니다. 🚨

 

그 이유는 다음과 같습니다.

인덱싱 불가: open(0)은 표준 입력(Standard Input)을 텍스트 파일 객체(TextIOWrapper) 형태로 엽니다.

 

이는 메모리에 고정된 배열이 아니라, 데이터를 순차적으로 빨아들일 준비를 하고 있는 '빨대' 🥤나 '파이프'에 가깝습니다. 따라서 reader[0]처럼 인덱스를 사용해 특정 위치에 직접 접근하려고 하면 파이썬이 에러(TypeError)를 뱉어냅니다.

 

텍스트 모드: os.read와 달리 open()은 기본적으로 텍스트 모드('r')로 작동합니다. 따라서 데이터를 읽어오더라도 바이트 객체(b'1')가 아닌 일반 문자열('1') 형태로 가져오게 됩니다.

 

즉, open(0)으로 만든 파일 객체는 그 자체로는 리스트처럼 다룰 수 없고, 안에 있는 데이터를 '읽어내는' 별도의 동작이 필요합니다.

---

질문
read()도 파일 객체 형태로 가져오는거 아니였나?

 

답변
open(): 데이터를 가져올 수 있는 '통로'나 '빨대' 🥤 역할을 하는 파일 객체를 만듭니다.

(아직 데이터를 읽어 들이지는 않은 준비 상태입니다.)

 

read() (또는 os.read()): 그 통로를 통해 데이터를 쭉 빨아들여서 메모리에 올려놓은 실제 내용물 💧 (바이트 데이터나 문자열)을 반환합니다.

 

즉, os.read(0, ...)는 표준 입력(0번)에서 데이터를 직접 읽어와서 거대한 바이트 객체(데이터 그 자체)로 만들어준 것이고, open(0)은 표준 입력과 연결된 파일 객체(통로)만 만들어준 것입니다.

 

따라서 reader = open(0) 상태에서는 reader가 인덱싱(reader[0])이 불가능한 파일 객체일 뿐이므로, 그 안의 내용물을 보려면 데이터를 읽어내는 추가 동작이 필요합니다. 방금 질문에서 언급하신 read()가 바로 그 역할을 하는 메서드 중 하나입니다!

---

질문

reader =open(0)

def solve(reader):
    result =[]
    n =reader.readline()

    for i in reader:  
        if '1' in str(i):
            i=i.rstrip('\n')
            result.append(i[-1])

이게 효율적일까

 

아니면

reader = sys.stdin.read().split('\n')[1:]



def solve(reader):
    result =[]
    for i in reader:  
        if '1' in str(i):
            result.append(i[-1])

이게 효율적일까?

 

답변
가지 방식은 각각 메모리(Memory)와 실행 속도(Speed) 측면에서 장단점이 뚜렷하게 다릅니다.

 

첫 번째 코드 (open(0) 후 for i in reader):
파일 객체에서 한 줄씩 데이터를 읽어옵니다. 데이터 전체를 한 번에 메모리에 올리지 않으므로 메모리 효율이 매우 좋습니다. 🧠

 

두 번째 코드 (sys.stdin.read().split('\n')[1:]):
입력 전체를 한꺼번에 읽어와서 거대한 문자열로 만든 뒤, 리스트로 쪼개고 복사본(슬라이싱)까지 만듭니다.

메모리 사용량은 훨씬 크지만, 파이썬 내부의 최적화된 C 언어 함수들(read, split)이 데이터를 한 번에 통째로 처리하기 때문에 실제 실행 속도는 이 방식이 더 빠른 경우가 많습니다. ⚡

(특히 알고리즘 문제 풀이 환경에서 두드러집니다.)

 

그런데 효율성을 비교하기 전에, 두 코드의 동작 결과가 완전히 다르게 나올 수 있는 중요한 차이점이 하나 숨어 있습니다. 바로 result.append(i[-1]) 부분입니다.

 

첫 번째 코드에서 for i in reader:로 문장을 한 줄씩 읽어올 때, 문자열 i의 맨 마지막에는 눈에 보이지 않는 줄바꿈 문자(\n)가 포함되어 있을까요, 아니면 제외되어 있을까요?

 

이 점을 고려한다면 첫 번째 코드의 i[-1]은 실제로 어떤 값을 result에 추가하게 될까요?

 

---

잘못된 답

import sys
reader = sys.stdin.read().split('\n')[1:]
print =sys.stdout.write


def solve(reader):
    result =[]
    for i in reader: 
        if '1' in str(i):
            result.append(i[-1])
        elif i ==2:
            if result:
                print(str(result.pop()))
            else:
                print('-1')

        elif i ==3:
            print( str(len(result)))
        elif i ==4:
            if result:
                print('0')
            else:
                print('1')
        elif i ==5:
            if result:
                print(str(result[-1]))
            else:
                print('-1')





solve(reader)

---

잘못된 답2

import sys
reader = sys.stdin.read().split('\n')[1:]
print =sys.stdout.write


def solve(reader):
    result =[]
    for i in reader: 
        if '1' in i:
            result.append(i[-1])
        elif i == '2':
            if result:
                print(result.pop()+'\n')
            else:
                print('-1'+'\n')

        elif i =='3':
            print( str(len(result))+'\n')
        elif i =='4':
            if result:
                print('0'+'\n')
            else:
                print('1'+'\n')
        elif i =='5':
            if result:
                print(result[-1]+'\n')
            else:
                print('-1'+'\n')

solve(reader)

피드백

현재 i[-1]을 사용해서 문자열의 맨 마지막 글자 하나만 스택에 넣고 계신데요. 만약 입력으로 1 15 (스택에 15를 추가하라는 명령어)가 들어온다면, 현재 코드에서는 스택에 어떤 값이 들어가게 될까요?

 

---

나의 정답(276ms)

import sys
reader = sys.stdin.read().split('\n')[1:]
print =sys.stdout.write


def solve(reader):
    result =[]
    for i in reader: 
        if '1' in i:
            result.append(i[2:])
        elif i == '2':
            if result:
                print(result.pop()+'\n')
            else:
                print('-1'+'\n')

        elif i =='3':
            print( str(len(result))+'\n')
        elif i =='4':
            if result:
                print('0'+'\n')
            else:
                print('1'+'\n')
        elif i =='5':
            if result:
                print(result[-1]+'\n')
            else:
                print('-1'+'\n')

solve(reader)

---

다른 사람의 풀이(244ms)

import sys

def solve():
    data = sys.stdin.read().split()
    N = int(data[0])
    stack = []
    output = []

    idx = 1
    for _ in range(N):
        command = data[idx]

        if command == '1':
            stack.append(data[idx+1])
            idx += 2
        elif command == '2':
            output.append(stack.pop() if stack else "-1")
            idx += 1
        elif command == '3':
            output.append(str(len(stack)))
            idx += 1
        elif command == '4':
            output.append("0" if stack else "1")
            idx += 1
        elif command == '5':
            output.append(stack[-1] if stack else "-1")
            idx += 1

    print("\n".join(output))

solve()

피드백

작성자님의 방식 (split('\n')): 줄바꿈을 기준으로만 문장을 통째로 나눕니다. 즉, i에는 "1 15" 와 같은 문자열이 그대로 들어갑니다.

 

다른 사람의 방식 (split()): 띄어쓰기, 줄바꿈 등 모든 종류의 공백을 기준으로 데이터를 완전히 조각냅니다. 리스트에는 ['1', '15', '2', '3'] 처럼 숫자만 깔끔하게 담깁니다.

 

이 두 방식의 차이는 '예상치 못한 입력'이 들어왔을 때 크게 벌어집니다.

 

작성자님의 코드에서는 "1 15"라는 문자열에서 숫자만 빼내기 위해 i[2:] (3번째 글자부터 끝까지 자르기)를 사용하셨는데요.

 

만약 테스트 케이스 중에 숫자 사이에 공백이 두 번 들어간 "1 15" (가운데 공백이 2개) 라는 입력이 주어졌다고 가정해 보겠습니다.

이때 다른 사람의 코드와 작성자님의 코드는 각각 스택에 어떤 값을 넣게 될까요?

 

---