스택, 큐, 덱

2025. 1. 6. 00:22ㆍAlgorithms/백준알고리즘 연습

28278번

스택 2

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

1024 MB

43425

15859

13155

36.945%

문제

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

명령은 총 다섯 가지이다.

1 X: 정수 X를 스택에 넣는다. (1 ≤ X ≤ 100,000)
2: 스택에 정수가 있다면 맨 위의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
3: 스택에 들어있는 정수의 개수를 출력한다.
4: 스택이 비어있으면 1, 아니면 0을 출력한다.
5: 스택에 정수가 있다면 맨 위의 정수를 출력한다. 없다면 -1을 대신 출력한다.

입력

첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

둘째 줄부터 N개 줄에 명령이 하나씩 주어진다.

출력을 요구하는 명령은 하나 이상 주어진다.

출력

출력을 요구하는 명령이 주어질 때마다 명령의 결과를 한 줄에 하나씩 출력한다.

예제 입력 1 복사

예제 출력 1 복사

스택은 첫번째 나오는 숫자가 맨 아래에 있다고 생각하면 됨.

초기 코드

import sys
n = int(sys.stdin.readline())
stack = []
new_s = []
for _ in range(n):
    x=int(sys.stdin.readline()) 
    if len(stack) == 0: 
        print(-1)
    else : 
        stack.append(x)
        new_s = stack.remove[-1]
        if len(new_s) =! 0 :
            print(new_s[-1])
        else :
            print(1)

작동법은 알겠는데, 순서가 헷갈린다.

문제 이슈 발생 이유 : 문제를 이해 못함

'입력으로 주어지는 명령' 이니까, 예제 입력은 주어진 정수가 아니라 문제의 번호 였던 것

#고쳐본코드

import sys
n = int(sys.stdin.readline())
stack = []
new_s = []
for _ in range(n):
    command = sys.stdin.readline.split() 
    if command[0] == '1' : 
        stack.append(command[1])
    elif command[0] == '2':
        if len(stack) == 0:
            print(-1)
        else : 
            new_s = stack.remove[-1]
            print(new_s)
    elif command[0] == '3':
        print(len(stack))
    elif command[0] == '4':
        if len(stack) == 0:
            print(1)
        else :
            print(0)
    elif command[0] == '5':
        if len(stack) == 0:
            print(-1)
        else :
            print(stack[-1])

스택에서 원소 제거하기 POP 함수

Stack - pop

스택에서 원소를 제거할 때에는 pop 메소드를 이용해 리스트의 가장 마지막 원소를 제거해준다. 이때, pop 메서드에 의해 제거한 원소를 리턴 받을 수 있다.

# 스택에서 원소 제거

stack = [1,2,3]

top = stack.pop()

print(top)

stack

# 3

# [1, 2]

10773 제로

제로 다국어

한국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

108961

74346

60205

68.374%

문제

나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.

재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.

재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.

재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!

입력

첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)

이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.

정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.

출력

재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 231-1보다 작거나 같은 정수이다.

예제 입력 1 복사

예제 출력 1 복사

예제 입력 2 복사

예제 출력 2 복사

초기 코드

import sys
k = int(sys.stdin.readline())
a_list = []
for _ in range(k):
    x = int(sys.stdin.readline())
    if x == 0 :
        a_list.remove[-1]
    else :
        a_list.append(x)
