백준 algorithm heapq 최소힙 13334 우선순위 큐 1715 python

파이썬 알고리즘 : 철로, 카드 정렬하기

백준13334, 백준 1715

2023년 7월 29일 알고리즘 문제풀이

백준 13334번

문제 링크

1차 시도

나의 생각

사람들의 사무실 과 집 둘 중 좌표가 작은 것을 먼저 오게 한 후, 그것을 오름차순으로 배열에 정리하였다. 각 지점을 철로의 시작점으로 삼아 모든 case를 검사하며 최댓값을 업데이트했다. 다 검사해버리니 당연히 시간초과…

결과

오답

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

import sys
from heapq import heappop, heappush
n = int(sys.stdin.readline())
people = []
for _ in range(n):
    h,o = map(int,sys.stdin.readline().split())
    if h <= o:
        heappush(people,[h,o])
    else:
        heappush(people,[o,h])
d = int(sys.stdin.readline())
ans = 0
while people:
    cnt = 0
    x = people[0][0]
    for person in people:
        if person[0] >= x and person[1] <= x+d:
            cnt += 1
    ans = max(ans,cnt)
    heappop(people)
print(ans)

2차 시도

나의 생각

어떤 사람의 집과 사무실의 거리는 철로의 길이인 d보다 멀 수도있다. 이 사람은 철로를 어디에 설정하든 이용할 수 없다. 따라서 입력을 받을 때 이런 케이스를 지우려고 했다. 또한 정렬을 해버린 만큼 굳이 필요하지 않은 조건들도 제거하였다. 하지만 예외케이스가 있는지 오답처리되었다.

결과

오답

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

import sys
from heapq import heappop, heappush
n = int(sys.stdin.readline())
tmp_people = []
people = []
for _ in range(n):
    h,o = map(int,sys.stdin.readline().split())
    if h <= o:
        tmp_people.append([h,o])
    else:
        tmp_people.append([o,h])
d = int(sys.stdin.readline())
for person in tmp_people:
    if person[1]-person[0] <= d:
        people.append(person)
people.sort(key= lambda x:x[1])
ans = 0
k = len(people)
for i in range(k):
    cnt = 0
    x = people[i][0]
    for j in range(i,k):
        if people[j][0] > x+d:
            break
        if people[j][1] <= x+d:
            cnt += 1
    ans = max(ans,cnt)
print(ans)

3차 시도

나의 생각

다른 사람들의 코드와 설명을 한참 보고도 이해가 힘들었는데 겨우겨우 이해했다..

설명의 출처

우선 각 사람들의 집과 오피스를 상관하지 말고 좌표의 크기로만 생각한다. 입력값으로 주어진 좌표들을 담는다. 우선 집과 사무실의 거리가 철로의 거리보다 먼 사람들은 제외한다. 어떠한 경우에도 철로에 포함될 수 없기 떄문이다. 각 사람의 집과 사무실 좌표를 좌표 크기에 따라 오름차순 정렬한 후, 전체 배열을 왼쪽좌표의 오름차순으로 정렬한다. 같은 것들은 오른쪽 좌표를 기준으로 오름차순으로 정렬하였다.

핵심은 배열에 있는 각 사람의 오른쪽 점을 철로의 끝으로 생각하는 것이다.

