AndroidTeacher

www.acmicpc.net/problem/17298

문제 설명

수열이 주어질 때, 수열의 각 원소Ai를 기준으로 오른쪽에 위치한 원소중 Ai보다 크면서 가장 왼쪽에 있는 수를 출력해야 한다. 단, 없을 경우 -1를 출력한다.

예를 들어, A=[3, 5, 2, 7] 이라는 수열이 있을 때 3의 오른쪽에 있으면서 3보다 큰 수 중 가장 왼쪽에 있는 원소는 5이고

5의 오른쪽에 있으면서 5보다 큰 수 중 가장 왼쪽에 있는 원소는 7이다.

그래서 [5, 7, 7, -1] 이라는 정답이 완성된다.

풀이 과정

처음 이 문제를 풀었을 때는, 스택을 사용하지 않고 이중for문을 이용하여 Ai를 기준으로 Ai+1 부터 n까지의 for문을 돌리며 Ai보다 큰 수를 만났을 때 break를 하는 방식으로 작성했다.

하지만 이 방식은 매번 N만큼의 for문을 돌면서 모든 원소들에 대해 실시해야 했기에 O(N^2)만큼의 시간복잡도가 발생했고 결국 시간초과를 초래했다.

그래서 stack을 이용하여 문제를 풀었다.

stack에는 원소값이 아닌 원소의 인덱스를 넣어주는 목적으로 사용하였다.

예를 들어, 3 5 2 7 이라는 수열이 있을 때

처음 스택에는 0이 들어가 있으며, A[1]과 A[stack[-1]의 원소를 비교한다.

stack[-1]은 0이기 때문에 A[1]과 A[0]을 비교하는 것이며, A[1]의 값이 더 크므로

answer[0]에는 A[1]의 값인 5를 넣어주게 되는 것이다. 즉 0의 오큰수를 구한 것이다.

그리고 0인덱스는 오큰수를 구했기 때문에 pop을 하고, 다음으로 구해야 할 인덱스 1을 넣어주는 것이다.

만약, 현재 i가 오큰수를 구하지 못했다고 하더라도 stack에 현재 인덱스i를 추가해야 한다.

그래야 이어서 i+1의 오큰수를 구할 수 있고, i+1의 오큰수를 구하면 자동으로 i의 오큰수도 구하게 되기 때문이다.

이러한 방식으로 각각의 인덱스에 대해 오큰수를 구해주면 된다.

import sys
n = int(input())
A = list(map(int, sys.stdin.readline().split()))
answer = [-1] * n
stack = []


stack.append(0)
for i in range(1, n):
    while stack and A[stack[-1]] < A[i]:
        answer[stack.pop()] = A[i]
    stack.append(i)


print(*answer)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/1874

문제 설명

문제가 조금 이해하기 어려울 수 있는데, 스택에 수를 push 할 때는 반드시 오름차순으로만 push할 수 있다.

예를 들어, 8을 push해야 한다면 앞의 1~7까지를 모두 push하고 8을 push할 수 있다.

그리고 스택을 쌓다가 필요한 타이밍에 pop을 하게 되는데, 이 pop을 한 수들을 쭉 나열했을 때,

N줄에 걸쳐 입력한 수열과 같아야 한다.

즉, 예제로 N=8이고 다음줄부터 4, 3, 6, 8, 7, 5, 2, 1을 입력한 상황을 예로 들어보면

내가 스택을 쌓다가 중간에 한번씩 pop을 한 데이터들을 나열한 순서도 4, 3, 6, 8, 7, 5, 2, 1이 되어야 한다는 것이다.

풀이 과정

위의 예제를 예로 들어 설명하면, 처음으로 4를 입력했다.

즉, 내가 첫 번째로 pop한 숫자가 4가 되어야 한다. 그러기 위해서는 1,2,3,4가 이미 스택안에 있어야 한다.

그래서 입력한 수를 만날 때 까지는 계속 push를 해서 1,2,3,4가 스택에 있도록 해야한다.

그리고 나서 4를 꺼내 스택은 현재 1,2,3인 상황이다.

그 다음으로 3이 주어졌기 때문에 push없이 현재 스택에서 pop을 하면 된다. 그리고 스택은 1,2가 된다.

그다음 입력으로 6이 주어졌기 때문에, 다시 6을 만날 때 까지 이전의 숫자들을 push 해준다. ( 즉 5, 6 push )

이 때, stack에서 pop할 숫자(TOP) 가 입력한 숫자가 아닐 경우(작을 경우) 정답을 완성할 수 없다.

왜냐하면 TOP 값이 입력한 숫자보다 크면, 입력한 수를 꺼내기 위해 계속 POP을 해야 하기 때문에

그 과정에서 POP한 수들의 수열이 정답과 일치하지 않게 되기 때문이다.

예를 들어 1, 2, 5, 3, 4가 입력으로 주어졌다고 하자.

1을 입력했을 때 스택은 [1] -> pop -> 1

2을 입력했을 때 스택은 [2] -> pop -> 2

5을 입력했을 때 스택은 [3, 4, 5] -> pop -> 5

3을 입력했을 때 스택은 [3, 4] -> pop -> 4 가 된다. 3이 먼저 나와야 하는데 4가 먼저 나와버린 것이다.

n = int(input())
stack = []
answer = []
flag = 0
cur = 1
for i in range(n):
    num = int(input())
    while cur <= num:       # 입력한 수를 만날 때 까지 오름차순으로 push
        stack.append(cur)
        answer.append("+")
        cur += 1
    # 입력한 수를 만나면 while문 탈출. 즉 cur = num일 때 까지 while문을 돌아 스택을 쌓는다.

    if stack[-1] == num:    # stack의 TOP이 입력한 숫자와 같다면
        stack.pop()         # 스택의 TOP을 꺼내 수열을 만들어 준다.
        answer.append("-")
    else:                   # stack의 TOP이 입력한 수가 아니면 주어진 스택을 만들 수 없다.
        print("NO")         # 왜냐하면 12345 처럼 오름차순으로 스택이 입력되는데
        flag = 1            # TOP이 num보다 크면 num은 TOP보다 더 아래에 쌓여있기 때문이다.
        break               

if flag == 0:
    for i in answer:
        print(i)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/4949

문제 설명

괄호들의 균형이 잘 맞춰져 있는지 확인하는 문제이다.

괄호는 소괄호"()"와 대괄호"[]"가 있으며 다음과 같은 규칙이 있다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

문제에서 문자열이 주어질 때, 그 문자열이 균형을 이루는 문장인지 확인하면 된다. 종료는 "."으로 한다.

풀이 과정

문자열을 처음부터 차례대로 검사하는데, 괄호가 등장하면 stack에 넣어준다.

1. 소괄호를 닫을 때 스택이 비어있거나, 스택의 top이 대괄호이면 잘못된 문장이다.

2. 대괄호를 닫을 때 스택이 비어있거나, 스택의 top이 소괄호이면 잘못된 문장이다.

3. 열린 괄호가 닫힌 괄호보다 많이 등장한다. ( 마지막에 stack이 비어있지 않을 때 )

이 세가지 경우를 제외하고는 짝을 맞춰 괄호가 등장한다.

import sys
while True:
    sen = sys.stdin.readline().rstrip()
    flag = 0
    stack = []
    if sen == '.':
        break
    for i in sen:
        if i == "(" or i == "[": #열린 괄호면 스택에 넣어준다.
            stack.append(i)
        elif i == ")": #닫는 소괄호가 등장했을 때
            if not stack or stack[-1] == "[": #열린 괄호가 없거나 열린 대괄호가 나오면
                print("no")
                flag = 1
                break
            else:
                stack.pop()
        elif i == "]": # 닫는 대괄호가 등장했을 때
            if not stack or stack[-1] == "(": #열린 괄호가 없거나 열린 소괄호가 나오면
                print("no")
                flag = 1
                break
            else:
                stack.pop()
    if flag == 0:   #앞서 no가 등장하지 않았을 때
        if not stack :  #스택이 비어있다 = 모든 괄호가 짝을 맞췄다
            print("yes")
        else:
            print("no")

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/9012

문제 설명

"( ( ) ) " or "( )( )" 등 괄호가 정상적으로 닫혔을 경우에는 YES 를 출력하고

"( ( ) ( " or "( ( ) " 등 괄호가 정상적으로 닫히지 않았을 경우에는 NO를 출력하는 문제이다.

풀이 과정

스택의 pop을 이용하기 때문에 가장 처음에는 " ) " 가 나와야 한다.

그리고 " ) " 를 꺼내지 않았는데 " ( " 가 나오는 경우도 정상적인 괄호가 아니다. ex)  " ()( " 

