[프로그래머스] 탐욕법(Greedy)문제풀이

그리디 알고리즘

: 현재 상황에서 지금 당장 좋은 것만 고르는 방법

그리디 알고리즘 최적해를 찾지 못할 가능성이 높음

but 탐욕적으로 문제 접근 시 정확한 답을 찾을 수 있는 보장이 있는 경우 매우 효과적

(ex. 거스름돈의 가장 큰 화폐단위부터 배열)

 

0. 거스름돈

문제설명:

n원의 돈을 500, 100, 50, 10원자리로 거슬러 줄 경우, 최소한의 동전 개수를 구하는 문제

 

풀이: 

# 동전 수를 최소화하기 위해 큰 단위의 화폐부터 차례대로 확인하기
coin_types = [500, 100, 50, 10]
cnt = 0
for coin in coin_types:
    cnt += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin

print(cnt)

 

1. 체육복( https://school.programmers.co.kr/learn/courses/30/lessons/42862  )

문제설명:

체육복을 놓고 온 사람과 여분을 가져온 사람의 리스트를 받아 체육수업을 들을 수 있는 최대값을 구하는 문제

풀이1: 

진짜 문제의 큰 틀을 보지 못한 채 되는대로 적은 코드다...분발하자

N = int(input())
empty = list(map(int,input().split()))
extra = list(map(int,input().split()))

students = [1]*N
for num in range(N):
	if num in [x-1 for x in empty]:
		students[num] -=1
	if num in [x-1 for x in extra]:
		students[num] +=1

for num in range(len(students) - 1):
	if students[num] > 1:
		if students[num + 1] == 0:
			students[num] -= 1
			students[num+1] +=1

for num in range(1, len(students)):
	if students[num] > 1:
		if students[num - 1] == 0:
			students[num] -= 1
			students[num-1] +=1

print(students.count(1)+students.count(2))

 

풀이2:

set을 이용하여 집합끼리의 뺄셈을 이용하여 reserve와 lost를 정의하였으며 set의 여부에 의해 체육복 여부 확인가능 

def solution(n, lost, reserve):
 reserve_set = set(reserve) - set(lost)
 lost_set = set(lost) - set(reserve)

 for num in reserve_set:
  if num - 1 in lost_set:
   lost_set.remove(num - 1)
  elif num + 1 in lost_set:
   lost_set.remove(num + 1)
 answer = n-len(lost_set)
 return answer

N = int(input())
lost = list(map(int,input().split()))
reserve = list(map(int,input().split()))

print(solution(N,lost, reserve))