[백준] 17413, 10799, 17298 (파이썬)

알고리즘 기초1 문제를 이어풀었다. 문제에 대한 이해력은 확실히 는 것 같으나, 오큰수 문제가 상당히 오래걸렸다. 지금까지 풀었던 알고리즘 중 최고 난이도여서 그럴수도 있다고 생각한다. 시간초과로 인해 꽤나 고생하기도 했다. 다른 개발자들의 코드를 참고하면서 시간초과 없이 효율적으로 문제를 푸는데 중점을 두었다.

백준 17413번 단어 뒤집기 2

from sys import stdin
S = stdin.readline().rstrip()
tag = True
stack = ''
ans = ''
for i in S:
    if i == '<':
        tag = False
        ans += stack[::-1] # 처음부터 끝까지 역순으로 
        ans += i
        stack = ''
        continue
    elif i =='>':
        tag = True
        ans += i
        continue
    elif i == ' ':
        ans += stack[::-1]+i
        stack = '' 
        continue
    if tag==True:
        stack+=i  
    elif tag==False:
        ans+=i
print(ans+stack[::-1])

백준 10799번 쇠막대기

# (이 나오면 stack에 넣음
# ()이 나오면 현재 스택에 있는 ( 수만큼 ans에 더함 
# )이 나오면 stack의 (를 pop하고 ans에 1을 더함
from sys import stdin
iron = stdin.readline().rstrip()
iron_list = list()
stack = list()
ans = 0
for j in iron:
    iron_list.append(j)
for i in range(len(iron_list)):
    if iron_list[i] == '(':
        stack.append('(')
    elif iron_list[i] == ')':
        if iron_list[i-1] =='(':
            stack.pop()
            ans += len(stack)
        elif iron_list[i-1] == ')':
            if len(stack)!=0:
                stack.pop()
                ans +=1        
print(ans)

백준 17298번 오큰수

'''시간초과 
from sys import stdin
N = int(stdin.readline())
num = [i for i in stdin.readline().split()]
nge = list()
new_num = list()
count = 0
for i in num:
    new_num = num[count+1:]
    count +=1
    if len(num)==count:
        nge.append('-1')
    for j in new_num:
        if i>max(new_num):
            nge.append('-1')
            break
        else:
            if i<j:
                nge.append(j)
                break
print(' '.join(nge))
'''
# 많이 막혔다. 추후 다시 복습할 것
from sys import stdin
N = int(stdin.readline())
num = [i for i in map(int,stdin.readline().split())]
stack = list()
answer =[-1] * N
for i in range(N):
    while stack and num[stack[-1]]<num[i]:
        # 오큰수를 구하지못하면 stack에 쌓아둠
        # 이후 오큰수를 구하면 stack에 쌓아둔 list도 동일 오큰수 
        answer[stack[-1]] = num[i]
        stack.pop()
    stack.append(i)
print(*answer) # *list : list 원소출력