print(int(sum(a_list))

오류 :

1. pop 을 써야 함. remove -1 은 잘못된 문법임

2. print 괄호 안닫힘. 그리고 int를 쓸 필요가 없었음

9012번 괄호

괄호 다국어

한국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

232717

111063

79483

46.443%

문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.

출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.

예제 입력 1 복사

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

예제 출력 1 복사

NO
NO
YES
NO
YES
NO

예제 입력 2 복사

3
((
))
())(()

예제 출력 2 복사

NO
NO
NO

초기 코드 로직

(와 )의 갯수가 맞아야 함

import sys
t = int(sys.stdin.readline())
for _ in range (t):
    x = sys.stdin.readline().strip()
    if x.count('(') == x.count(')'):
        print("YES")
    else :
        print("NO")

내 코드가 틀린 이유

Your code incorrectly classifies the string ")()" as balanced ("YES") because it only checks if the total number of opening and closing parentheses are equal, without considering their order. Here's why this happens:

Your code counts the number of '(' and ')' separately using the count() method.
For the string ")()", both x.count('(') and x.count(')') return 1.
Since the counts are equal, your code prints "YES"

근데 2번이 이해가 안감.

The count() method does not consider the order or position of the characters; it only tallies the total number of matches. This is why it's not suitable for determining if parentheses are properly balanced, as it doesn't account for the crucial aspect of parentheses matching: their relative positions and proper nesting order.

수정을 위해서는 stack 을 사용해야 함

import sys

def is_bal(s):
	stack = []
    for char in s:
    	if char == '(' :
        	stack.append(char)
        elif char == ')':
        	if not stack:
            	return False
            stack.pop()
     return len(stack) == 0

t = int(sys.stdin.readline())
for _ in range(t):
	x = sys.stdin.readline().strip()
    if is_bal(x):
    	print("YES")
    else :
    	print("NO")

1. definition을 활용하여, ( 와 ) 를 쌓는데, (를 쌓아놓고 )를 쌓으면 없어지는 식임. 만약 )이 닫히지 않으면 그 함수는 false 임. 아니라면 ()를 지워서 모든 ( 와 ) 이 짝을 지으면 len(stack) == 0 으로 만듬

2. bal 이 true 이면 yes, 아니라면 no를 print 만드는 것임

4949 번 균형잡힌 세상 파이썬

위의 코드를 활용

초기 코드 + 온점으로 끝난다 라는 것을 활용

초기 코드

import sys

def is_bal(s):
	stack = []
    for char in s:
    	if char == '(' :
        	stack.append(char)
        elif char == ')':
        	if not stack:
            	return False
            stack.pop()
        if char == '[' :
            stack.append(char)
        elif char == ']':
            if not stack:
                return False
            stack.pop()     
         
return is_bal == '.'

t = int(sys.stdin.readline())
for _ in range(t):
        x = sys.stdin.readline().strip()
        if is_bal(x):
            print("YES")
        else :
            print("NO")

그런데 간과한 것이 있음

