[ 이것이 코딩테스트다 with 파이썬 ] Greedy 기출문제

1. 모험가 길드 

• 문제

한 마을에 모험가가 N명 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어집니다.

모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다. 동빈이는 회대 몇 개의 모험가 그룹을 만들 수 있는지 궁금합니다.

 

** 모든 모험가를 특정한 그룹에 넣을 필요는 없습니다. ** 

 

• 입력조건 

- 첫째 줄에 모험가의 수 N이 주어진다. ( 1 ≤ N ≤ 100,000 )

- 둘째 줄에는 각 모험가의 공포도 값을 N 이하의 자연수로 주어지며, 각 자연수는 공백으로 구분합니다.

 

• 출력조건 

- 여행을 떠날 수 있는 그룹 수의 최댓값을 출력합니다.

# 모험가 길드
n = int(input())  # 모험가의 수
arr = list(map(int, input().split()))  # 모험가 길드의 공포도
arr.sort()
count= 0  # 현재 그룹에 포함된 모험가 수
result = 0 # 그룹 수

for i in arr:
    count += 1
    if count >= i:
        result += 1
        count = 0

print(result) # 총 그룹 수 출력

2. 곱하기 혹은 더하기

• 문제

각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요.

단, + 보다 x를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다.

예를 들어 02984라는 문자열이 주어지면, 만들어질 수 있는 가장 큰 수는 ( ( ( ( 0 + 2 ) x 9 ) x 8 ) x 4 ) = 576 입니다.

또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어집니다.

 

• 입력조건

- 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어집니다.

 

• 출력조건

- 첫째 줄에 만들어질 수 있는 가장 큰 수를 출력합니다.

# 곱하기 혹은 더하기
s = input()
arr = []

for i in s:
    arr.append(int(i))

arr.sort()
result = arr[0]

for i in range(1, len(arr)):
    if arr[i] <= 1 or result <= 1:
        result += arr[i]
    else:
        result *= arr[i]

print(result)

3. 문자열 뒤집기

• 문제

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있습니다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 합니다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것입니다.

뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미합니다.

 

예를 들어 S = 0001100 일 때 

1) 전체를 뒤집으면 1110011

2) 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 두 번만에 모두 같은 숫자로 만들 수 있습니다.

 

문자열 S가 주어졌을 대, 다솜이가 해야 하는 행동의 최소횟수를 출력하세요.

 

• 입력조건

- 첫째 줄에 0과 1로만 이루어진 문자열 S가 주어집니다. S의 길이는 100만보다 작습니다.

 

• 출력조건

- 첫째 줄에 다솜이가 해야하는 행동의 최소횟수를 출력합니다.

# 문자열 뒤집기
# 경우의 수를 생각해서 가정해보기

data = input()
count0 = 0 # 전부 0으로 바꾸는 경우
count1 = 0 # 전부 1로 바꾸는 경우

if data[0] == '1': # 1이면 0으로 바꿔야하기 때문에
    count0 += 1
else:
    count1 += 1

for i in range(len(data)-1):
    if data[i] != data[i+1]:
        if data[i+1] == '1':
            count0 += 1
        else:
            count1 += 1

print(min(count0, count1))

4. 만들  수 없는 금액

• 문제

동네 편의점 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이 때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.

 

예를 들어, N = 5이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리 (화폐단위) 동전이라고 가정합시다. 이 때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다.

 

또 다른 예시로, N = 3이고, 각 동전이 각각 3원, 5원, 7원짜리 (화폐단위) 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 1원입니다.

 

• 입력조건

- 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어집니다. 

- 둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분합니다. 

 

• 출력조건

- 첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력합니다.

n = int(input())
data = list(map(int, input().split()))
data.sort()

target = 1
for x in data:
    if target < x:
        break
    target += x

print(target)

5. 볼링공 고르기

• 문제

A, B 두 사람이 볼링을 치고 있습니다. 두 사람은 서로 무게가 다른 볼링공을 고르려고 합니다. 볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀있고, 공의 번호는 1번부터 순서대로 부여됩니다.

또한 같은 무게의 공이 여러 개 있을 수 있지만, 서로 다른 공으로 간주합니다. 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재합니다.

예를 들어 N이 5이고 M이 3이며 각각의 무게가 차례대로 1, 3, 2, 3, 2일 때 각 공의 번호가 차례대로 1부터 5번까지 부여됩니다. 이 때 두사람이 고를 수 있는 볼링공의 번호 조합을 구하면 다음과 같습니다.

 

결과적으로 두 사람이 공을 고르는 경우의 수는 8가지 입니다. N개의 공의 무게가 각각 주어질 때, 두 사람이 볼링공을 고르는 경우의 수를 구하는 프로그램을 작성하세요.

 

• 입력조건

