안녕하세요. 모각코 6일차입니다.
오늘도 저번 주와 같이 그리디 알고리즘 문제를 풀었습니다. 난이도는 골드 문제로 풀었습니다.
골드 문제
골드 문제에서는 heapq를 쓰는 문제가 많았습니다.
sort를 계속 진행하면 시간초과가 나기 때문에 우선순위 큐를 사용하여 문제를 해결해야했습니다.
11000
https://www.acmicpc.net/problem/11000
11000번: 강의실 배정
첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)
www.acmicpc.net
강의실 배정의 경우 시작 시간을 기준으로 정렬한 뒤, 새로운 강의실을 배정해야하는지 배정하지 않아도 되는지를 종료 시간과 다음 시작 시간으로 비교하면 됩니다.
그렇게 되면 room에는 강의실을 배정하는 첫 번째 강의가 들어가게 됩니다.
import sys, heapq
n = int(sys.stdin.readline())
li = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
li.sort()
room = []
heapq.heappush(room, li[0][1])
for i in range(1, n):
if li[i][0] < room[0]:
heapq.heappush(room, li[i][1])
else:
heapq.heappop(room)
heapq.heappush(room, li[i][1])
print(len(room))
1715
https://www.acmicpc.net/problem/1715
1715번: 카드 정렬하기
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장
www.acmicpc.net
카드 정렬 문제의 경우 골드 문제치고는 비교적 쉬운 편이었습니다.
모든 카드의 수를 heapq에 넣어서 가장 작은 수 두 개를 꺼낸 뒤, 더한 값도 큐에 넣으면 됩니다.
import sys, heapq
n = int(sys.stdin.readline())
cardSum = []
for i in range(n):
heapq.heappush(cardSum, int(sys.stdin.readline()))
cardCnt = 0
for _ in range(n-1):
n1 = heapq.heappop(cardSum)
n2 = heapq.heappop(cardSum)
cardCnt += n1 + n2
heapq.heappush(cardSum, n1 + n2)
print(cardCnt)
1339
https://www.acmicpc.net/problem/1339
1339번: 단어 수학
첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대
www.acmicpc.net
단어 수학 문제는 각 알파벳의 자리수만큼 10 ^ n 제곱으로 만들어주면 됩니다.
import sys
n = int(sys.stdin.readline())
li = [sys.stdin.readline().rstrip() for i in range(n)]
d = {}
for word in li:
for w in range(len(word)):
if word[w] in d:
d[word[w]] += 10 ** (len(word)-1 - w)
else:
d[word[w]] = 10 ** (len(word)-1 - w)
result_d = sorted(d.items(), key=lambda x:x[1], reverse=True)
result = 0
value = 9
for k, v in result_d:
result += v * value
value -= 1
print(result)
1744
https://www.acmicpc.net/problem/1744
1744번: 수 묶기
길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에
www.acmicpc.net
수 묶기 문제는 좀 오래 걸렸는데요. 왜냐하면
-3 -2 0 1 3 5 6 7 이런 경우를 고려하지 않았었기 때문입니다.
따라서 음수와 양수를 나눠서 음수는 내림차순, 양수는 오름차순으로 처리해주었습니다.
import heapq
import sys
n = int(sys.stdin.readline())
li = [int(sys.stdin.readline()) for i in range(n)]
num = []
reverseNum = []
value = 0
reverseValue = 0
n_v = 0
r_v = 0
for i in range(n):
if li[i] > 0:
heapq.heappush(num, -li[i])
n_v += 1
else:
heapq.heappush(reverseNum, li[i])
r_v += 1
# 오름차순
for _ in range(n_v//2):
n1 = heapq.heappop(num)
n2 = heapq.heappop(num)
if n1 == -1 or n2 == -1:
value += -n1 + -n2
else:
value += n1 * n2
# 내림차순
for _ in range(r_v//2):
n1 = heapq.heappop(reverseNum)
n2 = heapq.heappop(reverseNum)
if n1 == 1 or n2 == 1:
reverseValue += n1 + n2
else:
reverseValue += n1 * n2
if len(num) == 1:
value += -num[0]
if len(reverseNum) == 1:
reverseValue += reverseNum[0]
print(max(sum(li), value + reverseValue))
'2024 겨울 모각코 - 내 장점은 algorithm' 카테고리의 다른 글
[모각코 / 240202] 알고리즘 문제 풀이 (백준 - 그리디 부수기) (1) | 2024.02.04 |
---|---|
[모각코 / 240126] 알고리즘 문제 풀이 (프로그래머스 - bfs) (1) | 2024.01.30 |
[모각코 / 240119] 알고리즘 문제 풀이 (프로그래머스 - 스택/큐) (1) | 2024.01.22 |
[모각코 / 240112] 알고리즘 문제 풀이 (코드트리 - 백트래킹) (0) | 2024.01.17 |
[모각코 / 240105] 알고리즘 문제 풀이 (코드트리 - 시뮬레이션) (1) | 2024.01.11 |