정렬된 배열의 첫번째 사람의 오른쪽 점을 현재 철로의 끝점으로 생각한다. 아래 코드에서 x[1]이 이 점을 의미한다. x[1]-d는 철로의 끝점에서 철로의 길이만큼 뺸 것이니 철로의 시작점을 의미한다. 사람들을 heap에 담는 과정에서, 최소 힙이므로 최솟값이 0을 index로 하는 원소가 된다. 정확히는 왼쪽좌표가 가장 작은사람이다. x[1]-d로 구한 철로의 시작점보다 더 작은 좌표값을 왼쪽 점으로 가지는 사람은 더이상 철로에 포함되지 않는 사람이므로 heap에서 제거해야한다. 각 사람의 오른쪽 점을 철로의 끝점으로 삼고 사람을 옮겨가면서 현재 철로에 포함된 사람이자 heap에 들어있는 사람중 왼쪽 점이 최소인 사람을 조사해 이 사람이 철로에 포함되는지 검사하는 것이다. 포함되지 않는다면 제거하고 그 다음 최솟값으로 설정된 사람을 조사하면 된다. 포함된다면? 더이상 조사할 필요가 없다. 왼쪽점의 오름차순으로 정렬되어있으므로 당연히 다음 원소들은 철로에 포함되는 사람들일 것이다. 혹여나 이해가 힘든 사람들을 위해 마지막 최댓값을 구하는 과정을 조금 더 간결하게 정리해보겠다.

  1. 모든 사람은 집과 사무실을 가진다. 하지만 이제부터 왼쪽 점과 오른쪽 점을 가진다고 생각하자. 그게 집이든 사무실이든 상관없다.
  2. 왼쪽 점과 오른쪽 점의 거리가 철로보다 긴 사람들도 있을 수 있다. 그 사람들이 철로안에 두 점을 모두 포함시킬 방법은 없다.
  3. 따라서 우선적으로 배열에서 제거한다.
  4. 배열에 남은 사람들을 우선 왼쪽점의 좌표를 기준으로 오름차순 정렬하고, 왼쪽 점이 같다면 오른쪽 점을 기준으로 오름차순 정렬한다.
  5. 배열된 사람들을 하나씩 주목한다. 이는 검사를 위해서가 아니라 철로의 설정을 위해서이다. 검사를 위해 heap 배열을 새로 만든다.
  6. 주목한 사람의 오른쪽 점을 철로의 끝으로 설정한다. 그리고 주목한 사람은 heap 배열에 넣는다.
  7. heap 배열의 0번 index는 최솟값이 와야한다. 그말은 왼쪽 좌표의 값이 가장 작은 사람이라는 뜻이다.
  8. 지금 주목한 사람의 오른쪽 점은 철도의 끝점이다. 그럼 철도의 시작점은 이 점에서 철도의 길이인 d를 뺴면 된다.
  9. heap의 최솟값과 철도의 시작점을 비교한다. 최솟값이 더 작다면 제거한다. 철도밖에 왼쪽 점이 있다는 뜻이기 떄문이다.
  10. 이 검사를 heap 내에 있는 모든 사람을 대상으로 검사한다.
  11. 결국 heap에는 철도에 포함되는 사람들의 수만 남게 된다. 이 수를 최댓값과 비교하며 업데이트한다.
  12. 왼쪽 점이 철도에 포함된다면 heap에서 빠지지 않는다. 철도의 끝점이 바뀌어도 heap에 남게된다.

결과

이해 완료

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

import sys
from heapq import heappush, heappop

n = int(sys.stdin.readline())
people = []
for _ in range(n):
    person = list(map(int, sys.stdin.readline().split()))
    people.append(person)

d = int(sys.stdin.readline())
arr = []
for person in people:
    house, office = person
    if abs(house - office) <= d:
        person = sorted(person)
        arr.append(person)
arr.sort(key=lambda x:x[1])

ans = 0
heap = []
for x in arr:
    if not heap:
        heappush(heap, x)
    else:
        while heap[0][0] < x[1] - d:
            heappop(heap)
            if not heap:
                break
        heappush(heap, x)
    ans = max(ans, len(heap))

print(ans)

백준 1715

문제 링크

1차 시도

나의 생각

쉬운 문제인듯 했으나 규칙을 잘못파악해서 오래걸렸다. 나는 카드 더미중 가장 작은 두개를 더한 다음, 차례차례 그 다음으로 작은 값을 더해주면 된다고 생각했다. 그래서 두개를 더한 후 그 값을 2배한 뒤 그 다음 작은 값을 heappop하여 더해주는 방법을 이용했으나 틀렸다. 안되는 이유는 예시를 통해 금방 알 수 있다.

카드 더미가 10 20 15 21 40 으로 이루어진 5개라고 생각해보자. 기존의 내 코드에 의하면

  1. 10 + 15 = 25
  2. 25 * 2 = 50
  3. 50 + 20 = 70
  4. 70 * 2 = 140
  5. 140 + 21 = 161
  6. 161 * 2 = 322
  7. 322 + 40 = 362 이라는 결과가 도출된다. 실제 정답과의 차이는 2번에서 발생한다.

10과 15를 더하여 25라는 비교 횟수를 구하고 나면 카드더미는 25,20,21,40 4개가 된다.

애초에 문제를 이렇게 4개짜리를 받았다면 내 로직으로는 당연히 20과 21을 더하면서 시작해야한다.

근데 내 첫 로직은 25와 20을 더한다! 처음 더미를 합친 25에 25+20을 더해서 70을 도출한 결과가 3번이다. 여기서 문제가 발생하여 오답이였다. 따라서 현재 카드 더미중 가장 작은 두개의 값을 더한 후 다시 배열에 넣어 가장 작은 2개를 새롭게 찾아내야 한다.

결과

정답

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

import sys
from heapq import heappop, heappush
n = int(sys.stdin.readline())
cards = []
for _ in range(n):
    card = int(sys.stdin.readline())
    heappush(cards,card)

cnt = 0
ans = 0

if n == 1:
    ans = 0

elif n == 2:
    tmp1 = heappop(cards)
    tmp2 = heappop(cards)
    ans = tmp1 + tmp2

else:
    while len(cards) > 1:
        tmp1 = heappop(cards)
        tmp2 = heappop(cards)
        tmp = tmp1 + tmp2
        ans += tmp
        heappush(cards,tmp)
ans += heappop(cards)
print(ans)
CATALOG
    algorithm