[PY] <!> 하자있는 채로 풀었던 내용들

내가 직접 손 쓴 것이 거의 없는데 과연 블로그에 글을 쓰는게 맞을까라는 생각이 들었던 이번 주였다.
그래서 시간이 남는다면 (부디 그렇다면 좋겠다) 다시 눈여겨 봐야 할 문제들에 대해 정리 해두려고 한다.

우선순위 큐를 사용해서 해낼 수 있는 문제(들) :

1655 : 가운데를 말해요

https://www.acmicpc.net/problem/1655

우선순위 큐는 최대 힙 또는 최소 힙을 사용해서 만들어지는데, 꼭 큐의 형태를 생각하지 않더라도 항상 첫번째 원소가 최대 또는 최소를 가리키는 배열 두 개를 갖고 중앙값을 찾아야 하는 문제라고 생각하면 보다 직관적으로 생각 할 수 있었다.

하지만.. 이 아이디어에서 더 진도를 나가지 못했다. 뭔가 더 많이 떠올려야 하는데 이어가지질 않았다.
뒤에 일정이 예정 되어 있는게 많았기에 많은 시간을 들일 수 없었다. 

import heapq, sys

n = int(sys.stdin.readline())

leftHeap = []
rightHeap = []

for i in range(n):
    num = int(sys.stdin.readline())

    if len(leftHeap) == len(rightHeap):
        heapq.heappush(leftHeap, -num)
    else:
        heapq.heappush(rightHeap, num)


    if rightHeap and rightHeap[0] < -leftHeap[0]:
        leftVal = heapq.heappop(leftHeap)
        rightVal = heapq.heappop(rightHeap)

        heapq.heappush(leftHeap, -rightVal)
        heapq.heappush(rightHeap, -leftVal)

    print(-leftHeap[0])

1715 : 카드 정렬하기

https://www.acmicpc.net/problem/1715

의미있는 아이디어를 도출 하지 못했다. 근데 정답 처리 코드는 무척 쉽게 구성되어있던 걸 보면 조금 생각하면 어떻게 됐겠다 생각은 든다.

import sys, heapq

n = int(sys.stdin.readline())

cards = []
count = 0

for _ in range(n):
    heapq.heappush(cards, int(sys.stdin.readline()))

while len(cards) != 1:
    temp = heapq.heappop(cards) + heapq.heappop(cards)
    count += temp
    heapq.heappush(cards, temp)

print(count)

13334 : 철로

https://www.acmicpc.net/problem/13334

앞의 케이스처럼 의미있는 아이디어를 도출하지 못했다.

import sys
import heapq

# 입력값 받기
n = int(sys.stdin.readline().strip())
locations = [] # ([(시작 좌표, 끝 좌표) ...]
for _ in range(n):
    h, o = map(int, sys.stdin.readline().strip().split())
    # 집과 사무실 중 좌표값이 낮은 것을 앞에, 좌표값이 높은 것을 뒤에 넣어줌
    locations.append((min(h, o), max(h, o)))
d = int(sys.stdin.readline().strip())

# 선분의 끝점을 기준으로 오름차순 정렬한 다음, 앞점을 기준으로 오름차순 정렬
locations.sort(key=lambda x: (x[1], x[0]))

heap = []
max_cnt = 0

for location in locations: # 각 사람의 좌표를 기준으로 반복문 돌기
    start, end = location
    heapq.heappush(heap, start) # 최소 힙. pop했을 때 start가 작은 것부터 나올 수 있도록
    line_start = end - d # 현재 사람의 끝 좌표를 기준으로 철로의 시작 지점 계산
    while heap and heap[0] < line_start: # heap[0] = 힙에 저장된 시작 지점 중 최소값
        heapq.heappop(heap) # 철로의 시작 지점보다 시작 좌표가 작은 경우 철로를 벗어나므로 pop
    max_cnt = max(max_cnt, len(heap)) # 현재 철로에 포함되는 사람 수가 최대값인 경우 갱신

print(max_cnt)

분할정복을 사용해서 해낼 수 있는 문제(들) :

2261 : 가장 가까운 두 점

