📚 TIL

📌 오늘의 문제

✔ 백준 2805 나무자르기 (이분탐색 알고리즘)

N,M=map(int,input().split(' '))
trees=list(map(int,input().split(' ')))
left=1
max_height=0
right=max(trees)-1
while left<=right:
    #설정한 절단기 높이
    mid=(left+right)//2
 
    #상근이가 가져가는 나무의 길이
    total=0
    for tree in trees:
        result=tree-mid
        if result>0:
            total+=result
    if total>M:
        max_height=max(max_height,mid)
        left=mid+1
    elif total==M:
        max_height = max(max_height, mid)
        break
    else:
        right=mid-1

print(max_height)

python 은 시간초과가 나서 pypy3으로 풀었다.
처음에는 total이 M보다 큰 경우에 답이 찾아질 수 있는 경우를 생각하지 못하고 total이 M과 같아진 경우에만 break를 하고 답을 구했다.
하지만 같아질 수 없는 경우가 존재할 수도 있으니 이 때는 M이 만들어질 수 있는 최대의 높이를 구해야한다.
그래서 경우를 3가지로 나누어서 문제를 풀었다.

✔ 백준 1021 회전하는 큐 (스택,큐 알고리즘)

# 데크
import sys
from collections import deque

input = sys.stdin.readline  # 빠른 입력
N, M = map(int, input().split())
loc = list(map(int, input().split()))

deque = deque([i for i in range(1, N+1)])

find = 0
count = 0

while (True):

    if deque[0] == loc[find]:
        deque.popleft()
        find += 1
        if find == M:
            break
    else:

        if deque.index(loc[find]) < abs(deque.index(loc[find]) - len(deque)):
            deque.append(deque.popleft())
        else:
            # 3번의 경우
            deque.appendleft(deque.pop())
        count += 1

print(count)

이번에는 deque에 index 메소드가 없다는 생각을 해서 문제를 못풀었다.
하지만 옛날에 풀었던 내 코드를 보았더니 index 메소드가 떡하니 있었다 ^^
한 한시간은 고민한 것 같은데 ....ㅎㅎ

• 우선 찾아야할 숫자는 리스트에 넣고 1부터 N까지 숫자는 deque에 넣었다
• 숫자를 차례대로 순회하면서 찾는 숫자가 0번 index에 있다면 popleft 시켜주고 1개의 숫자를 찾았으니 find+=1 시켜주었다
• 찾는 숫자가 0번 index에 없다면 deque에서 index를 찾아주어 2번 연산을 할지 3번 연산을 할지 결정해주는 알고리즘이 point!!

8개월전에 풀었는데 이때는 알고리즘 문제 꽤 열심히 꾸준히 풀었던 때였다..ㅎㅎ
이때보다 실력의 발전은 없는 것 같다
꾸준히 푸는게 중요하다고 오늘 다시금 깨달았다