- 첫째 줄에 볼링공의 개수 N, 공의 최대 무게 M이 공백으로 구분되어 각각 자연수 형태로 주어집니다.

- 둘째 줄에 각 볼링공의 무게 K가 공백으로 구분되어 순서대로 자연수 형태로 주어집니다.

 

• 출력조건

- 첫째 줄에 두 사람이 볼링공을 고르는 경우의 수를 출력합니다.

import itertools

n, m = map(int, input().split())

arr = list(map(int, input().split()))
a = 0
b = 0

for i in itertools.combinations(arr, 2):
    if list(i)[0] == list(i)[1]:
        b += 1
    a += 1

print(a-b)

실제 코테에서 조합 라이브러리를 쓸 수 있는지 모르기에  예시 답안도 추가했다. 

# 볼링공 고르기 답안
n, m = map(int, input().split())
data = list(map(int, input().split()))

# 1부터 10까지 무게를 담을 수 있는 리스트
array = [0] * 11

for x in data:
    # 각 무게에 해당하는 볼링공의 개수 카운트
    array[x] += 1

result = 0
# 1부터 m까지의 각 무게에 대하여 처리
for i in range(1, m+1):
    n -= array[i] # 무게가 i인 볼링공의 개수 (A가 선택할 수 있는 개수) 제외
    result += array[i] * n # B가 선택하는 경우의 수와 곱하기

print(result)

6. 무지의 먹방 라이브

• 문제

평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다.

그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다.

무지는 다음과 같은 방법으로 음식을 섭취한다.

 

• 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.
• 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.
• 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다.
• 다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다.
• 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다고 가정한다.

무지가 먹방을 시작한 지 K 초 후에 네트워크 장애로 인해 방송이 잠시 중단되었다.

무지는 네트워크 정상화 후 다시 방송을 이어갈 때, 몇 번 음식부터 섭취해야 하는지를 알고자 한다.

각 음식을 모두 먹는데 필요한 시간이 담겨있는 배열 food_times, 네트워크 장애가 발생한 시간 K 초가 매개변수로 주어질 때 몇 번 음식부터 다시 섭취하면 되는지 return 하도록 solution 함수를 완성하라.

 

제한사항

 

• food_times 는 각 음식을 모두 먹는데 필요한 시간이 음식의 번호 순서대로 들어있는 배열이다.
• k 는 방송이 중단된 시간을 나타낸다.
• 만약 더 섭취해야 할 음식이 없다면 -1을 반환하면 된다.

정확성 테스트 제한 사항

 

• food_times 의 길이는 1 이상 2,000 이하이다.
• food_times 의 원소는 1 이상 1,000 이하의 자연수이다.
• k는 1 이상 2,000,000 이하의 자연수이다.

효율성 테스트 제한 사항

 

• food_times 의 길이는 1 이상 200,000 이하이다.
• food_times 의 원소는 1 이상 100,000,000 이하의 자연수이다.
• k는 1 이상 2 x 10^13 이하의 자연수이다.

입출력 예

food_times [ 3, 1, 2 ]

k 5

result 1

 

• 0~1초 동안에 1번 음식을 섭취한다. 남은 시간은 [2,1,2] 이다.
• 1~2초 동안 2번 음식을 섭취한다. 남은 시간은 [2,0,2] 이다.
• 2~3초 동안 3번 음식을 섭취한다. 남은 시간은 [2,0,1] 이다.
• 3~4초 동안 1번 음식을 섭취한다. 남은 시간은 [1,0,1] 이다.
• 4~5초 동안 (2번 음식은 다 먹었으므로) 3번 음식을 섭취한다. 남은 시간은 [1,0,0] 이다.
• 5초에서 네트워크 장애가 발생했다. 1번 음식을 섭취해야 할 때 중단되었으므로, 장애 복구 후에 1번 음식부터 다시 먹기 시작하면 된다.

import heapq

def solution(food_times, k):
    # 음식을 다 먹은 경우 더 먹을 것이 없을 때
    if sum(food_times) <= k:
        return -1
    
    q = []
    for i in range(len(food_times)):
        # (음식시간, 음식 번호) 형태로 우선순위 큐에 삽입
        heapq.heappush(q, (food_times[i], i+1))
    sum_value = 0 # 먹기 위해 사용한 시간 
    previous = 0 # 직전에 다 먹은 음식 시간
    length = len(food_times) # 남은 음식 개수
    
    while sum_value + ((q[0][0] - previous)*length) <= k:
        now = heapq.heappop(q)[0]
        sum_value += (now-previous) * length 
        length -= 1
        previous = now # 이전 음식 시간 재설정 
    
    result = sorted(q, key = lambda x : x[1]) # 음식 번호 기준으로 정렬 
        
    return result[(k-sum_value)%length][1]