100년 뒤 개발자 한승규입니다.

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

당연히 heap을 사용해야 한다는 것은 알고 있었지만, 어떻게 사용할 지에 대해서 고민을 많이 했었다.

보석과 가방을 같은 heap에 넣는다는 생각을 하는 게 좀 힘들었던 것 같다.

무게를 기준으로 최소 heap에 보석과 가방을 넣어준다.

가방 같은 경우는 같은 무게에서 가장 뒤로 갈 수 있도록 가치에는 무한을 넣어준다.

하나씩 꺼낼 때 쓸 heap도 만들어준다.

보석과 가방을 넣은 heap에서 하나씩 꺼내어서 반복문을 실행해준다.

만약 꺼낸 것이 보석이라면 최대 heap에 가치를 넣어준다.

만약 꺼낸 것이 가방이라면 최대 heap에서 하나의 보석을 넣을 수 있는 것이므로 가장 큰 값을 가져와 결과값에 더해준다.

그렇게해서 구한 결과값을 출력해주면 된다.

import sys
import heapq

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

jewelry = list()

for _ in range(N):
    heapq.heappush(jewelry, list(map(int, sys.stdin.readline().split())))

for _ in range(K):
    heapq.heappush(jewelry, [int(sys.stdin.readline().strip()), float('inf')])

result = 0
cur_jewelry = list()

while jewelry:

    weight, value = heapq.heappop(jewelry)

    if value == float('inf'):
        if cur_jewelry:
            result += heapq.heappop(cur_jewelry)
    else:
        heapq.heappush(cur_jewelry, value * -1)


print(result * -1)

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

당연히 회의실 문제랑 똑같은 줄 알고 heap으로만 바꿔서 풀었었다.

문제를 똑바로 읽지 않은 내 잘못이다..

이번 문제는 해당 강의를 모두 가능하도록 만들어야 한다.

그렇기에 끝나는 시간으로 정렬하는 것이 아닌, 시작하는 순서대로 해서 빨리빨리 받아서 끝내도록 해야한다.

나중에 퀵정렬을 사용하는 것이 아니라 heap을 사용하여 입력을 받았다.

강의실을 배정할 때도 가장 빨리 끝나는 시간 순으로 정렬을 해두고, 앞의 시간이랑 비교해서 만약 강의 진행이 불가능 하다면 새로운 강의실을 편성한다.

만약 가능하다면 해당 강의실의 끝나는 시간을 현재 강의가 끝나는 시간으로 변경한 후 다시 heap으로 넣어준다.

import sys
import heapq

heap = []

N = int(sys.stdin.readline().strip())

for i in range(N):
    S, T = map(int, sys.stdin.readline().split())

    heapq.heappush(heap, [S, T])

room = list()
heapq.heappush(room, heap[0][1])
heapq.heappop(heap)

while heap:
    heap_S, heap_T = heapq.heappop(heap)

    if room[0] <= heap_S:
        heapq.heappush(room, heap_T)
        heapq.heappop(room)
    else:
        heapq.heappush(room, heap_T)


print(len(room))

마지막에는 강의실의 개수를 출력하고 마무리 해준다.

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

일의 자리는 * 1
십의 자리는 * 10

백의 자리는 * 100

으로 배열에 각 알파벳 마다 수를 계산해서 가지고 있는다.

그리고 큰 순으로 정렬을 해서 9, 8, 7, .... 이렇게 곱하기 해준 후 더해주면 된다.

import sys

word = [0 for i in range(ord('Z') - ord('A') + 1)]

for i in range(int(sys.stdin.readline().strip())):

    input_word = str(sys.stdin.readline().strip())

    cur_index = 1

    while input_word:
        word[ord(input_word[-1]) - ord('A')] += cur_index
        cur_index *= 10
        input_word = input_word[:-1]

word.sort(reverse=True)

result = 0

for i in range(10):
    result += (word[i] * (9-i))

print(result)

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

그리디답게 생각하는 데 오래 걸리지 않는다.

해당 카드 뭉치들에서 가장 작은 거 2개를 뽑아오는 것이 가장 최적일 것이다.

그러면 가장 작은 뭉치를 어떻게 가져오느냐를 생각해야 하는 데, 당연히 정렬이 먼저 떠오를 것이다.

여기서 퀵 정렬을 사용하면 nlogn의 시간복잡도가 나올 것인데, 지속적으로 가장 작은 것을 가져오려면 우선순위 큐를 사용하는 것이 logn으로 시간복잡도가 더 낮을 것이다.

그렇기 때문에 우선순위 큐를 사용하도록 한다.

import sys
import heapq

heap = []

for _ in range(int(sys.stdin.readline().strip())):
    heapq.heappush(heap, int(sys.stdin.readline().strip()))

result = 0

