스택 알고리즘

: FILO 후입선출 구조

탑

2493번: 탑

lst = [0] * N
for i in range(1,N):
  for j in range(i-1,-1,-1):
    if arr[j] >= arr[i]:
      lst[i] = j+1
      break

완전탐색으로 풀었을 때 백준에서 시간초과가 뜬다

스택..

후입선출

[6,9,5,7,4]

[0,0,2,2,4]

스택에서 pop해서 현재 값이랑 비교

작으면 현재 인덱스 push

크면 그대로 push print

6 → 6

9 → stack[-1] 비교 pop 9 push

5 → stack[-1] 비교 5 push

7 → stack[-1] 비교 pop(), 비교 7 push

4 → stack[-1] 비교

for i in range(1,N):
  while stk:
    if arr[stk[-1]] > arr[i]:
      lst[i] = stk[-1] + 1
      break
    else:
      stk.pop()
  stk.append(i)

원 영역

10000번: 원 영역

left list 랑 right list 를 만들어서

리스트 안에 같은 값이 있으면 내접한 상태니까 +1

리스트 끼리 비교해서 같은 값이 있으면 외접한 상태니까 +2

이게 될거라고 생각은 안했는데 입력 예시를 계산해보니까 출력이 잘 나올 것 같았다 ( 그래도 완전 탐색으로 구해야 해서 시간, 메모리 다 초과 나올 듯.. )

그래서 검색과 설명을 들은 결과→

원과 x축이 만나는 지점들을 오른쪽 왼쪽 구분해서 리스트에 넣고

정렬한 뒤,

위치가 같은 원들을 겹치는 부분이라고 판단해서 영역을 구분하고

카운팅

for i in range(N*2):
    x, y = arr[i]
    
    if not stk:
        # 스택 비어있으면 추가
        stk.append({'x':x,'y':y,'stat':0})
        continue
    
    if y == 'e':
        # 원이 하나 끝나면 area 추가
        cnt+=1
        
        if stk[-1]['stat'] == 1:
            cnt+=1
        stk.pop()
        
        # 다음 점과 접점 여부 확인 (마지막 값이 아니면서, x 가 같지 않을때)
        if i != N*2-1 and arr[i+1][0] != x:
                stk[-1]['stat'] = 0
      
    else:
        # 스택의 마지막 좌표와 위치가 같을 때, 상태 1로 바꿈
        if stk[-1]['x'] == x:
            stk[-1]['stat'] = 1
        stk.append({'x':x,'y':y,'stat':0})

크게 만들기

2812번: 크게 만들기

처음에 생각한 방향은

해당길이의 모든 조합을 구할 생각이었는데

아무리 생각해도 너무 바보같은 생각이어서

다른 사람들의 뇌를 참조했다

입력받은 문자열에서 숫자 하나씩 가져와서

스택의 마지막값과 비교해서 크거나, 같은 값이 나올때 까지 pop

조건이 안 맞으면 stack

stack에서 자릿수 만큼 문자열로 출력

'''
1231234
3234
'''
stack = []
m = N-K

for i in range(N):
    # 스택에 값이 있으면서, 뺄 값이 남아있고, 스택 마지막값보다 크면 pop()
    while stack and K > 0 and num[i] > stack[-1]:
        stack.pop()
        K -= 1
    stack.append(num[i])
    
# 빼야할 값들이 다 빠지지 않을 수도 있으니, 고정 자릿수까지만 출력
print("".join(stack[:m]))