티스토리 뷰

그리디 기출문제 풀이

1. 모험가 길드

사람들의 공포도 리스트를 오름차순으로 정렬 후, 공포도가 작은 사람부터 그룹을 형성해서 그룹이 최대 개수가 되도록 풀었다.

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

answer = 0
idx = 0  # 현재 사람의 인덱스
while True:
    num = x[idx]  # 현재 사람의 공포도
    answer += 1
    if idx + num >= n:  # 현재 사람의 공포도만큼 수 추가
        break  # 만약 n을 넘어가면 break
    else:  # 현재 사람의 공포도만큼 인원 수를 추가했을 때 n을 넘지 않는다면 
        idx += num  # idx 조정하여 다음 사람 따지도록

print(answer)

 

 

2. 곱하기 혹은 더하기

S = input()
result = 0
value = int(S[0])

for i in range(1, len(S)):
    value = max(value + int(S[i]), value * int(S[i]))  # 더한 것과 곱한 것 중 큰 값
print(value)

 

3. 뒤집기 (BOJ 1439)

백준에도 올라와있는 문제다. https://www.acmicpc.net/problem/1439

풀이시간이 20분이라고 돼있는데 40분 걸려 풀었다.. 풀고보니 이렇게까지 걸릴 문제는 아닌 듯한데..ㅎㅎ

근데 내 접근법이랑 답지랑 상당히 달랐다. 

처음엔 되게 고민하다가 예제들을 살펴보면서 규칙을 발견했다.

 

맨 앞과 맨 뒤를 동시에 없애가면서 마지막에 동일한 숫자들만 남을 때까지 없앴을 때, 그때까지의 횟수가 답이었다.

맨 앞과 맨 뒤가 같을 때는 위에 말처럼 동시에 없애고, 

맨 앞과 맨 뒤가 다를 때는 둘 중 하나만 없앤다. 이 없애는 과정을 수행한 수를 답으로 내주었다. 

이를 편하게 구현하기 위해 일단 연속되는 숫자들을 하나로 만들어주었다. 

이렇게 말로만 하면 이해하기 어려우니까 예제로 보자.

아래 그림에서 화살표 개수가 답이라고 생각하면 편할 것 같다.

 

0001100 = 010 -> 1 :: 답 1

010에서 맨 앞 0과 맨 뒤 0이 같으므로 둘을 없애준다. 

그러면 1만 남으므로 답은 1

 

11111 = 1 :: 답 0

하나일 경우에는 0으로 예외처리 해주었다.

 

00000001 = 01 -> 1 :: 답 1

01에서 맨 앞 0과 맨 뒤 1이 다르므로 둘 중 하나를 없애준다.

나는 앞을 잘라주었다. 

그러면 1 하나만 남으므로 답은 1

 

11001100110011000001 = 101010101 -> 0101010 -> 10101 -> 010 -> 1 :: 답 4

101010101에서 맨 앞과 맨 뒤가 같으므로 0101010 

이 과정을 반복하면 하나의 숫자 1만 남을 때까지 총 4번의 수행이 있다. 

 

11101101 = 10101 -> 010 -> 1 :: 답 2

마찬가지로 10101은 맨 앞과 맨 뒤가 같으므로 010 으로 처리되고,

이후에는 1이 되어 답은 2이다.

 

 

# BOJ 1439
S = input()
newS = S[0]
for s in range(1, len(S)):
    if newS[-1] == S[s]:
        continue
    else:
        newS += S[s]

j = len(newS)-1
count = 0
while True:
    if len(newS) == 1:
        break
    else:
        if newS[0] == newS[j]:  # 처음과 끝이 똑같다면
            newS = newS[1:-1]  # 처음과 끝 자르기
            count += 1
            j -= 2
        elif newS[0] != newS[j]:  # 처음과 끝이 다르다면
            newS = newS[1:]  # 맨 앞만 자르기 newS[0:-1]도 무방
            count += 1
            j -= 1
print(count)

 

4. 만들 수 없는 금액

정렬을 이용한 그리디 문제로, 15분 정도 나름 꽤 고민을 하다가 풀었다. 30분 제한시간 문제인데 25분 걸려 풀었다.

나는 주어진 금액 number가 만들 수 있는 금액인지 따질 때, coins 중 큰 금액부터 빼는 것으로 풀었다.

n = int(input())
coins = list(map(int, input().split()))
coins.sort(reverse=True)

answer = 1
while True:
    number = answer
    if number < coins[n-1]:  # 동전 중 가장 작은 금액보다 작을 경우
        break # while문 나가서 answer 출력
    for i in range(n):
        if number == 0:  # number == 0 이라면 딱 떨어진 것이므로 만들 수 있는 금액
            break
        if number < coins[i]:  # 현재 코인이 number보다 크면
            continue  # 다음 coin으로 넘어감
        else:
            number -= coins[i]  # 큰 수부터 하나씩 뺌
        
        if number != 0 and i == n-1:  # 0이 안됐는데 coin 끝까지 다 왔으면
            print(answer)  #  그러면 answer 출력하고 종료
            exit(0)
    answer += 1

print(answer)

그런데 내가 푼 방법은 2중 반복문으로 시간 복잡도에 걸릴 가능성이 있다. 사실 매우 큰 듯 하다

