스택(Stack)

1
int stack[10000];
2
int size = 0;

1
"""
2
파이썬은 따로 stack 구조를 제공하지 않는다.
3
기본 클래스 list를 이용하여 stack을 표현할 수 있다.
4
"""
5
import sys
6

7
# 입력을 빠르게 받기 위해 sys.stdin.readline을 input으로 사용
8
input = sys.stdin.readline
9

10
n = int(input())  # 정수 n을 입력받습니다. 이것은 명령의 개수를 의미
11
stack = []  # 스택을 생성, 스택은 나중에 사용될 리스트
12

13
for _ in range(n):  # n번 반복
14
    s = input().split()  # 공백을 기준으로 문자열을 분리
15
    cmd = s[0]  # 리스트 s의 첫 번째 요소를 명령어로 설정
16

17
    if cmd == "push":
18
        num = int(s[1])  # 문자열을 정수로 변환하여 숫자를 얻음
19
        stack.append(num)  # 스택에 숫자를 추가
20

21
    elif cmd == "top":
22
        # 스택이 있으면, 가장 위에 있는 숫자를 출력
23
        if stack:
24
            print(stack[-1])
25
        # 스택이 비어있으면, -1 출력
26
        else:
27
            print(-1)
28

29
    # 스택의 크기(길이)를 출력
30
    elif cmd == "size":
31
        print(len(stack))
32

33
    # 스택이 비어있으면 1, 아니면 0을 출력
34
    elif cmd == "empty":
35
        print(0 if stack else 1)
36

37
    elif cmd == "pop":
38
        # 스택이 있으면, 가장 위에 있는 숫자를 꺼내고 출력
39
        if stack:
40
            print(stack.pop())
41
        # 스택이 비어있으면, -1을 출력
42
        else:
43
            print(-1)

1
"""
2
N개의 글자를 스택에 넣었다가 빼면 순서가 역순이 된다.
3
알파벳을 스택에 넣고, 공백이나 문자열의 끝이면 스택에서 모두 빼내서 역순을 만든다.
4

5
📌 [::-1] : 리스트를 처음부터 끝까지 거꾸로 스텝하라는 의미
6
            -> 파이썬 리스트에서 슬라이싱을 사용하여 역순으로 된 리스트를 생성
7
📌 join() : 문자열 리스트의 각 요소들을 하나의 문자열로 이어붙이는 역할
8
"""
9
import sys
10

11
input = sys.stdin.readline
12

13
TEST_CASE = int(input())
14

15

16
for _ in range(TEST_CASE):
17
    inputSentence = input()  # 한 줄을 읽어들여 변수에 저장
18
    stack = []
19

20
    # 문자열 inputSentence에 대해 한 문자씩 반복
21
    for charactor in inputSentence:
22
        if charactor == " " or charactor == "\n":
23
            # stack에 저장된 문자들을 역순으로 이어붙여서 출력하고, 마지막의 개행 문자를 제거
24
            print("".join(stack[::-1]), end="")
25
            stack.clear()
26

27
            # 공백(' ') 또는 개행 문자('\n')를 출력
28
            print(charactor, end="")
29
        # 문자 ch가 공백 또는 개행 문자가 아니라면, stack에 문자를 추가
30
        else:
31
            stack.append(charactor)

1
def getIsParentheses(s):
2
    count = 0  # 괄호 쌍을 유지하기 위한 카운트 변수 초기화
3

4
    for ch in s:
5
        # 여는 괄호일 경우 카운트 증가 (괄호 쌍 시작)
6
        if ch == "(":
7
            count += 1
8
        # 닫는 괄호일 경우 카운트 감소 (괄호 쌍 끝)
9
        else:
10
            count -= 1
11
        # 중간에 닫는 괄호가 더 많을 경우
12
        if count < 0:
13
            return "NO"
14
    # 모든 괄호가 쌍을 이루었을 경우
15
    if count == 0:
16
        return "YES"
17
    # 괄호 쌍이 다 맞지 않는 경우
18
    else:
19
        return "NO"
20

21

22
TEST_CASE = int(input())
23

24
for _ in range(TEST_CASE):
25
    print(getIsParentheses(input()))

1
"""
2
스택에 수를 push 할 때는 반드시 오름차순으로만 push할 수 있다.
3

4
e.g., 8을 push해야 한다면 앞의 1~7까지를 모두 push하고 8을 push할 수 있다.
5
그리고 스택을 쌓다가 필요한 타이밍에 pop을 하게 되는데, 이 pop을 한 수들을 쭉 나열했을 때,
6
N줄에 걸쳐 입력한 수열과 같아야 한다.
7

8
e.g. N=8이고 다음줄부터 4, 3, 6, 8, 7, 5, 2, 1을 입력한 상황을 보면
9
스택을 쌓다가 중간에 한번씩 pop을 한 데이터들을 나열한 순서도 4, 3, 6, 8, 7, 5, 2, 1이 되어야 한다
10

11
처음으로 4를 입력했다.
12
즉, 내가 첫 번째로 pop한 숫자가 4가 되어야 한다. 그러기 위해서는 1,2,3,4가 이미 스택안에 있어야 한다.
13
그래서 입력한 수를 만날 때 까지는 계속 push를 해서 1,2,3,4가 스택에 있도록 해야한다
14

15
그리고 나서 4를 꺼내 스택은 현재 1,2,3인 상황이다.
16
그 다음으로 3이 주어졌기 때문에 push없이 현재 스택에서 pop을 하면 된다. 그리고 스택은 1,2가 된다.
17
그다음 입력으로 6이 주어졌기 때문에, 다시 6을 만날 때 까지 이전의 숫자들을 push 해준다. ( 즉 5, 6 push )
18

19
----------
20
이 때, stack에서 pop할 숫자(TOP)가 입력한 숫자가 아닐 경우(작을 경우) 정답을 완성할 수 없다.
21
왜냐하면 TOP 값이 입력한 숫자보다 크면, 입력한 수를 꺼내기 위해 계속 POP을 해야 하기 때문에
22
그 과정에서 POP한 수들의 수열이 정답과 일치하지 않게 되기 때문이다.
23

24
e.g. 1, 2, 5, 3, 4가 입력으로 주어졌다고 하자.
25
1을 입력했을 때 스택은 [1]       -> pop -> 1
26
2을 입력했을 때 스택은 [2]       -> pop -> 2
27
5을 입력했을 때 스택은 [3, 4, 5] -> pop -> 5
28
3을 입력했을 때 스택은 [3, 4]    -> pop -> 4 가 된다.
29
3이 먼저 나와야 하는데 4가 먼저 나와버린 것이다
30
"""
31
import sys
32

33
n = int(input())
34
stack = []
35
result = []
36

37
# n개의 숫자를 입력받아 수열 리스트에 저장
38
progression = [int(input()) for _ in range(n)]
39

40
# 스택에 push할 오름차순 자연수, 맨 처음에 들어간 것이 없으니 0으로 초기화
41
currentNum = 0
42

43
for el in progression:
44
    # 입력된 숫자가 현재 최댓값보다 큰 경우
45
    if el > currentNum:
46
        # el와 같아질 때까지, currentNum의 값을 1씩 올리면서 push를 반복, '+' 기호를 추가하여 push 동작을 표시
47
        while el > currentNum:
48
            currentNum += 1
49
            stack.append(currentNum)
50
            result += ["+"]
51

52
        # el와 같아져서 반복이 끝난 후, 스택에서 값을 제거하고, '-' 기호를 추가하여 pop 동작을 표시
53
        stack.pop()
54
        result += ["-"]
55

56
    # 입력된 숫자가 현재 최댓값보다 작거나 같은 경우
57
    else:
58
        # 스택의 맨 위 값과 입력된 숫자가 다른 경우 'NO' 출력
59
        if stack[-1] != el:
60
            print("NO")
61
            sys.exit(0)  # 프로그램 종료
62
        # 스택의 맨 위 값과 입력된 숫자가 같은 경우, 스택에서 값을 제거하여 pop 동작 표시
63
        stack.pop()
64
        result += ["-"]
65

66
# 결과 리스트의 내용을 개행문자와 함께 출력
67
print("\n".join(result) + "\n")

1
"""
2
'L'은 커서를 왼쪽으로 옮김
3
'D'는 커서를 오른쪽으로 옮김
4
'P'는 커서 왼쪽에 문자를 추가
5
'B'는 커서 왼쪽에 문자를 삭제
6
모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램
7

8
커서를 기준으로 커서의 왼쪽 스택(left)와 오른쪽 스택(right)로 나눠서 문제를 풀 수 있다.
9
e.g. abc | xyz (|는 커서를 의미)
10
"""
11
import sys
12

13
input = sys.stdin.readline
14

15
left = list(input().strip())  # 왼쪽 문자열 초기화
16
right = []  # 오른쪽 문자열을 위한 빈 리스트 생성
17

18
M = int(input())  # 수행할 명령어 개수 입력
19

20
for _ in range(M):
21
    line = input().strip().split()  # 공백을 기준으로 입력을 나눠 리스트에 저장
22
    command = line[0]  # 명령어의 첫 번째 요소 (어떤 작업을 할지)
23

24
    if command == "L":
25
        # 왼쪽 문자열에 남아있는 문자가 있는 경우, 왼쪽 문자열의 마지막 문자를 오른쪽 문자열로 이동
26
        if left:
27
            right.append(left.pop())
28
    elif command == "D":
29
        # 오른쪽 문자열에 남아있는 문자가 있는 경우, 오른쪽 문자열의 마지막 문자를 왼쪽 문자열로 이동
30
        if right:
31
            left.append(right.pop())
32
    elif command == "P":
33
        # 두 번째 요소로 주어진 문자를 왼쪽 문자열에 추가
34
        left.append(line[1])
35
    elif command == "B":
36
        # 왼쪽 문자열에 남아있는 문자가 있는 경우, 왼쪽 문자열의 마지막 문자 삭제
37
        if left:
38
            left.pop()
39

40
left += right[::-1]  # 남은 문자열을 모두 왼쪽 문자열에 추가 (오른쪽 문자열을 뒤집어서)
41

42
print("".join(left))  # 왼쪽 문자열을 하나의 문자열로 합쳐서 출력