while len(heap) > 1:
    A = heapq.heappop(heap)
    B = heapq.heappop(heap)

    result += (A + B)
    heapq.heappush(heap, A + B)

print(result)

heap이라는 우선순위큐를 만들고 그곳에다가 카드의 수를 입력 받는다.

그리고는 while 반복문으로 카드 뭉치가 하나 남을 때까지 카드들을 뭉쳐주고 그렇게 뭉친 카드 뭉치는 다시 우선순위큐로 넣을 수 있도록 한다.

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

문제를 이해하는 시간만 한시간 정도 걸렸던 것 같다.

당연히 점수인 줄 알았는 데, 너무 이해가 되지 않아 질문게시판 찾아보니까 순위라고 하더라....

무조건 한 명 이상은 뽑을 것이니 처음 result를 1로 해준다.

그러고는 그냥 단순히 앞 순위로 정렬해주고, 반복문으로 순위를 점점 올려가며 가능한 친구들만 받고 result를 +1해준다.

import sys

for i in range(int(sys.stdin.readline().strip())):
    candidate = sorted([list(map(int, sys.stdin.readline().split())) for _ in range(int(sys.stdin.readline().strip()))])
    top = 0
    result = 1

    for t in range(1, len(candidate)):
        if candidate[t][1] < candidate[top][1]:
            top = t
            result += 1

    print(result)

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

아무리 생각해도 이 문제는 그리디보다는 BFS에 가깝다고 생각을 한다.

중복이 있으면 반복이 오래걸리고 같은 계산을 반복하기에 set으로 만들어서 중복을 제거하도록 했다.

우선 첫 수를 집합에 넣는다.

그리고 반복문을 실행하는 데, 조건은 B가 집합에 없고 집합이 비어있지 않는다는 조건이다.

반복문이 실행할 때마다, 임시로 저장할 집합을 만들고 해당 집합에 전역 집합에 있는 수에 *2, *10 + 1 한 값을 다 넣어두고 해당 집합을 전역 집합으로 바꿔준다.그리고 반복문이 실행될 때마다 결과값을 +1 해준다.

출력에서는 B가 발견이 되어 집합에 수가 남아있다면 result를 출력하고, 아니라면 B를 찾지 못하기 때문에 -1을 출력해준다.

import sys

A, B = map(int, sys.stdin.readline().split())

greedy = set()
greedy.add(A)

result = 1

while B not in greedy and greedy:

    current_greedy = set()

    while greedy:
        element = greedy.pop()
        if element * 2 <= 10 ** 9:
            current_greedy.add(element * 2)
        if element * 10 + 1 <= 10 ** 9:
            current_greedy.add(element * 10 + 1)

    result += 1
    greedy = current_greedy


print(result if greedy else -1)

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

학교에서도 배웠던 문제이고, 그리디라는 것을 알고 푸니 어렵지 않았다.

어떻게 정렬할지만 최대한 생각을 해보았다.

당연히 끝나는 시간을 기준으로 빨리 끝나는 거 부터 쭉 줄 세우고 가능한 회의만 받도록 했다.

빨리 끝나기만 하면 얼마나 걸리든지, 다음 회의를 받을 수 있기 때문이다.

중간에 정렬할 때 생각 못한 부분들이 있어서 오래 걸리긴 했다.

import sys

meeting = sorted([list(map(int, sys.stdin.readline().split())) for i in range(int(sys.stdin.readline().strip()))],
                 key=lambda x: (x[1], x[0]))

time = 0
result = 0

while meeting:
    start_time, end_time = meeting.pop(0)
    if start_time >= time and end_time < 2 ** 31:
        time = end_time
        result += 1

print(result)

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

이번 문제는 카테고리가 그리디이긴 하지만, 딱히 그리디를 생각하지는 않았다.

그냥 단순히 정렬 후 같은 것들은 묶어주고, 만약 문자가 짝수개이면 하나의 문자도 혼자있으면 안되며 홀수인 경우에는 하나의 문자만 홀로 있어야 한다.

다른 거 수와 문자열의 길이만 비교해서 구현하면 쉬운 문제로 딱히 로직에 관련해서는 설명하지 않도록 하겠다.

import sys

input_str = sorted(list(sys.stdin.readline().strip()))

start = ""
mid = ""
end = ""

chance = 0 if len(input_str) % 2 == 0 else 1

cur_char = ""

for i in input_str:
    if cur_char == "":
        cur_char = i
    else:
        if cur_char == i:
            start = start + cur_char
            end = cur_char + end
            cur_char = ""
        else:
            chance -= 1
            mid = cur_char
            cur_char = i

if cur_char != "":
    mid = cur_char

if chance >= 0:
    print(start + mid + end)
else:
    print("I'm Sorry Hansoo")