수학과의 개발자 도전기

- 문제 : https://www.acmicpc.net/problem/2075

문제 이해 

문제 자체를 이해하는 데는 그렇게 어렵지 않았다. 주어진 N^2개의 수 중에서 N번째 수를 구하면 된다. 

그런데 N이 최대 1500이므로 N^2개의 원소를 하나의 배열에 모으고, 그걸 정렬하는데는 O(N^2)의 시간 복잡도가 발생한다. 그래서 다른 방법으로 진행해야하는데 이 때 힌트가 될만한 게, 하나의 열에서는 크기 순서대로 행이 정렬되었다는 것이다. 따라서 시간 복잡도 + 같은 열에서는 원소 오름차순 정렬 이라는 조건으로 heap을 사용해 문제를 해결할 수 있다. 

여기에서 heap을 사용하는 대상이 주어진 배열이 아니라, heap이라는 새로운 배열을 heap으로 진행해야한다. 

풀이 로직

- heap이라는 배열을 heap으로 적용하는데, heap 배열의 길이는 최대 N개가 될 수 있다. 

- 먼저 주어진 값을 temp로 받은 뒤 각 temp의 각 원소(each)를 탐색하는데 len(heap)의 값에 따라 다르게 진행한다.

1. len(heap) < n 인 경우는 each를 heap에 그냥 넣는다.

2. len(heap) >= n 인 경우는 heap의 첫 번째 원소는 배열의 최솟값이므로 만약 each > heap[0] 이라면 heappop()을 한 뒤 each 값을 넣는다 

- 반복문을 끝낸 뒤 heap에 남은 값들은 주어진 수를 정렬했을 때 heap[0] 값이 전체에서 n번째 수이므로 heap[0]을 출력한다.

정답풀이 

import heapq

n = int(input())
heap = []

for _ in range(n):
    temp = map(int, input().split())
    for each in temp:
        if len(heap) < n:
            heapq.heappush(heap, each)
        else:
            if heap[0] < each:
                heapq.heappop(heap)
                heapq.heappush(heap, each)
                
print(heap[0])

참고 블로그 

[BOJ] 2075 N번째 큰 수

- 문제 : https://www.acmicpc.net/problem/14235

문제 이해

- 문제 설명이 이해하기가 좀 어려웠다. 일단 이해한바로는 n개의 숫자 혹은 숫자 배열이 주어진다.

- 숫자가 0인 경우는 gifts 배열에서 가장 큰 값을 출력하면 되고, 만약 gifts에 숫자가 없다면 -1 을 출력한다. 

- 숫자 배열 a가 주어진 경우라면 a[0]은 배열 a의 마지막 인덱스를 의미하고, a[1] ~ a[a[0]]의 값을 gifts 배열에 추가하면 된다.

- 숫자가 0일 때 gifts에서 가장 큰 값을 출력해야하므로 최대 heap으로 풀어야 하는 문제다. 최대 Heap이니 숫자들의 값에 -1을 곱해서 heappush를 하면 된다. 

정답 풀이 

import heapq

n = int(input())
gifts = []

for _ in range(n):
    a = list(map(int, input().split()))
    
    if a[0] == 0:
        if len(gifts) == 0:
            print(-1)
            continue
        else:
            print(-1 * heapq.heappop(gifts))
            
    if a[0] != 0 :
        for i in range(1, len(a)):
            heapq.heappush(gifts, -a[i])

- 문제 : https://www.acmicpc.net/problem/1417

문제 이해 

- 후보 1번을 포함한 n명의 후보의 예상 투표 개수가 주어지는데, 1번 후보가 가장 큰 값을 가질 수 있게 만드는 문제다

- 1번이 가장 많은 예상 득표수를 가져야하므로, 2번 - n번의 후보들 중 가장 득표수가 많은 후보를 뽑아 그 후보의 득표수를 줄이면 된다

- heap을 사용하는 이유는 2번 ~ N번 후보에서 가장 높은 득표수 후보를 계속 뽑아야 하므로 가장 작은/큰 값이 가장 앞단에 위치하고, 시간 복잡도가 O(logN)으로 짧은 자료구조가 필요했기 때문이다. 

- 이때 최대 힙을 구현해야하므로 득표수는 마이너스 값으로 진행한다 (가장 작은 마이너스 값이 가장 큰 양수값이므로)

- 다른 후보에서 뺏은 득표수를 1번 후보 득표수에 계속 더하고, 1번 후보의 득표수가 다른 어떤 후보 보다 더 클 때 멈추면 된다

- 마지막으로 득표수를 뺏는 반복을 몇 번 했는지 세서 프린트 하면 끝

풀이 로직

- 1번 후보는 계속 써야하므로 first 변수에 저장하고, votes에는 나머지 후보들의 마이너스 득표 수를 추가한다

- votes를 heap으로 진행할 것이므로 heapify도 해준다

- while문을 돌면서 votes에서 heappop을 해서 후보 중 가장 큰 득표수를 가져온다

- 만약 first의 값이 더 크다면 first 값이 최대이므로 반복문을 break하고

- 아니라면 해당 후보의 득표수를 줄이고(vote_num + 1 (vote_num이 음수이기 때문), 1번 후보의 득표수를 늘린다 (first -= 1)

정답 풀이

import heapq

n = int(input())

first = -1 * int(input())
votes = []
for i in range(1, n):
    votes.append([-1 * int(input()), i])

heapq.heapify(votes)

count = 0
while votes:
    vote_num, number = heapq.heappop(votes)
    
    if vote_num > first: # 1번 득표수가 제일 클 때 
        break
        
    heapq.heappush(votes, [vote_num + 1, number])
    first -= 1
    count += 1
    
print(count)

- 문제 : https://www.acmicpc.net/problem/14247

문제 이해 

- n개의 나무를 n일에 걸쳐서 하나씩 자른다 

- i번째 나무를 한번 자르면 다음날에 grow_term[i]만큼 자란다

- 위의 방법대로 나무를 n일 동안 잘랐을 때 나무 길이의 최대값을 구한다

풀이 팁

- 하나의 나무를 나눠서 자르는 것보다 한 번에 나무 전체를 다 자르는 것이 효율적이다. (어차피 나무들이 1일마다 grow_term[i]만큼씩 자라기 때문)

- 따라서 자를 나무 순서를 정한 뒤 그 순서대로 자르면 자른 나무 길이의 합이 최대가 된다. 

- 나무 순서 정하는 방법은 성장세가 낮은 나무, 즉 grow_term[i]의 값이 작은 값부터 베면 된다. 

풀이 로직 

- 나무 순서와 grow_term 간에 관계가 있으므로 result 배열에 리스트로 [나무 초기 길이, grow_term 값]을 넣고

- grow_term을 기준으로 result를 오름차순 정렬한다. 

- 0일부터 n - 1일까지 반복문을 돌면서 i일에 해당하는 나무의 길이(초기값(result[i][0]) + 며칠(i) * 증가값(result[i][1])를 answer에 누적한다.

- 정답 풀이 

n = int(input())
first = list(map(int, input().split()))
grow_term = list(map(int, input().split()))

result = []
for i in range(len(first)):
    result.append([first[i], grow_term[i]])
    
result.sort(key = lambda x : x[1])
    
answer = 0    
for i in range(len(result)):
    answer += i * result[i][1] + result[i][0]
    
print(answer)