[스택] 코딩테스트 문제 TIL (스택) - 백준 10828번

말하는 감자·2024년 8월 21일

baekjoon python stack 백준 스택 코딩테스트 코딩테스트 준비 파이썬

코딩테스트 유형별 풀이

목록 보기

2/67

드디어, 유형별 풀이 첫 주제 스택, 큐, 덱입니다!

이 문제는 제가 생각하는 스택 자료구조의 기본 문제라고 생각합니다. 그럼 문제 한 번 살펴볼까요?

1. 오늘의 학습 키워드

스택
자료 구조
구현

2. 문제: 스택 (10828번)

단계: 🥈실버 5티어
알고리즘 분류: 구현, 자료 구조, 스택
출처: https://www.acmicpc.net/problem/10828

스택

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.5 초 (추가 시간 없음)	256 MB	272283	100069	72601	37.718%

문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

push X: 정수 X를 스택에 넣는 연산이다.
pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 스택에 들어있는 정수의 개수를 출력한다.
empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

예제 입력 1

14
push 1
push 2
top
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
top

예제 출력 1

예제 입력 2

7
pop
top
push 123
top
pop
top
pop

예제 출력 2

-1
-1
123
123
-1
-1

출처

문제를 만든 사람: baekjoon
데이터를 추가한 사람: deunlee, djm03178

알고리즘 분류

3. 나의 풀이

문제 요약

이 문제에서는 정수를 저장하는 스택을 구현하고, 주어진 명령을 처리하는 프로그램을 작성해야 합니다. 명령은 총 5가지로, 각각의 명령에 따라 스택에 변화를 주거나 스택의 상태를 출력합니다.

주어진 명령들:

push X: 정수 X를 스택에 넣습니다.
pop: 스택의 가장 위에 있는 정수를 꺼내고 그 값을 출력합니다. 스택이 비어있다면 -1을 출력합니다.
size: 스택에 들어있는 정수의 개수를 출력합니다.
empty: 스택이 비어있다면 1을, 아니면 0을 출력합니다.
top: 스택의 가장 위에 있는 정수를 출력합니다. 스택이 비어있다면 -1을 출력합니다.

코드 구현

아래는 Python을 사용하여 문제를 해결한 코드입니다. 이 코드는 deque를 사용하여 스택을 구현했습니다. deque는 양방향 큐로서, 리스트보다 빠르게 스택과 큐의 연산을 처리할 수 있습니다.

import sys
from collections import deque

N = int(sys.stdin.readline().strip())
stack = deque()

for _ in range(N):
    command = sys.stdin.readline().split()

    if command[0] == 'push':
        stack.append(int(command[1]))
    elif command[0] == 'pop':
        if stack:
            print(stack.pop())
        else:
            print(-1)
    elif command[0] == 'size':
        print(len(stack))
    elif command[0] == 'empty':
        print(int(len(stack) == 0))
    elif command[0] == 'top':
        if stack:
            print(stack[-1])
        else:
            print(-1)

코드 설명

1. `import sys`와 `from collections import deque`

sys.stdin.readline을 사용하면 입력 속도를 빠르게 할 수 있습니다. 특히 많은 명령을 처리해야 할 때 유용합니다.
deque는 리스트와 달리, 양방향에서의 삽입 및 삭제가 O(1)의 시간 복잡도를 가집니다. 따라서 스택 연산에 매우 적합합니다.

2. 스택 명령 처리

push: stack.append()를 사용하여 스택의 끝에 요소를 추가합니다.
pop: stack.pop()을 사용하여 스택의 끝에서 요소를 제거하고 출력합니다. 스택이 비어있으면 1을 출력합니다.
size: len(stack)을 사용하여 스택에 들어있는 요소의 개수를 출력합니다.
empty: 스택이 비어있는지 여부를 int(len(stack) == 0)으로 확인하고, 1 또는 0을 출력합니다.
top: 스택의 끝에 있는 요소를 stack[-1]로 접근하여 출력합니다. 스택이 비어있으면 1을 출력합니다.

예제 입력 및 출력 분석

예제 입력 1:

14
push 1
push 2
top
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
top

예제 출력 1:

이 예제에서는 스택에 1과 2를 넣은 후, 여러 가지 명령을 처리하며 스택의 상태를 출력합니다. pop 명령으로 스택의 요소를 꺼내고, empty 명령으로 스택의 비어있는 상태를 확인하는 등, 다양한 상황을 테스트하고 있습니다.