스택의 뒤에서 하나씩 괄호를 꺼내게 되는데 " ) " 를 만나면 count를 +1 해주고

" ( " 를 만나면 count를 -1 해준다.

이 때, count가 0이라는 것은 닫힌 괄호가 준비되지 않았다는 뜻이므로 NO를 출력해준다.

마지막에, 모든 괄호를 빼왔을 때도, count가 0이 아니라는 것은 짝이 맞지 않는다는 뜻이므로 NO를 출력한다.

import sys
t = int(input())
for i in range(t):
    count = 0
    stack = list(sys.stdin.readline().strip())
    flag = 0
    while len(stack) > 0:
        bracket = stack.pop()
        if bracket == ")":
            count += 1
        elif bracket == "(":
            if count == 0:
                print("NO")
                flag = 1
                break
            count -= 1
    if flag == 0:
        if count == 0:
            print("YES")
        else:
            print("NO")

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/10773

문제 설명

기본적인 스택을 이용한 문제이다.

첫째 줄에 입력할 정수의 개수 K를 입력하고 다음 K번 동안 정수를 입력받는다.

0일 경우 가장 최근에 넣은 수를 꺼내고, 나머지 경우에는 스택에 입력을 넣어주면 된다.

풀이 과정

0을 입력할 경우 가장 최근에 쓴 수를 지우라고 했으므로 스택의 pop 기능을 사용하면 된다.

마지막에는 sum함수를 이용해 스택의 모든 수를 더하면 된다.

k = int(input())
stack = []
for i in range(k):
    money = int(input())
    if money == 0:
        stack.pop()
    else:
        stack.append(money)

print(sum(stack))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/10828

문제 설명

스택을 직접 구현해보는 문제이다.

• push X: 정수 X를 스택에 넣는 연산이다.
• pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 스택에 들어있는 정수의 개수를 출력한다.
• empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
• top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

풀이 과정

파이썬의 경우 리스트에 stack의 기본 기능들이 내장되어 있다.

따라서 각각의 명령어에 맞게 구현만 해주면 된다.

import sys
n = int(input())
stack = []
for i in range(n):
    comm = sys.stdin.readline().strip()
    if comm[:4] == "push":
        stack.append(comm[5:])
    elif comm == "top":
        if len(stack) == 0:
            print(-1)
        else:
            print(stack[-1])
    elif comm == "pop":
        if len(stack) == 0:
            print(-1)
        else:
            print(stack.pop())
    elif comm == "size":
        print(len(stack))
    elif comm == "empty":
        if len(stack) == 0:
            print(1)
        else:
            print(0)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !