[TIL] 백준 풀이 정리2

※ 평일에 풀지 않고 넘긴 문제 풀이 ※

1. 8983번 - 사냥꾼

import sys

# M : 사대 개수
# N : 동물의 수
# L : 사정거리
M, N, L = map(int, sys.stdin.readline().split())

gun = list(map(int, sys.stdin.readline().split())) # 사대의 위치
gun.sort()

animal = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] # 동물들의 위치

def hunt(gun, animal) :
    count = 0
    # 동물의 위치를 반복
    for x, y in animal :
        min_idx, max_idx = 0, len(gun)-1
        # 동물을 잡을 수 있는 위치를 이분 탐색
        while min_idx <= max_idx :
            mid_idx = (min_idx + max_idx) // 2
            length = abs(gun[mid_idx] - x) + y
            if length <= L :
                count += 1
                break
            else :
                # 동물의 위치보다 사대가 오른쪽에 있으면 max 값 감소
                if gun[mid_idx] > x :
                    max_idx = mid_idx - 1
                # 동물의 x 위치보다 사대가 왼쪽에 있으면 min 값 증가
                else :
                    min_idx = mid_idx + 1
    print(count)        

hunt(gun, animal)

처음에 문제를 접했을 때 그래프부터 보이고 훑어봤을 때는 사대의 위치에 따라 동물의 수를 구하는 것인줄 알았다.
그러나 읽어보니 어떤 사대에서 잡든 그냥 잡을 수 있는 동물의 수만 구하면 되는 문제였다.
동물의 위치 리스트만큼 반복하면서 전체 사대에 대해 이분 탐색을 통해 잡을 수 있는지 없는지 판별만 하면 되도록 코드를 작성했다.

---

2. 2504번 - 괄호의 값

import sys

# 입력값 : 뒤에 개행문자 제거
s = sys.stdin.readline().strip()

def getScore(s) :
    stack = [] # (괄호, status : 현재 괄호 속 값)
    score = 0
    
    for i in s :
        # 열린 괄호일 경우
        if i == '(' or i == '[' :
            stack.append({'i': i, 'status':0})
        # 닫힌 괄호이면 스택 안에 무조건 값 존재해야 올바르다.
        elif stack :
            if i == ')' and stack[-1]['i'] == '(':
                current = stack.pop()
                if current['status'] == 0 :
                    if stack :
                        stack[-1]['status'] += 2
                    else :
                        score += 2
                else :
                    if stack :
                        stack[-1]['status'] += 2 * current['status']
                    else :
                        score += 2 * current['status']
            elif i == ']' and stack[-1]['i'] == '[' :
                current = stack.pop()
                if current['status'] == 0 :
                    if stack :
                        stack[-1]['status'] += 3
                    else :
                        score += 3
                else :
                    if stack :
                        stack[-1]['status'] += 3 * current['status']
                    else :
                        score += 3 * current['status']
            # 스택에 올바른 짝으로 존재하지 않았으면 잘못된 경우
            else :
                score = 0
                break
        else :
            score = 0
            break
    print(score)

getScore(s)

괄호가 완성되면 스택이 빈다는 성질을 이용해서 score에 저장할 때를 정해주었다.
그 외에는 스택에 저장할 때 현재 상태값이라는 값을 같이 추가해줘서 이를 이용하여 현재 계산하고 있는 값을 업데이트해주었다.

---

3. 2812번 - 크게 만들기

import sys

N, K = map(int, sys.stdin.readline().split())
num = sys.stdin.readline().strip()

def max_value(num) :
    stack = []
    count = K
    
    for i in range(len(num)) :
        # 스택에 값이 존재하고 현재 값보다 작은 스택 내의 값은 모두 삭제
        while stack and stack[-1] < num[i] and count > 0 :
            stack.pop()
            count -= 1
        stack.append(num[i])
    
    # N-K = 원래 입력값에서 필요한 수 만큼 지운 후의 결과값 길이
    # K번의 지우기 수행을 하지 못했을 경우도 존재 -> 스택의 길이 > 결과값의 길이
    # 스택은 최댓값부터 쌓이도록 했기에 뒤에 필요없는 값 제거
    # ex) 6 2 / 989999
    print(''.join(stack[:N-K]))

max_value(num)

스택을 이용하여 문제를 풀긴 했는데 시간초과
내 코드 안에는 반복문 속 조건문이 너무 많았다. 계속해서 줄일려고 했지만 너무 헷갈려서 블로그를 참고했다.
<참고 블로그>  https://jokerldg.github.io/algorithm/2021/05/25/make-big.html 

while문으로 간단하게 스택에 최댓값부터 쌓일 수 있게 만드는 것은 이해하기 쉬웠다.
그러나 마지막 출력시 발생하는 예외 상황을 생각해본적이 없어서 틀렸었다.
주석으로 작성한 내용처럼 다양한 입력 상황을 생각해보고 이를 포함하여 해결할 수 있는 코드를 짜도록 노력해야겠다.