[알고리즘 기초 1/2] 자료구조 1

토익 한다고 백준을 안했다.
그렇다고 토익을 잘 봤느냐? 그것도 아님 하하..
멘탈 나가서 백준이라도 해야겠다..

앞으로 백준 강의에 있는 문제들을 찬찬히 풀어나가려고 한다.

10799번: 쇠막대기

레이저가 나오면 덱에 쌓여있는 (를 카운트해서 더해주었다.
레이저가 아니고 막대기의 끝인 )이라면 +1 해주어 막대기를 절단냈다.

이런 식으로..

str = input('')

from collections import deque

answer = 0
dq = deque()

for i in range(len(str)) :
    # 레이저라면
    if (dq and str[i - 1] == '(' and str[i] == ')') :
        dq.pop()
        answer += len(dq)
    elif (str[i] == '(') :
        dq.append('(')
    # 닫히는 경우
    elif (str[i - 1] != '(' and str[i] == ')' and dq[-1] == '(') :
        dq.pop()
        answer += 1

print(answer)

코드는 이러하다.
결과는 성공

17298번: 오큰수

오큰수의 경우에는 어려워서 다른 풀이를 참고했다.
스택에 stack[-1][0]보다 더 큰 수가 나오면 pop()을 하면서 answer 리스트를 갱신해주는 방식이다.

출처 : https://hooongs.tistory.com/329

n = int(input())
a = list(map(int, input().split(' ')))

from collections import deque

stack = deque()
answer = [-1] * n

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

print(*answer)

17299번: 오등큰수

오큰수를 풀고 나서 푸니까 쉽게 풀렸다.

오큰수와는 달리 숫자가 등장하는 개수를 기준으로 오큰수와 동일하게 진행해주면 된다. 오큰수의 경우 Ai를 기준으로 stack을 넣고 빼줬다면, 오등큰수의 경우는 기준이 F(Ai)라는 것이다.

F(Ai)를 구하는 방법은 간단하다. Counter를 쓰면 된다. 카운터를 사용하면 요소의 개수를 {요소i : 개수i}의 형태로 반환해주어 찾기 쉽다. 시간복잡도는 O(1)이다.

from collections import Counter, deque

n = int(input())
arr = list(map(int, input().split(' ')))

counter = Counter(arr)
stack = deque()
answer = [-1] * n

for i in range(n) :
    while (stack and stack[-1][1] < counter[arr[i]]) :
        tmp, fai, idx = stack.pop()
        answer[idx] = arr[i]
    stack.append([arr[i], counter[arr[i]], i])

print(*answer)

1953번: 후위 표기식2

후위표기식의 경우, A/B를 AB/로 나타내는 것을 말한다.
stack에 넣어서 팝팝.. 팝.. 팝 유 원 잇

n = int(input())
str = input()
arr = []

for i in range(n) :
    arr.append(int(input()))

from collections import deque
stack = deque()

for i in str :
    if (i <= 'Z' and i >= 'A') :
        idx = ord(i) - ord('A')
        stack.append(arr[idx])
    if i in '*/+-' :
        b = stack.pop()
        a = stack.pop()

        if i == '*' :
            stack.append(a * b)
        elif i == '/' :
            stack.append(a / b)
        elif i == '+' :
            stack.append(a + b)
        elif i == '-' :
            stack.append(a - b)

print("{:.2f}".format(stack[-1]))

다 해놓고 도대체 어떻게 소수점 두자리만 출력해야되는건지 몰라서 구글링을 했다.. 공부 좀 하자^^>..

10824번: 네 수

a, b, c, d = input().split(' ')

num1 = int(a + b)
num2 = int(c + d)

print(num1 + num2)