1. 모험가 길드
문제 설명
모험가에게는 '공포도'가 존재하고 공포도가 X인 모험가는 반드시 X명 이상의 모험가 그룹에 참여헤야 모험을 떠날 수 있다.
N명의 모험가에 대한 정보가 주어졌을 때, 최대 그룹 수를 구하라.
(1 <= N <= 100,000, 1초)
문제 풀이
최대 그룹 수를 구해야 하므로 최소 공포도 순으로 정렬을 한 후
공포도가 작은 사람끼리 그룹을 최대한 많이 구성해야 한다.
따라서 현재 그룹 수 >= 해당 모험가의 공포도가 되면 그룹을 구성하도록 했다.
2 3 1 2 2 => 1 2 2 2 3 (정렬)
1 2 2 2 3
count = 1
power = 1
그룹 생성! (count 초기화)
1 2 2 2 3
count = 1
power = 2
1 2 2 2 3
count = 2
power = 2
그룹 생성! (count 초기화)
1 2 2 2 3
count = 1
power = 2
1 2 2 2 3
count = 2
power = 3
따라서 그룹 수는 2개이다. ( 1 / 2 2 )
정답
n = int(input())
array = list(map(int, input().split()))
array.sort() # 오름차 정렬
answer = 0 # 정답
count = 0 # 현재 그룹 수
for power in array:
count += 1
# 현재 그룹 수 >= 현재 모험가의 공포도이면 종료
if power <= count:
answer += 1
count = 0
print(answer)
2. 곱하기 혹은 더하기
문제 설명
각 자리가 0 ~ 9까지의 숫자로만 이루어진 문자열 S에 대해
왼쪽부터 오른쪽까지 모든 숫자 사이에 'x' 혹은 '+' 연산자를 넣어
구할 수 있는 가장 큰 수를 구하는 프로그램을 작성하라.
이때 모든 연산은 일반적인 방식과 달리 왼쪽부터 순차적으로 이루어진다.
(1 <= S의 길이 <= 20, 결과는 20억 이하의 정수이다., 1초)
문제 풀이
사칙 연산이 아닌 왼쪽부터 순차적으로 적용되는 연산이므로
연산 대상이 0 이거나 1인 경우에는 곱하기를 사용하는 것보다
더하기를 사용하는 것이 더 큰 값을 얻을 수 있다.
정답
s = str(input())
answer = int(s[0]) # 첫번째 원소 대입
# 두번째 원소부터 마지막까지 반복
for i in s[1:]:
# 연산의 대상이 0이거나 1이면 + 연산
if i == '0' or i == '1' or answer == 0 or answer == 1:
answer += int(i)
# 0, 1이 아니면 x 연산
else:
answer *= int(i)
print(answer)3. 문자열 뒤집기
문제 설명
0과 1로만 이루어진 문자열 S가 있다.
연속된 하나 이상의 숫자를 뒤집는 행동으로 모든 숫자를 전부 같게 만들고 싶다.
이때 모든 숫자를 같게 만드는 최소 행동 횟수를 구하라.
( 1 <= S <= 1,000,000, 2초)
문제 풀이
0을 1로 뒤집는 것이 유리한지 1을 0으로 뒤집는 것이 유리한지 파악해야 한다.
즉, 0을 1로 뒤집을 것인지 1을 0으로 뒤집을 것인가를 결정해야 한다.
0에서 1로 바뀌는 순간을 횟수와 1에서 0으로 바뀌는 순간의 횟수를 구한 후
더 적은 경우의 수가 최소 행동 횟수라는 것을 알 수 있다.
정답
s = str(input())
zero_to_one = 0 # 0에서 1로
one_to_zero = 0 # 1에서 0으로
first = s[0] # 초기 값 설정
for second in s[1:]:
# 앞 뒤가 다른 경우
if first != second:
# 0으로 바뀐 경우
if second == '0':
one_to_zero += 1
# 1로 바뀐 경우
else:
zero_to_one += 1
# 다음 비교를 위해서 first를 second로
first = second
# 두 행동 횟수 중 더 작은 값을 출력
print(min(zero_to_one, one_to_zero))4. 만들 수 없는 금액
문제 설명
N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하라.
(1 <= N <= 1,000, 1 <= 화폐 단위 <= 1,000,000, 1초)
ex) N = 5이고 coins = [1, 2, 1, 3, 9]일 때
최솟값은 8이다.
문제 풀이
첫번째 접근 방법
1부터 화폐로 만들 수 있는 최대 양의 정수까지 전체 탐색을 하려고 했으나
1,000 x 1,000,000로 1초의 시간을 훨씬 뛰어넘게 된다. (1초에 2000만번)
두번째 접근 방법
1 2 1 3 9
1 = 1
2 = 2
3 = 3
4 = 3 + 1
5 = 3 + 2
6 = 3 + 2 + 1
7 = 3 + 2 + 1 + 1
8 = 8원 이하의 동전들로 만들 수 없는 금액 → 8
위의 로직을 만들기 위해서 조합을 사용할까 생각했지만
n이 1,000이고 1부터 n까지의 조합을 모두 생각해야 하므로
1000C1 + 1000C2 + ... + 1000C1000으로 시간 초과가 발생할 것 같다.
세번째 접근 방법
1 1 2 3 9 (오름차 정렬)
1원 추가 → 가능 금액 : 1
이전 가능 금액 : 1 → 1원 추가 → 현재 가능 금액 : 1(1), 2(1+1)
이전 가능 금액 : 1 2 → 2원 추가 → 현재 가능 금액 : (2), 3(2+1), 4(2+1+1)
이전 가능 금액 : 1 2 3 4 → 3원 추가 →
이전 현재 가능 금액 : 3(3), 4(3+1), 5(3+2), 6(3+2+1), 7(3+2+1+1)
이전 가능 금액 : 1 2 3 4 5 6 7 → 9원 추가 →
현재 가능 금액 : 9(9), 10(9+1), ... , 16(9+3+2+1+1)
즉, 7까지 만들 수 있었고 9원을 추가하기 전까지의 동전들로 구성이 가능했고
여기에 9원을 추가하게 되면 9에 이전 값들을 더하면서 만들 수 있는 금액이 결정되므로 8을 만들 수 없게 되는 것이다.
즉, 마지막 만들 수 있는 금액인 cost에 1을 더한 값보다 큰 값이 추가되면
cost + 1부터 추가된 코인 값 - 1까지는 만들 수 없는 금액이 되는 것이다.
따라서 cost + 1이 만들 수 없는 최소 금액이 되는 것이다.
이 경우 선형적으로 돌아가기 때문에 시간복잡도도 충분하다.
정답
n = int(input())
coins = list(map(int,input().split()))
coins.sort() # 오름차 정렬
target = 0 # 이전 가능 금액 중 최고 금액
# 모든 코인에 대하여
for coin in coins:
# 이전 가능 금액보다 현재 코인이 크면 종료 -> 만들 수 없음
if coin > target:
break
else:
target += coin
# 이전 가능 금액 중 최고 금액에 1을 더한 값 = 만들 수 없는 최소 금액
print(target + 1)5. 볼링공 고르기
문제 설명
A,B 두 사람이 볼링을 치고 있다.
두 사람은 서로 무게가 다른 볼링공을 고르려고 한다.
총 N개의 볼링공이 존재하며 공의 번호는 1번부터 순서대로 부여된다.
공의 무게는 1부터 M까지의 자연수 형태로 존재한다.
이때 두 사람이 볼링공을 고를 수 있는 번호의 조합 수를 구하라.
(1 <= N <= 1,000, 1 <= M <= 10 , 1 <= 각 볼링공의 무게 <= M, 1초)
문제 풀이
N의 개수가 1000이고 2개를 선택하는 경우이므로 1000C2라고 생각할 수 있다.
이 때 1000C2는 1000 x 999 / 2 = 499,950으로 1초 안에 작동하므로
조합을 통해 모든 경우를 구한 후 두 수가 같은 경우를 제외하는 방법으로
문제를 해결하였다.
정답
from itertools import combinations
n, m = map(int, input().split())
weight = list(map(int, input().split()))
# 볼링공의 번호에 대한 리스트
s = ''
for i in range(n):
s += str(i)
# 모든 볼링공 번호에 대해서 2개를 선택하는 모든 조합의 수
all_case = list(combinations(s, 2))
exception = 0 # 제외되는 경우의 수
# 모든 조합의 수에 대해서
for case in all_case:
a = int(case[0]) # A의 볼링공 번호
b = int(case[1]) # B의 볼링공 번호
# A의 볼링공 무게와 B의 볼링공 무게가 같은 경우 예외 처리
if weight[a] == weight[b]:
exception += 1
# 전체 조합의 수에서 예외 경우의 수 빼기
print(len(all_case) - exception)6. 무지의 먹방 라이브
문제 설명
위의 문제는 기본 코드가 제공되므로 해당 링크를 통해서 문제를 풀어야 합니다.
정답
# 무지의 먹방 라이브
import heapq
def solution(food_times, k):
answer = -1
h = []
for i in range(len(food_times)):
heapq.heappush(h, (food_times[i], i + 1))
food_num = len(food_times) # 남은 음식 개수
previous = 0 # 이전에 제거한 음식의 food_time
while h:
# 먹는데 걸리는 시간: (남은 양) * (남은 음식 개수)
t = (h[0][0] - previous) * food_num
# 시간이 남을 경우 현재 음식 빼기
if k >= t:
k -= t
previous, _ = heapq.heappop(h)
food_num -= 1
# 시간이 부족할 경우(음식을 다 못먹을 경우) 남은 음식 중에 먹어야 할 음식 찾기
else:
idx = k % food_num
h.sort(key=lambda x: x[1])
answer = h[idx][1]
break
return answer문제 풀이
(food_time, 음식 번호)를 heap에 넣고 food_time이 짧은 음식부터 삭제하자!
- 모든 음식에 대해 (food_time, 음식 번호)를 heap에 삽입한다.
- food_time이 짧은 음식부터 음식을 먹는데 걸리는 시간을 계산한다.
- 음식을 먹는데 걸리는 시간: (남은 음식 양) * (남은 음식 개수)
- 남은 음식 양: 현재 food_time - 이전에 제거한 food_time
- 현재 음식을 다 먹을 수 있는 경우 음식을 제거한다.
- 남은 시간(k)에서 현재 음식을 먹는 시간을 뺀다.
- 이전에 제거한 food_time과 남은 음식 개수를 갱신한다.
- 현재 음식을 다 먹을 수 없는 경우 다음 먹을 음식 번호를 구한다.
- heap에 남아있는 음식 번호 중에 (k + 1)번째 번호를 찾는다.
- k는 (k % 남은 음식 개수)로 번호를 찾는다.
나의 풀이(오답)
def solution(food_times, k):
answer = 0
num = 0
i = 0
n = len(food_times)
# 모든 식사 시간의 합이 k보다 작으면 -1 반환
if sum(food_times) < k:
answer = -1
return answer
while i < k:
# 리스트를 넘어가지 않도록
num %= n
# 식사 시간이 0인 경우
if food_times[num] == 0:
# 다음 음식으로 넘어간다.
num += 1
continue
# 식사를 한 후 1을 빼준다.
food_times[num] -= 1
# 다음 음식으로
num += 1
num %= n
i += 1
# 인덱스로 계산했으므로 1을 더해준다.
answer = num + 1
return answer참고 자료
이것이 코딩 테스트다 교재 CHAP 11 그리디 문제
