18단계 문제들 : 스택
인트로
스택..지겨와..
Stack이란?
출처: 위키백과
- LIFO (Last In First Out) 의 구조를 갖는다
- 자료를 넣는 것을 push / 자료 빼는 것을 pop
- 가장 늦게 넣은 것이 더 먼저 나오는 자료구조
10828번 - 스택
스택을 구현하는 문제이다. push / pop / size / empty / top의 기능을 수행하는 스택을
구현하면 되는 문제.
코드
import sys
input = sys.stdin.readline
N = int(input())
A = []
for _ in range(N):
mode = input()
if 'push' in mode:
modes, x = mode.split()
A.append(x)
if 'pop' in mode:
if len(A) !=0:
a = A[-1]
del A[-1]
print(a)
else:
print(-1)
if 'empty' in mode:
if len(A) !=0:
print(0)
else:
print(1)
if 'size' in mode:
print(len(A))
if 'top' in mode:
if len(A) !=0:
a = A[-1]
print(a)
else:
print(-1) 정말 직관적 ..^ ^
이 문제랑 큐 구현하는 거랑 똑같은데 스택을 큐로만 이용해서 구현하면 된다.
10773번 - 제로
입력을 K번 받는다.
입력 받은 값이 0이면 가장 최근 값을 지우고, 0이 아니면 해당 값을 쓴다.
그렇게 최종 값들의 합을 구하면 된다.
코드
import sys
input = sys.stdin.readline
K = int(input())
stack = []
for i in range(K):
num = int(input())
if num != 0:
stack.append(num)
else:
stack.pop()
print(sum(stack))0이면 최근 값 (= pop) 꺼내면 된다.
9012번 - 괄호
괄호가 쌍으로 ( ) 잘 구현되어있으면 YES / 쌍으로 ) ( 잘 안구성되어있으면 NO
출력하면 됨 !
코드
import sys
input = sys.stdin.readline
K = int(input())
for i in range(K):
A = input()
if A.count('(') != A.count(')'):
print('NO')
else:
while True:
a = A.replace('()','')
if '()' not in a:
break
A = a
if a.count('(') == a.count(')') and ')(' not in a:
print('YES')
else:
print('NO')우선적으로는 (와 )의 개수가 맞지 않으면 볼 필요도 없이 잘 구성되어있지 않는 것이다.
따라서, NO를 출력한다.
하지만 예외적으로, ( )와 쌍이 맞아도 안되는 경우가 있다.
예시를 보면 () )( () 이런 류의 예시도 있다. 개수는 짝이 맞지만 () 을 지워보면 나머지는 )( 인 것이다.
따라서, 더이상 () 이 남지 않을 때까지 replace을 이용하여 () 을 지워줬다.
그런 다음에 ( 와 )의 개수가 맞고, )(의 형태가 없는 경우 YES을 출력하고, 그 외는 NO을 출력한다.
4949번 - 균형잡힌 세상
[ 는 ] 로만! ( 는 )로만 잘 짝이 이루어져있는 경우를 판별하는 문제이다.
정규표현식 re
-
sub (패턴, 교체할 문자열, 문자열, 최대 교체 수, 플래그)
ex) re.sub (r"[0-9]", string ) -> string의 0-9를 공백으로 바꾼다 -
split (패턴, 문자열, 최대 split 수, 플래그)
ex) re.split( 'b' , 'abc' ) -> ['a','c'] -
findall (패턴, 문자열, 플래그) : 문자열 안에 있는 패턴에 맞는 케이스를 전부 찾아서 리스트로 반환
ex) re.findall('\d', '숫자123이 이렇게56 있다8')) -> ['1', '2', '3', '5', '6', '8'] -
match (패턴, 문자열, 플래그) : 문자열 처음부터 시작하여 작성한 패턴에 맞는지 확인 (y/n)
코드
import sys
input = sys.stdin.readline
import re
while (True):
string = str(input())
if string == '.\n' or string == '.':
break
newstring = re.sub(r"[a-zA-Z]","",string)
newstring = newstring.replace(" ","")
if newstring.count('(') != newstring.count(')') or newstring.count('[') != newstring.count(']'):
print('no')
else:
while (True):
newstring = newstring.replace('()',"")
newstring = newstring.replace('[]',"")
if '()' not in newstring and '[]' not in newstring:
break
if len(newstring) > 2:
print('no')
else:
print('yes')문자열이 . 로만 주어지면 그 값이 끝이라는 뜻이기 때문에 처음에 input에 대한 조건을 건다.
'.' 와 같다고만 뒀더니 가끔가다 '.\n' 로 주어지기도 해서 무한루프에 빠지곤 한다.
꼭 두 조건을 같이 둘 것 .. 나도 알고 싶지 않았다
그리고 입력 받은 문자열을 정규표현식과 replace을 이용하여 알파벳과 공백을 제거한다.
그 다음 (와 )의 쌍의 개수가 맞는지, [와 ]의 쌍의 개수가 맞는지 확인한다.
이 또한 쌍의 개수가 안맞으면 계산할 필요도 없이 안맞는 것.. ^ ^
만약 개수는 맞다면,
() 와 []가 더 없을 때까지 replace함수를 통해 없애준다.
만약 () 와 []을 더 이상 없었는데도 무엇인가 남아있다는 것은 ..? -> 안맞는 아이! 라는 것이기 때문에
newstring (=알파벳 및 맞는 쌍들을 제거한 것) 의 길이가 남아있다면 no을 출력하고
그 외는 yes을 출력한다.
길이를 2라고 둔 것은 문자열의 끝을 알리는 '.' 이 남아있기 때문이다.
'.' 와 공백이 같이 남아있기 때문에 길이가 2이상이면 쌍이 안맞는 것이 있다는 것이다.
따라서 이 조건을 걸어둔 것이다.
1874번 - 스택 수열
ㅎㅎ .. ㅜ
시작에 앞서서 너무너무 힘들게 이 문제를 탈출했기 때문에 .. ^ ^
문제
사실 별 거 없는 문제다
그래서 미쳐버리는 그런 거 먼지 알아요?
하하하
문제 풀이
우선 처음으로 나는 좀 돌아가는 방법으로 구현하긴 했다.
1부터 시작하는 값이 입력값보다 작으면 그 값이 될 때까지 더해주는 값을 stack에 추가해주고
그 값이 맨 끝이라면 pop 하는 구조로 생각했다.
그러다보니, 4 3 2 10 11 을 하게 되면 stack에 1 2 3 4 5 6 7 8 9 10 10 11 이런식으로
pop이 된 값을 저장하지 못하는 오류가 발생하게 되었다.
그래서 새롭게 answer이라는 배열을 또 다시 하면서 해당 배열에 이미 써진 값인지 확인하려 하였다.
그러다보니 시간초과가 났다. 이는 pypy3으로 실행하면 실행되긴 하였다.
시간복잡도 및 정답 배열을 지우고 간략화한 코드는 다음과 같다.
코드
import sys
input = sys.stdin.readline
N = int(input())
stack = []
answer = []
count = 1
realanswer = []
for _ in range(N):
A = int(input())
while count <= A:
stack.append(count)
realanswer.append('+')
count += 1
if stack and A == stack[-1]:
stack.pop()
realanswer.append('-')
else:
print('NO')
break
else:
for i in realanswer:
print(i)count 하는 값이 입력값보다 작거나 같을 때까지 스택에 값을 넣는다.
그리고 answer이라는 배열에 '+'을 같이 추가한다.
스택이 비어있지 않고, stack의 맨 끝 값이 입력값과 같다면 해당 값을 꺼낸다.
그리고 pop했기에 '-'을 추가한다.
만약 해당 경우가 아닌 경우, 스택이 제대로 구성될 수 없으므로 NO를 출력하고 끝낸다.
for문이 잘 끝났다면 realanswer에 추가된 값들을 차근히 출력한다.
후기
스택 정복 했나 >< ??????????????????????????????????????????