+ Bonus!

보통 표준 입력을 받을 때 input()함수를 많이 사용합니다. 그런데 저는 sys.stdin을 사용했는데요. 이것에 대해 한 번 알아볼까요?

Python에서 sys.stdin 모듈을 사용하면 표준 입력을 처리할 수 있습니다. 특히 sys.stdin은 대량의 입력을 효율적으로 처리할 때 유용하며, input() 함수보다 더 빠르게 동작합니다. 여기서는 sys.stdin.readline(), sys.stdin.readlines(), 그리고 sys.stdin.read()에 대해 설명하겠습니다.

1. `sys.stdin.readline()`

설명: 한 줄의 입력을 읽어들입니다.
특징: 줄 끝에 있는 개행 문자(\n)가 포함됩니다. 개행 문자를 제거하려면 .strip() 메서드를 추가로 사용할 수 있습니다.

사용 예시:

import sys
line = sys.stdin.readline()
print(line.strip())  # 개행 문자를 제거한 후 출력

사용 시기: 입력이 한 줄씩 주어질 때 사용합니다. 예를 들어, 반복문 안에서 여러 줄을 하나씩 읽어야 하는 경우에 유용합니다.

2. `sys.stdin.readlines()`

설명: 입력의 모든 줄을 한꺼번에 읽어들여 리스트 형태로 반환합니다. 리스트의 각 요소는 한 줄에 해당하며, 각 줄 끝에는 개행 문자(\n)가 포함됩니다.
특징: 여러 줄의 입력을 한 번에 처리해야 할 때 사용됩니다.

사용 예시:

import sys
lines = sys.stdin.readlines()
for line in lines:
    print(line.strip())  # 개행 문자를 제거한 후 출력

사용 시기: 여러 줄의 입력을 한꺼번에 처리해야 하는 경우, 예를 들어 파일 전체를 읽어와 처리하는 경우에 유용합니다.

3. `sys.stdin.read()`

설명: 전체 입력을 한꺼번에 읽어들여 하나의 문자열로 반환합니다. 입력이 끝날 때까지 모든 내용을 읽어옵니다.
특징: 개행 문자를 포함한 전체 입력을 하나의 문자열로 처리할 수 있습니다.

사용 예시:

import sys
data = sys.stdin.read()
print(data)  # 전체 입력 내용을 출력

사용 시기: 전체 입력을 한 번에 처리해야 할 때 사용됩니다. 예를 들어, 대용량 데이터를 통째로 읽어와서 처리해야 하는 경우에 유용합니다.

요약

sys.stdin.readline(): 한 줄씩 입력을 읽어옵니다. 주로 반복문과 함께 사용되어 줄 단위로 데이터를 처리할 때 유용합니다.
sys.stdin.readlines(): 모든 입력을 한 번에 읽어오고, 각 줄을 리스트의 요소로 반환합니다. 여러 줄의 입력을 리스트로 관리하고 싶을 때 사용합니다.
sys.stdin.read(): 전체 입력을 하나의 문자열로 읽어옵니다. 대용량 데이터를 한 번에 처리할 때 사용합니다.

각 방법은 입력의 형태와 필요에 따라 선택적으로 사용하면 됩니다. 일반적으로 코딩 테스트나 프로그래밍 대회에서는 입력의 효율적인 처리가 중요하므로, sys.stdin 관련 함수들이 자주 사용됩니다.

예제를 통해 sys.stdin.readline(), sys.stdin.readlines(), sys.stdin.read()의 차이를 명확하게 이해할 수 있도록 각각의 결과를 비교해보겠습니다.

예제 입력

다음과 같은 입력이 있다고 가정해봅시다:

Hello, World!
This is a test.
Let's see how sys.stdin works.

1. `sys.stdin.readline()` 사용 예시

import sys

# 첫 번째 줄 읽기
line = sys.stdin.readline()
print(f"Readline output: '{line}'")

결과:
```
Readline output: 'Hello, World!\n'
```
- sys.stdin.readline()은 입력된 첫 번째 줄만 읽어들입니다.
- 결과 문자열에는 개행 문자(\n)가 포함되어 있습니다.

2. `sys.stdin.readlines()` 사용 예시

import sys

# 전체 입력을 리스트로 읽기
lines = sys.stdin.readlines()
print(f"Readlines output: {lines}")

