티스토리 뷰
Greedy 기출문제 - 모험가 길드, 곱하기 혹은 더하기, 뒤집기(BOJ 1439), 만들 수 없는 금액, 볼링공 고르기(SW마에스트로 기출), 무지의 먹방 라이브(프로그래머스-카카오 기출)
우징어🦑 2022. 4. 24. 17:15그리디 기출문제 풀이
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 파이썬 (나동빈 저자)
'알고리즘, 코딩테스트' 카테고리의 다른 글
BOJ 백준 코드플러스 알고리즘 기초 - 다이나믹 프로그래밍1 (0) | 2021.02.15 |
---|---|
BOJ 백준 수학 문제(나머지,최대공약수,최소공배수,소수) | 코드플러스 알고리즘 기초1/2 - 수학 (0) | 2021.02.08 |
- Total
- Today
- Yesterday
- partyrock사용볍
- SpacewBetween
- 티스토리챌린지
- 정적 웹사이트 배포
- AWSBedrock
- vscode easycode
- BOJ
- React native 작동 원리
- aws생성형ai
- partyrock
- 파이썬
- S3배포
- 정적 웹페이지 배포
- awsgenai
- easycode chatGPT
- partyrock생성
- genaiapp
- PYTHON
- 코딩테스트
- 오블완
- S3 403 forbidden
- 알고리즘
- partyrock무료
- easycode
- 술자리병돌리기게임
- partyrock앱
- 병돌리기구현
- ChatGPT
- 생성형AI
- 백준
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |