2학기 3주차_알고리즘( 백준28278번 : 스택2 )

3주차 알고리즘 문제를 시작하겠다.

 

문제

 

 

 

➡️문제

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

명령은 총 다섯 가지이다.

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

➡️입력

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

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

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

➡️출력

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

 

오늘의 문제는 제목부터 스택이다. 나는 스택이라는 개념을 아직 배워본적이 없어서 이전에 문제들에서 스택이라는 기술이 쓰이면 쉽게 푸는 문제들도 다른 방법으로 더 어렵게 풀어왔었다.

 

오늘의 문제는 스택이니 이참에 스택을 학습해봐야겠다.

찾아보니까 해당문제는 스택 자료구조와 관련된 문제라고한다.

 

 

 

 개념 공부

 

📌STACK이란?

• 스택은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조이다.
• 데이터의 입력과 출력 순서는 후입선출(LIFO:Last In First Out)이다.
• C언어 프로그램에서 함수를 호출하고 실행할 때 프로그램 내부에서는 스택을 사용한다.
• push : 데이터를 넣는 작업을 뜻한다.
• pop : 데이터를 꺼내는 작업을 뜻한다.
• top : push, pop 하는 위치를 말한다.
• botoom : stack의 가장 밑바닥 부분을 뜻한다.

 

✅ 참고 학습 자료 (아래 링크는 내가 학습하는데 도움을 받은 자료이다.)

스택(Stack)에 대해서 (velog.io)

→ 해당 링크를 통해서 스택에 대해서 더 자세히 공부해야할 것같다.

 

 코드

import sys
input = sys.stdin.readline


N = int(input())
stack = []
for _ in range(N):
    command = input().rstrip()
    
    #push
    if len(command) > 2:
        stack.append(int(command[2:]))
    
    #pop
    elif command == '2':
        if len(stack)==0:
            print(-1)
        else:
            print(stack.pop())
    
    #size
    elif command == '3':
        print(len(stack))

    #empty
    elif command == '4':
        print(1 if len(stack)==0 else 0)
    
    #top
    elif command == '5':
        if len(stack)==0:
            print(-1)
        else:
            print(stack[-1])
            
    #print(command)
    #print(stack)

 

나는 C로 풀이를하고 싶었는데, 대부분의 풀이들이 C++아니면 Python으로 되어있었다.

그래서 나는 내가 학습한 경험이 있는 Python을 통해 풀이를 진행해보겠다.

 

풀이

1. N = int(input()): 정수 N을 입력받는다.
2. 이 정수는 이어지는 명령의 개수를 나타낸다
3.stack = []: 빈 리스트를 스택으로 사용하기 위해 초기화한다.
4. for _ in range(N):: N번 반복하는 루프를 시작한다.
5. command = input().rstrip(): 사용자로부터 명령을 문자열로 입력받고, 오른쪽 끝의 개행 문자(\n)를 제거한다.
6. if len(command) > 2:: 만약 입력된 명령이 길이가 2보다 크다면(push 명령이라면,
stack.append(int(command[2:])) 스택에 해당하는 값을 정수로 변환하여 추가한다.
7. 명령의 앞 부분은 "push"이므로, command[2:]는 숫자 부분을 나타낸다.
8. elif command == '2':: 입력된 명령이 '2'라면(pop 명령이라면),if len(stack)==0:: 스택이 비어있다면,print(-1): -1을 출력한다. (스택이 비어있을 때 pop 연산은 불가능하므로) else:: 그렇지 않으면,print(stack.pop()): 스택의 가장 위에 있는 값을 꺼내서 출력한다.
9. elif command == '3':: 입력된 명령이 '3'이라면(size 명령이라면),print(len(stack)): 스택의 현재 크기를 출력한다.
10. elif command == '4':: 입력된 명령이 '4'라면(empty 명령이라면),print(1 if len(stack)==0 else 0): 스택이 비어있으면 1을, 그렇지 않으면 0을 출력한다.
11. elif command == '5':: 입력된 명령이 '5'라면(top 명령이라면),if len(stack)==0:: 스택이 비어있다면,print(-1): -1을 출력한다. (스택이 비어있을 때 top 연산은 불가능하므로)else:: 그렇지 않으면,print(stack[-1]): 스택의 가장 위에 있는 값을 출력한다.

 

스택이라는 개념을 앞으로 많이 사용할 거 같으니 해당내용을 잘 기억하고 추가학습해서 다음번에 잘 활용할 수 있도록 해야겠다.

또 이번에는 Python에서 스택을 학습했지만, 추가적으로 C 에서 스택의 개념이 어떻게 쓰이는지도 확인하고 학습해야겠다.

 

결과

 

첫번째 문제 끝

 

참고 자료

스택(Stack)에 대해서