CH1. 그리디 문제
🗨 곱하기 혹은 더하기
각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요. 단 +보다 x를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다.
입력 조건
- 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어집니다.(1<=S의 길이<=20)
출력 조건
- 첫째 줄에 만들어질 수 있는 가장 큰 수를 출력합니다.
👆 처음에 풀 때, 숫자가 1인 경우에도 곱하기보다 더하기가 더 커진다는 사실을 고려하지 못하고 0만 고려함. 즉, 숫자가 0또는 1인 경우에는 더하기를 해 주고, 나머지는 곱하기를 하는 것이 가장 큰 수를 만드는 방법이다.
풀이 코드
data = input()
result = int(data[0])
for i in range(1,len(data)):
num = int(data[i])
if num<=1 or result<=1:
result+=num
else:
result*=num
print(result)
🗨 문자열 뒤집기
다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있습니다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 합니다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것입니다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미합니다.
예를 들어 S=0001100일 때는 다음과 같습니다.
1. 전체를 뒤집으면 1110011이 됩니다.
2. 4번째 문자부터 5번째 문자까지 뒤집으면 111111이 되어서 두 번 만에 모두 같은 숫자로 만들 수 있습니다.
하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있습니다.
문자열 S가 주어졌을 때, 다솜이가 해야 하는 행동의 최소 횟수를 출력하세요.
입력 조건
- 첫째 줄에 0과 1로만 이루어진 문자열 S가 주어집니다. S의 길이는 100만보다 작습니다.
출력 조건
- 첫째 줄에 다솜이가 해야 하는 행동의 최소 횟수를 출력합니다.
👆 처음에 생각한 방법은, 맨 앞 숫자를 나머지 수와 비교하면서 다른 수가 나올 경우, 그 이후에도 다른 수가 나오는지 확인하면서 count를 증가시키는 방향으로 생각했다.
결국 풀이가 더 간단하고 정확한 것 같아서 풀이대로 풀었음.
풀이는 모두 0으로 바꾸는 경우의 count 수와 1로 바꾸는 경우의 수를 비교하여 더 작은 수를 return한다.
data = input()
count0=0 #모두 0으로 바꾸는 경우
count1=0 #모두 1으로 바꾸는 경우
if data[0]=='1':
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))🗨 만들 수 없는 금액
동네 편의점 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.
예를 들어, N=5이고, 각 동전이 각각 3원,2원,1원,1원,9원짜리(화폐 단위) 동전이라고 가정합시다. 이 때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다.
입력 조건
- 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어집니다.(1<=N<=1,000)
- 둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분합니다. 이 때, 각 화폐 단위는 1,000,000 이하의 자연수입니다.
출력 조건
- 첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력합니다.
👆 화폐 단위를 오름차순으로 정렬하고 작은 단위들부터 만들 수 있는 금액을 나열한 뒤, 그 값에 큰 단위들을 더해서 만들 수 있는 금액을 확인하려고 했음. 풀이가 간단해서 그걸로 함ㅎ
target은 만들 수 있는지 확인하려고 하는 금액. target과 화폐 단위들을 비교하면서, 만약 화폐 단위가 target보다 커지면, target은 만들 수 없는 최소 값이 되므로 break. 아니라면 target에 화폐단위 더해줌.
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)
🗨 볼링공 고르기
A,B 두 사람이 볼링을 치고 있습니다. 두 사람은 서로 무게가 다른 볼링공을 고르려고 합니다. 볼링공은 총 N개가 있으며,각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번부터 순서대로 부여됩니다. 또한 같은 무게의 공이 여러 개 있을 수 있지만, 서로 다른 공으로 간주합니다. 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재합니다.
예를 들어 N이 5이고, M이 3이며 각각의 무게가 차례대로 1,3,2,3,2일 때 각 공의 번호가 차례대로 1번부터 5번까지 부여됩니다. 이때 두 사람이 고를 수 있는 볼링공 번호의 조합을 구하면 다음과 같습니다.
(1번,2번), (1번,3번), (1번,4번), (1번,5번), (2번,3번), (2번,5번), (3번,4번), (4번,5번)
결과적으로 두 사람이 공을 고르는 경우의 수는 8가지입니다. N개의 공의 무게가 각각 주어질 때, 두 사람이 볼링공을 고르는 경우의 수를 구하는 프로그램을 작성하세요.
입력 조건
- 첫째 줄에 볼링공의 개수 N,공의 최대 무게 M이 공백으로 구분되어 각각 자연수 형태로 주어집니다. (1<=N<=1,000, 1<=M<=10)
- 둘째 줄에 각 볼링공의 무게 K가 공백으로 구분되어 순서대로 자연수 형태로 주어집니다.(1<=K<=M)
출력 조건
- 첫째 줄에 두 사람이 볼링공을 고르는 경우의 수를 출력합니다.
👆 처음에 공의 최대 범위인 M의 범위가 1부터 10까지인 것을 보지 못하고 그냥 이중 for문으로 구현했다. 풀이 참고하면서, M의 범위가 1~10이므로 리스트를 이용해서 각 무게별로 볼링공이 몇 개가 존재하는지 이용하여 각 무게별로 볼링공이 몇 개가 존재하는지 기록하여 구현하면 이중 for문을 안해도 된다는 것을 알았음.
n,m = map(int,input().split())
data = list(map(int,input().split()))
#1부터 10까지 무게를 담을 수 있는 리스트
array = [0]*11
for x in data:
#무게를 array index로 이용하여 각 무게에 해당하는 볼링공의 개수를 카운트.
array[x]+=1
result=0
for i in range(1,m+1):
n-=array[i] #무게가 i인 볼링공의 개수(A가 선택할 수 있는 개수)제외
result+=array[i]*n #B가 선택하는 경우의 수와 곱하기.
print(result) 🗨무지의 먹방 라이브
문제 : https://programmers.co.kr/learn/courses/30/lessons/42891
👆 걍 단순히 중단 시간 K가 0이 될때 까지 반복문 돌리면서 1번 음식부터 차례로 소진시키려고 했다.근데 이 방식은 3번 조건을 만족시키지 못한다. 풀이는 최소 힙을 이용해서 푼다.
import heapq
def solution(food_times, k):
# 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
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) # 남은 음식의 개수
# sum_value + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
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] 이 문제는 풀이 이해가 완벽히 안됐음... 일단 파이썬 다루는게 아직 너무 미숙한 것 같아서 파이썬 문법 더 익힌 뒤에 문제를 더 풀어봐야 될 것 같다
그리디 문제를 더 풀어봐야 풀이 방식에 익숙해 질 것 같다. 문제를 보고 풀이가 잘 안 떠오르는게 문제ㅠ...