결과:
```
Readlines output: ['Hello, World!\n', 'This is a test.\n', "Let's see how sys.stdin works.\n"]
```
- sys.stdin.readlines()는 입력된 모든 줄을 리스트로 읽어들입니다.
- 각 줄은 리스트의 요소로 저장되며, 개행 문자가 포함되어 있습니다.

3. `sys.stdin.read()` 사용 예시

import sys

# 전체 입력을 문자열로 읽기
data = sys.stdin.read()
print(f"Read output: '{data}'")

결과:
```
Read output: 'Hello, World!\nThis is a test.\nLet's see how sys.stdin works.\n'
```
- sys.stdin.read()는 전체 입력을 하나의 문자열로 읽어들입니다.
- 개행 문자 포함한 전체 내용을 하나의 문자열로 반환합니다.

요약된 결과

sys.stdin.readline(): 'Hello, World!\\n'
- 첫 번째 줄만 읽고, 개행 문자를 포함합니다.
sys.stdin.readlines(): ['Hello, World!\\n', 'This is a test.\\n', "Let's see how sys.stdin works.\\n"]
- 전체 입력을 줄 단위로 리스트에 저장하며, 각 줄은 개행 문자를 포함합니다.
sys.stdin.read(): 'Hello, World!\\nThis is a test.\\nLet's see how sys.stdin works.\\n'
- 전체 입력을 하나의 문자열로 읽어들이며, 개행 문자를 포함합니다.

4. 결론

이 문제는 스택의 기본적인 연산들을 구현하고, 이를 통해 스택의 동작 원리를 이해하는 데 도움을 줍니다. 스택은 여러 가지 알고리즘에서 중요한 역할을 하므로, 이러한 기본적인 문제를 통해 충분히 연습해보시기 바랍니다.

또한, 코딩 테스트에서는 속도가 중요한데, 사소한 속도라도 줄이고자 저는 python의 sys.stdin 모듈을 사용해서 입출력을 사용했습니다.

다음에는 다른 자료구조나 알고리즘 문제로 돌아오겠습니다! 질문이나 피드백이 있다면 언제든지 댓글로 남겨주세요.

감사합니다! 🚀

말하는 감자

할 수 있다

이전 포스트

코딩테스트 유형별 풀이 START

다음 포스트

[스택] 코딩테스트 문제 TIL (스택) - 백준 10828번

코딩테스트 유형별 풀이

1. 오늘의 학습 키워드

2. 문제: 스택 (10828번)

스택

문제

입력

출력

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

출처

알고리즘 분류

3. 나의 풀이

문제 요약

주어진 명령들:

코드 구현

코드 설명

1. `import sys`와 `from collections import deque`

2. 스택 명령 처리

예제 입력 및 출력 분석

+ Bonus!

1. `sys.stdin.readline()`

2. `sys.stdin.readlines()`

3. `sys.stdin.read()`

요약

예제 입력

1. `sys.stdin.readline()` 사용 예시

2. `sys.stdin.readlines()` 사용 예시

3. `sys.stdin.read()` 사용 예시

요약된 결과

4. 결론

코딩테스트 유형별 풀이 START

[큐] 코딩테스트 문제 TIL (큐) - 백준 10845번

0개의 댓글

관련 채용 정보

[스택] 코딩테스트 문제 TIL (스택) - 백준 10828번

코딩테스트 유형별 풀이

1. 오늘의 학습 키워드

2. 문제: 스택 (10828번)

스택

문제

입력

출력

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

출처

알고리즘 분류

3. 나의 풀이

문제 요약

주어진 명령들:

코드 구현

코드 설명

1. import sys와 from collections import deque

2. 스택 명령 처리

예제 입력 및 출력 분석

+ Bonus!

1. sys.stdin.readline()

2. sys.stdin.readlines()

3. sys.stdin.read()

요약

예제 입력

1. sys.stdin.readline() 사용 예시

2. sys.stdin.readlines() 사용 예시

3. sys.stdin.read() 사용 예시

요약된 결과

4. 결론

코딩테스트 유형별 풀이 START

[큐] 코딩테스트 문제 TIL (큐) - 백준 10845번

0개의 댓글

관련 채용 정보

1. `import sys`와 `from collections import deque`

1. `sys.stdin.readline()`

2. `sys.stdin.readlines()`

3. `sys.stdin.read()`

1. `sys.stdin.readline()` 사용 예시

2. `sys.stdin.readlines()` 사용 예시

3. `sys.stdin.read()` 사용 예시