이 문제를 풀기 전에 히스토그램에서의 최대 직사각형 문제를 풀었었는데 이 곳에도 적용 할 수 있을까를 고민했다. 아쉽게도 더 이어 갈 순 없었다. 적어 내려오면서 생각해 본건데, 구체화하는데 뭔가 좀 정성을 더 들여야 할 듯.

import sys

n = int(sys.stdin.readline())

points = []

for _ in range(n):
    x, y = map(int, input().split())
    points.append((x, y))

points.sort()

def computeMinDist(start, end):
    min_dist = int(1e10)
    for i in range(start, end - 1):
        for j in range(i + 1, end):
            dist = (points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2
            min_dist = min(min_dist, dist)
    return min_dist

def findMinDist(start, end):
    size = end - start
    if size < 3:
        return computeMinDist(start, end)
    
    mid = (start + end) // 2

    left = findMinDist(start, mid)
    right = findMinDist(mid, end)

    min_dist = min(left, right)

    check_point = []
    divide_x = points[mid][0]

    for i in range(start, end):
        if (points[i][0] - divide_x)**2 <= min_dist:
            check_point.append(points[i])
    check_point.sort(key=lambda x:x[1])

    for i in range(len(check_point)):
        now = check_point[i]
        for j in range(i + 1, len(check_point)):
            compare = check_point[j]
            if(compare[1] - now[1])**2 >= min_dist:
                break
            dist = (now[0] - compare[0])**2 + (now[1] - compare[1])**2
            min_dist = min(min_dist, dist)
    return min_dist

print(findMinDist(0, n))

# https://codable.tistory.com/4

스택을 사용해서 해낼 수 있는 문제(들)

10000 : 원 영역

https://www.acmicpc.net/problem/10000

대체 이걸 스택으로 할 수 있다고 어떻게 상상하지? 난 이 시점에서 이 문제에 대한 내용을 놔버렸다.

import sys
n = int(sys.stdin.readline())

circles = []
for _ in range(n):
    x, r = map(int, sys.stdin.readline().split())
    circles.append(("L", x - r))
    circles.append(("R", x + r))

circles.sort(key=lambda x: (x[0]), reverse=True)
circles.sort(key=lambda x: x[1])

stack = []
count = 1

for circle in circles:
    if circle[0] == "L":
        stack.append(circle)
        continue


    total_width = 0
    while stack:
        prev = stack.pop()

        if prev[0] == "L":

            width = circle[1] - prev[1]

            if total_width == width:
                count += 2
            else:
                count += 1

            stack.append(("C", width))
            break
        elif prev[0] == "C":
            total_width += prev[1]
print(count)

# https://e-juhee.tistory.com/entry/python-%EB%B0%B1%EC%A4%80-10000-%EC%9B%90-%EC%98%81%EC%97%AD-%EC%8A%A4%ED%83%9D

2504 : 괄호의 값

https://www.acmicpc.net/problem/2504

여기 문제 중에서 할만한 문제 중 하나였다. 나중가니 더 요상한 내용을 요구해서 하다가 말았지만..

import sys

arr = sys.stdin.readline()
stack = []

answer = 0
tmp = 1

for i in range(len(arr)):
    if arr[i] == '(':
        stack.append(arr[i])
        tmp *= 2
    elif arr[i] == '[':
        stack.append(arr[i])
        tmp *= 3
    elif arr[i] == ")":
        if not stack or stack[-1] == "[":
            answer = 0
            break
        if arr[i - 1] == "(":
            anwser += tmp
        stack.pop()
        tmp //= 2
    else:
        if not stack or stack[-1] == "(":
            answer = 0
            break
        if arr[i - 1] == '[':
            answer += tmp
        stack.pop()
        tmp //= 3

if stack:
    print(0)
else:
    print(answer)


# https://velog.io/@rhdmstj17/%EB%B0%B1%EC%A4%80-2504%EB%B2%88-%EA%B4%84%ED%98%B8%EC%9D%98-%EA%B0%92-python-stack-%EC%9E%90%EC%84%B8%ED%95%9C-%ED%92%80%EC%9D%B4

2812 : 크게 만들기

얘는 시도중이다.