[Algorithm] 스택(Stack)

• 목차

  스택이란

  [10828] 스택

  문제

  입력

  출력

  답안

  [9093] 단어 뒤집기

  문제

  입력

  출력

  예제 입력 1

  예제 출력 1

  답안

  join 앞에 ‘’가 붙는 이유

  stack[::-1]의 의미

  [9012] 괄호

  문제

  입력

  출력

  예제 입력 1

  예제 출력 1

  예제 입력 2

  예제 출력 2

  풀이

  def란?

  def의 사용범위는?

스택이란

1. 의미 : 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조 마지막으로 넣은 것이 가장 먼저 나오기 때문에 LIFO(Last In First Out)라고도 함

2. push : 스택에 자료를 넣는 연산

3. pop : 스택에서 자료를 빼는 연산

4. top : 스택의 가장 위에 있는 자료를 보는 연산

5. empty : 스택이 비어있는지 아닌지를 알아보는 연산

6. size : 스택에 저장되어 있는 자료의 개수를 알아보는 연산

 

 

 

[10828] 스택

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.5 초 (추가 시간 없음)	256 MB	200885	70797	51661	37.307%

문제

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

명령은 총 다섯 가지이다.

• push X: 정수 X를 스택에 넣는 연산이다.

• pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

• size: 스택에 들어있는 정수의 개수를 출력한다.

• empty: 스택이 비어있으면 1, 아니면 0을 출력한다.

• top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

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

출력

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

 

답안

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

 

 

 

 

[9093] 단어 뒤집기

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	29655	15527	11646	53.183%

문제

문장이 주어졌을 때, 단어를 모두 뒤집어서 출력하는 프로그램을 작성하시오. 단, 단어의 순서는 바꿀 수 없다. 단어는 영어 알파벳으로만 이루어져 있다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는 공백이 하나 있다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 문장의 단어를 모두 뒤집어 출력한다.

예제 입력 1

2 I am happy today We want to win the first prize 

예제 출력 1

I ma yppah yadot eW tnaw ot niw eht tsrif ezirp 

 

답안

import sys  t = int(sys.stdin.readline()) for _ in range(t):     s = sys.stdin.readline()     stack = []     for w in s:         if w == ' ' or w == '\n':             print(''.join(stack[::-1]), end='')             stack.clear()             print(w, end='')         else:             stack.append(w)

 

join 앞에 ‘’가 붙는 이유

join() 함수는 리스트의 모든 요소를 하나의 문자열로 결합하는데, 이때 각 요소 사이에 어떤 문자열을 삽입할지 결정할 수 있습니다. 이때, join() 함수에 전달되는 인자는 각 요소 사이에 삽입할 문자열입니다.

따라서 ''.join(stack[::-1])에서 ''는 요소 사이에 삽입할 문자열이 없음을 의미합니다. 즉, stack[::-1] 리스트의 모든 요소를 그대로 붙여서 하나의 문자열로 만든다는 의미입니다.

만약 join() 함수에 ','와 같은 구분자를 전달한다면, 리스트의 요소들 사이에 , 문자열이 삽입되어 결합된 문자열이 반환됩니다. 예를 들어, ','.join(['a', 'b', 'c'])는 'a,b,c'를 반환합니다.

 

stack[::-1]의 의미

stack[::-1]은 파이썬에서 리스트를 역순으로 뒤집는 방법 중 하나입니다. 리스트 슬라이싱(slicing)을 이용하여 구현할 수 있습니다.

리스트 슬라이싱은 [start:stop:step] 형태로 표현됩니다. start는 슬라이스를 시작하는 인덱스, stop은 슬라이스를 끝내는 인덱스(이 인덱스는 포함되지 않음), step은 간격을 나타냅니다.

start, stop, step 중 하나를 생략할 수 있습니다. step을 생략하면 기본값인 1이 사용됩니다. start와 stop 중 하나를 생략하면 리스트의 처음부터 끝까지를 의미합니다. start와 stop 모두 생략하면 리스트 전체를 의미합니다.

stack[::-1]에서 start와 stop이 생략되어 있으며, step이 -1로 설정되어 있습니다. 따라서 stack[::-1]은 stack 리스트를 역순으로 뒤집은 새로운 리스트를 생성합니다.

 

 

 

[9012] 괄호

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	156097	72359	52193	45.299%

문제

괄호 문자열(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 

 

풀이

def valid(s):     cnt = 0     for ch in s:         if ch == '(':             cnt += 1         else:             cnt -= 1         if cnt < 0:             return 'NO'     if cnt == 0:         return 'YES'     else:         return 'NO'   t = int(input()) for _ in range(t):     print(valid(input()))

 

def란?

Python에서 def는 "define"의 약자로, 새로운 함수를 정의할 때 사용됩니다. 함수는 입력 값을 받아 처리하고 결과를 반환하는 코드 블록입니다.

def 문법은 다음과 같이 구성됩니다:

def 함수이름(매개변수1, 매개변수2, ...):     코드 블록     return 반환값

함수 이름은 일반적으로 영문 소문자로 작성하며, 매개변수는 함수가 받아들일 입력 값을 나타냅니다. 코드 블록은 함수가 수행할 작업을 포함하며, return 문은 함수의 결과를 반환합니다.

예를 들어, 다음은 두 개의 정수를 더하는 간단한 함수를 정의하는 코드입니다:

def add_numbers(x, y):     result = x + y     return result

위의 코드에서 add_numbers 함수는 두 개의 매개변수를 받아들이고, 그들의 합을 반환합니다. 함수를 호출할 때는 다음과 같이 입력 값을 전달합니다:

sum = add_numbers(3, 5) print(sum)  # 출력 결과는 8입니다.

함수를 정의하면 코드의 재사용성이 높아지므로, 프로그래밍 작업이 더 효율적으로 이루어집니다.

 

def의 사용범위는?

Python에서 def로 정의된 함수는 해당 함수가 정의된 블록에서만 사용할 수 있습니다. 즉, 함수의 사용범위는 해당 함수가 정의된 모듈, 클래스, 함수 또는 코드 블록입니다.

예를 들어, 다음 코드는 함수를 정의하고 호출하는 간단한 예입니다:

def greeting(name):     print("Hello, " + name + "!")  greeting("Alice")

위의 코드에서 함수 greeting()은 전역 범위(global scope)에서 정의되었으며, 해당 모듈 내에서 어디에서나 호출할 수 있습니다.

함수 내에서 다른 함수를 정의할 수도 있습니다. 이 경우 내부 함수는 바깥 함수 내부에서만 호출됩니다. 이러한 내부 함수를 클로저(closure)라고 부르며, 해당 함수 내에서만 유효한 지역 변수(local variable)를 포함할 수 있습니다.

def outer_function(x):     def inner_function(y):         return x + y     return inner_function  add_five = outer_function(5) result = add_five(3) print(result)  # 출력 결과는 8입니다.

위의 코드에서 outer_function()은 inner_function()을 반환합니다. 반환된 내부 함수 add_five는 외부 함수 outer_function()에서 정의된 x 값을 유지하며, 외부 함수의 호출이 완료된 후에도 사용될 수 있습니다.

 

Uploaded by

N2T