과거 프로그래밍 자료들/코딩테스트

[백준] python 코딩테스트 - 스택(10828, 10799, 2812)

평부 2022. 9. 22. 23:43

 

 

 

출처 : http://www.yes24.com/Product/Goods/107478270

 

보통의 취준생을 위한 코딩 테스트 with 파이썬 - YES24

이 책은 손에 잡히는 코딩 테스트 합격 방법을 제시한다. 바로 “백준 플래티넘 5 & 코드 포스 파란색 랭크”로 목표 설정을 구체화한 것이다. 이 수준을 달성하면 웬만한 기업의 코딩 테스트 문

www.yes24.com

 

 

* 스택(10828)

https://www.acmicpc.net/problem/10828

 

10828번: 스택

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

www.acmicpc.net

 

import sys
n = int(sys.stdin.readline())

stack = []
for i 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] == "top":
        if len(stack) == 0:
            print(-1)
        else:
            print(stack[-1])

 

 

* 쇠막대기 (10799) [▶ 부분에 오타가 있을 경우 댓글로 알려주세요]

▶ 위의 예제와 달리 왜 스택인지 이해 못 했었음

▶ 1. "("가 나올 때 stack 배열에 넣기

▶ 2.  "("가 아닐 때(즉 ")"일 때) 전에 입력한 게 "("라면 stack 비우기(pop 이용), answer의 stack 길이만큼 +1

▶ 3. "("가 아닐 때(즉 ")"일 때) 전에 입력한 게 ")"라면 answer에 +1

galho = input()
stack = []
answer = 0
for i in range(len(galho)):
    if galho[i] == "(":
        stack.append(galho[i])
    else:  
        if galho[i-1] == "(":
            stack.pop()
            answer += len(stack)
        else:
            stack.pop()
            answer += 1
print(answer)

 

 

* 해설 부분(print 포함)

더보기
galho = input()
stack = []
answer = 0
for i in range(len(galho)):
    if galho[i] == "(":
        stack.append(galho[i])
        print("galho", galho)
        print("stack", stack)
    else:  # ")"
        if galho[i-1] == "(":
            stack.pop()
            print("stack2", stack)
            answer += len(stack)
            print("len(stack)", len(stack))
            print("answer", answer)
        else:
            stack.pop()
            answer += 1
            print("answer2", answer)
print(answer)

# ()(((()())(())()))(())
# galho ()(((()())(())()))(())
# stack ['(']
# stack2 []
# len(stack) 0
# answer 0
# galho ()(((()())(())()))(())
# stack ['(']
# galho ()(((()())(())()))(())
# stack ['(', '(']
# galho ()(((()())(())()))(())
# stack ['(', '(', '(']
# galho ()(((()())(())()))(())
# stack ['(', '(', '(', '(']
# stack2 ['(', '(', '(']
# len(stack) 3
# answer 3
# galho ()(((()())(())()))(())
# stack ['(', '(', '(', '(']
# stack2 ['(', '(', '(']
# len(stack) 3
# answer 6
# answer2 7
# galho ()(((()())(())()))(())
# stack ['(', '(', '(']
# galho ()(((()())(())()))(())
# stack ['(', '(', '(', '(']
# stack2 ['(', '(', '(']
# len(stack) 3
# answer 10
# answer2 11
# galho ()(((()())(())()))(())
# stack ['(', '(', '(']
# stack2 ['(', '(']
# len(stack) 2
# answer 13
# answer2 14
# answer2 15
# galho ()(((()())(())()))(())
# stack ['(']
# galho ()(((()())(())()))(())
# stack ['(', '(']
# stack2 ['(']
# len(stack) 1
# answer 16
# answer2 17
# 17

 

 

* 크게 만들기 (2812)

https://www.acmicpc.net/problem/2812

 

2812번: 크게 만들기

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

n, k = map(int, input().split())
number = list(input())

answer = []
cnt = k
for num in number:
    while answer and cnt > 0 and answer[-1] < num:
        del answer[-1]
        cnt -= 1
        print("cnt", cnt)

print(''.join(answer[:n-k]))

 

* 해설 부분(print 포함)

더보기
n, k = map(int, input().split())
number = list(input())

answer = []
cnt = k
print("number", number)
for num in number:
    print("num", num)
    while answer and cnt > 0 and answer[-1] < num:
        print("answer[-1]", answer[-1])
        print("answer", answer)
        del answer[-1]
        cnt -= 1
        print("cnt", cnt)
    answer.append(num)
    print("answer2", answer)

print("answer[:n-k]", answer[:n-k])
print(''.join(answer[:n-k]))

# 입력
# 4 2
# 1924

# number ['1', '9', '2', '4']
# num 1
# answer2 ['1']
# num 9
# answer[-1] 1
# answer ['1']
# cnt 1
# answer2 ['9']
# num 2
# answer2 ['9', '2']
# num 4
# answer[-1] 2
# answer ['9', '2']
# cnt 0
# answer2 ['9', '4']
# answer[:n-k] ['9', '4']
# 94