이 문제에서는 N <= 1000 이라는 조건이 걸리긴 했지만 N이 좀더 커지면 아마 시간제한에 걸릴 것이다.

 

 

그래서 책에 나와있는 답안을 보았다.

너무 간단해서 놀랐다... 허허

문제 해결 아이디어를 잘 잡으면 훨씬 간단한 코딩이 가능하다.

 

아이디어 및 풀이법

작은 금액부터 확인하면서 target 금액을 만들 수 있다면 증가시키는 방식을 이용했다.

 

현재 상태를 1부터 target-1 까지 만들 수 있는 상태로 본다. 이때 매번 target인 금액도 만들 수 있는지 체크한다.

즉 target = n이라면  n-1 까지의 금액은 모두 만들 수 있다는 것을 의미한다.

 

예를 들어,

현재 주어진 동전들이 [1,2,3] 이라고 하자. 그러면 1~6원 까지 만들 수 있다.

그 다음 확인해야 할 target = 7이다.

이때 다음 추가된 코인으로 5원이 추가되었을 때와 12원이 추가되었을 때를 비교해보자

 

(1) [1, 2, 3, 5]

이미 1~6원을 만들 수 있으므로 새로 추가한 5원 동전으로는

1 + 5 = 6

2 + 5 = 7

3 + 5 = 8

4 + 5 = 9

5 + 5 = 10

6 + 5 = 11

까지 만들 수 있다. 그러므로 target에 새 동전 5원이 더해져서 target + 5 =12 가 된다.

이는 11원까지 만들 수 있고, 다음 확인해야 할 금액이 12원이라는 의미이다. 

여기서 더 추가할 동전이 없으므로 만들 수 없는 최소 금액은 12 가 된다.

 

그러면 12원이 추가된 다음 상황을 보자.

(2) [1, 2, 3, 12]

마찬가지로 이미 1~6원을 만들 수 있으므로 새로 추가한 12원 동전으로는

1 + 12 = 13

2 + 12 = 14

3 + 12 = 15

4 + 12 = 16

5 + 12 = 17

6 + 12 = 18

까지 만들 수 있다. 그런데 이때는 7~12원이 빈다.

이는 target 보다 새로 추가한 동전의 금액이 크기 때문이다.

이 경우는 target = 7에서 다음으로 업데이트될 수 없기 때문에 만들 수 없는 최소 금액이 7이 된다. 

 

이렇게 새로운 동전이 추가되었을 때 이전 target + 새 동전의 금액 을 하면서 target을 올려 나가면 되고,

target 보다 새 동전의 단위가 큰 경우 현재 target 이 만들 수 없는 금액이 된다.

 

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

target = 1
for x in coins:
    # 만들 수 없는 금액을 찾으면 반복 종료
    if target < x:
        break
    target += x

print(target)

 

 

5. 볼링공 고르기 (SW 마에스트로 19년도)

(1) combinations을 사용한 풀이

from itertools import combinations

n, m = map(int, input().split())
balls = list(map(int, input().split()))
combis = list(combinations(balls, 2))

answer = len(combis)
for combi in combis:
    if combi[0] == combi[1]:
        answer -= 1

print(answer)

 

 

(2) combinations을 사용하지 않은 풀이

# combinations 없이 풀기
n, m = map(int, input().split())
balls = list(map(int, input().split()))

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

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

 

6. 무지의 먹방 라이브 (카카오 신입공채 19년도)

https://programmers.co.kr/learn/courses/30/lessons/42891?language=python3에도 실린 문제이다.

k로 반복문 돌면서 하기에는 효율성 테스트에서 무조건 걸린다. 2*10^13 이기 때문에..

그러므로 반복문이 아닌 그리디로 풀어야 하는데..  물론 그리디 챕터 안에 있긴 하지만

아이디어가 잘 생각이 안나 답을 참고해서 풀었다. 아직 공부가 많이 필요하다..!

import heapq

def solution(food_times, k):
    if sum(food_times) <= k:  # 모든 음식 먹을 시간보다 k가 크면
        return -1  # 먹을 음식이 없으므로 -1 반환

    q = []  # 시간이 적은 음식부터 빼야 하므로 우선순위 큐 이용(최소힙)
    for i in range(len(food_times)):
        heapq.heappush(q, (food_times[i], i + 1))  # (음식 시간, 음식 번호)
    
    n = len(food_times)
    previous = 0  # 이전에 제거한 음식의 food_time

    while q:
        # 먹는데 걸리는 시간 = (남은 양) * (남은 음식 개수)
        eat_time = (q[0][0] - previous) * n

        #시간이 남을 경우 현재 음식 빼기
        if k >= eat_time:
            k -= eat_time
            previous = heapq.heappop(q)[0]
            n -= 1
        
        # 시간이 부족할 경우 남은 음식 중 먹을 음식 색출
        else:
            q.sort(key=lambda x: x[1])
            return q[k % n][1]



print(solution([8, 6, 4], 15))
print(solution([3, 1, 2], 5))

 

 

 

 

문제 출처 : 이것이 취업을 위한 코딩테스트다 with 파이썬 (나동빈 저자)