[4월 - 코딩테스트] 그리디 문제 풀이 모음

 

내가 풀이한 그리디 문제 

 

1. 프로그래머스 구명보트

https://school.programmers.co.kr/learn/courses/30/lessons/42885

프로그래머스

 

 

from collections import deque

def solution(people, limit):
    A = list()
    for person in people :
        A.append(person)
    A.sort()
    A = deque(A)
    count = 0
    
    while len(A)>1:
        data_1 = A.popleft() #작은 수
        data_2 = A.pop() #큰 수
        temp = data_1 + data_2
        
        if temp > limit :
            count += 1
            A.appendleft(data_1)
            
        elif temp <= limit :
            count +=1
            
    if len(A) == 1 :
        return count + 1
    
    else : 
        return count

 

 

---

 

2. 백준 동전개수의 최솟값 구하기

 

https://www.acmicpc.net/problem/11047

 

N,M = map(int, input().split())
A = list()

for i in range(N):
    A.append(int(input()))

count = 0
for i in range(N-1,-1,-1):
    if M >= A[i] :
        count += int(M/A[i])
        M = M%A[i]
print(count)

 

 

---

 

3. 백준 ATM

https://www.acmicpc.net/problem/11399

 

N = int(input())
A = list(map(int, input().split()))
A.sort()
S = [0] * N
S[0] = A[0]
sumnumber = 0

for i in range(1,N) :
    S[i] = S[i-1] + A[i]

for j in S :
    sumnumber += j
    
print(sumnumber)

 

 

---

 

 

4. 백준 보물

 

https://www.acmicpc.net/problem/1026

 

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A.sort()
B.sort(reverse = True)
sumnumber = 0

for i in range(N) :
    sumnumber += A[i] * B[i]
    
print(sumnumber)

 

 

---

 

5. 백준 잃어버린 괄호

 

https://www.acmicpc.net/problem/1541

 

A = input().split("-")
answer = 0

def plus(k) :
    B = k.split("+")
    sumnum = 0
    for j in B :
        sumnum += int(j)
        
    return sumnum

for i in range(len(A)) :
    M=plus(A[i])
    if i == 0:
        answer += M
        
    else :
        answer -= M
        
        
print(answer)

 

 

---

 

5. 백준 뒤집기

 

https://www.acmicpc.net/problem/1439

N = input()
count = 0

for i in range(len(N)-1) :
    if N[i] != N[i+1] :
        count += 1
        
print((count+1)//2)

 

 

 

---

 

 

6. 전자레인지

• 마지막에 출력값 형태가 리스트 형태인 줄 알고, 계속 리스트 출력하면서 왜 잘못되었는지 못 찾고 있었음
• 전형적인 그리디 - 동전문제와 비슷한 유형

n = int(input())
A = [300,60,10]
count_list = [0,0,0]

for i in range(len(A)) :
    if n >= A[i] :
        count_list[i] += int(n/A[i])
        n = n - (A[i] * count_list[i])

count_list = list(map(str,count_list))
if n==0:
    print(' '.join(count_list))
else :
    print(-1)

 

---

 

7. A->B

• m(큰 숫자)에서 부터 작은 숫자로 내려오기 
• 조건은 크게 3가지
  • 2로 나누어 떨어지는 경우
  • 마지막 숫자가 1인 경우 ( m%10 == 1 )
  • 홀수인 경우 (위의 2가지 경우에 아무것도 해당이 되지 않는 경우

https://www.acmicpc.net/problem/16953

 

n,m = map(int, input().split())
answer_list = []

while n != m :
    if m%2 == 0 and m > n:
        m = int(m/2)
        answer_list.append(m)

    elif m%10 == 1 and m > n :
        m = m//10
        answer_list.append(m)

    else :
        answer_list.append(-1)
        break

if -1 not in answer_list and answer_list[-1] == n :
    print(len(answer_list)+1)
else :
    print(-1)

 

 

---

8. 폴리오미노

• stack 으로 풀려다가... 하지만 replace 함수 이용하면 아주 쉽게 풀리는 문제였음 ㅜ

N = input()

N=N.replace('XXXX','AAAA')
N=N.replace('XX','BB')

if 'X' in N :
    print(-1)
else : print(N)

 

---

 

 

9. 세탁소사장 동혁

https://www.acmicpc.net/problem/2720

• 위의 거스름돈 문제랑 구현방법 똑같음

n = int(input()) # 몇 개 들어올건지 ?
def coin_return(m) :
    answer_list = [0]*4

    if m>=25 :
        answer_list[0] = (m//25)
        m = m%25

    if m>=10 :
        answer_list[1] = (m//10)
        m = m%10

    if m>=5 :
        answer_list[2] = (m//5)
        m = m%5

    if m>=1 :
        answer_list[3] = (m//1)
        m = m%1

    return answer_list

for i in range(n) :
    input_number = int(input())
    answer = map(str, coin_return(input_number))
    print(' '.join(answer))

 

 

---

 

10. 수들의 합 (⭐️ 복습하기)

• 초반에 실수한 것 : while 문 조건을 < start_index != n-1 and end_index !=n-1 > 이렇게 설정해줌
  • 그러나 start_index < n 이렇게 설정해줘야 함
  • 내가 초반에 설정한 조건은 start_index와 end_index가 서로 다른 위치에 있는지 여부를 판별해주는 코드임

https://www.acmicpc.net/problem/2003

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

start_index = 0
end_index = 0
sum = A[0]
count = 0

while start_index != n :
    if sum == m :
        count += 1
        sum -= A[start_index]
        start_index += 1


    elif sum < m and end_index + 1< n:
        end_index += 1
        sum += A[end_index]

    else :
        sum -= A[start_index]
        start_index += 1


print(count)