A rope may form )( a trail in a maze.

위의 인풋도 false임. 즉, (이 오면 )가 따라와야함.

수정 코드

import sys

def is_balanced(s):
    stack = []
    for char in s:
        if char in '([':
            stack.append(char)
        elif char in ')]':
            if not stack:
                return False
            if (char == ')' and stack[-1] != '(') or (char == ']' and stack[-1] != '['):
                return False
            stack.pop()
    return len(stack) == 0

while True:
    line = sys.stdin.readline().rstrip()
    if line == '.':
        break
    
    # 괄호와 마침표만 남기고 모든 문자 제거
    line = ''.join(char for char in line if char in '()[].')
    
    if is_balanced(line[:-1]):  # 마지막 마침표 제외
        print("yes")
    else:
        print("no")

12789번

도키도키 간식 드리미

1. 로직

스택문제인데,

입력

입력의 첫째 줄에는 현재 승환이의 앞에 서 있는 학생들의 수 N(1 ≤ N ≤ 1,000,자연수)이 주어진다.

다음 줄에는 승환이 앞에 서있는 모든 학생들의 번호표(1,2,...,N) 순서가 앞에서부터 뒤 순서로 주어진다.

출력

승환이가 무사히 간식을 받을 수 있으면 "Nice"(따옴표는 제외)를 출력하고 그렇지 않다면 "Sad"(따옴표는 제외)를 출력한다.

예제 입력 1 복사

5
5 4 1 3 2

예제 출력 1 복사

Nice

어떤 로직으로 승환이가 nice 를 받을 수 있는지 이해하지 못했다.

일단 1번이 출력되고, 3번이 스택에 쌓이고, 2번이 출력되고, 그 후 스택에 쌓여 있는 3,4,5번이 나와야 한다

그렇게 짜본 초기 코드

import sys
stack = []
n = int(sys.std.readline())
for _ in range(n):
    x = int(sys.std.readline())
    if x == 3 or x == 4 or x == 5:
        stack.append(x)
stack.pop()
if stack.pop()
    print("Nice")
else : 
    print("Sad")

도저히 고민하다가 안되어서 다른분 코드 참조.

정답 코드

출처 : https://velog.io/@highcho/Algorithm-baekjoon-12789

import sys

input = sys.stdin.readline
n = int(input())
wait = list(map(int, input().split()))
tmp = []
target = 1
for i in wait:
	tmp.append(i)
	while tmp and tmp[-1] == target: # tmp 스택 하나로 비교
		tmp.pop()
		target += 1
	if len(tmp) > 1 and tmp[-1] > tmp[-2]:
		print("Sad")
		sys.exit()
if tmp:
	print("Sad")
else:
	print("Nice")

wait이라는 리스트를 만들고, tmp안에 1~5 씩 넣고 비교해서, 대기줄과 tmp가 같으면 pop 되도록 만듬.

스택에서 빼지 못하면 전 원소와 비교하여 에러를 확인할 수 있도록 만듬.

나중에 들어온게 앞에 들어와있는 것 보다 크면 sad를 반환

18258번 큐 2

import sys
n = int(sys.stdin.readline())
stack = [] 
for _ in range(n):
    command = sys.stdin.readline().split()
    if command[0] == 'push' : 
        stack.append(command[1])
    elif command[0] == 'pop':
        if len(stack) == 0:
            print(-1)
        else :
            print(stack.pop())
    elif command[0] == 'size':
        print(len(stack))
    elif command[0] == 'empty':
        if len(stack) == 0:
            print(1)
        else :
            print(0)
    elif command[0] == 'front':
        if len(stack) == 0:
            print(-1)
        else :
            print(stack[1])
            
    elif command[0] == 'back':
        if len(stack) == 0:
            print(-1)
        else :
            print(stack[-1])

attribute error 가 나는데 왜인지 모르겠음

고친 코드

queue를 구현할 수 있는 daque 사용

조건문의 반복이 필요함

import sys
from collections import deque

n = int(sys.stdin.readline())
queue = deque()

for _ in range(n):
    command = sys.stdin.readline().split()
    
    if command[0] == 'push':
        queue.append(int(command[1]))
    elif command[0] == 'pop':
        if queue:
            print(queue.popleft())
        else:
            print(-1)
    elif command[0] == 'size':
        print(len(queue))
    elif command[0] == 'empty':
        print(1 if not queue else 0)
    elif command[0] == 'front':
        if queue:
            print(queue[0])
        else:
            print(-1)
    elif command[0] == 'back':
        if queue:
            print(queue[-1])
        else:
            print(-1)

조건부 표현식

print(1 if not queue else 0)

비어있으면 true 여서 1을 반환하고, 아니면 false 니까 - 0을 반환하라

조건부를 잘 쓸줄 알아야 하는데..

'Algorithms > 백준알고리즘 연습' 카테고리의 다른 글

스택, 큐, 덱 (2) (0)	2025.01.06
스택, 큐 (2) - deque의 기능 (0)	2025.01.06
백준 알고리즘 약수, 소수와 배수 2 (2) (1)	2024.12.22
약수, 배수와 소수 2 (2)	2024.12.14
백준 집합과 맵 (0)	2024.12.11

이러저러한 것들을 열심히 파보는 블로그

태그

최근글

댓글

공지사항

아카이브

28278번

스택 2

문제

입력

출력

예제 입력 1 복사

예제 출력 1 복사

Stack - pop

10773 제로

제로 다국어

문제

입력

출력

예제 입력 1 복사

예제 출력 1 복사

예제 입력 2 복사

예제 출력 2 복사

괄호 다국어

문제

입력

출력

예제 입력 1 복사

예제 출력 1 복사

예제 입력 2 복사

예제 출력 2 복사

4949 번 균형잡힌 세상 파이썬

12789번

도키도키 간식 드리미

입력

출력

예제 입력 1 복사

예제 출력 1 복사

18258번 큐 2

'Algorithms > 백준알고리즘 연습' 카테고리의 다른 글

관련글

티스토리툴바