[이코테 2021] 그리디 & 구현

 

알고리즘 문제는 결국 문제해결능력을 물어보는 것이다.

무작정 코딩하려 하지 말고,

주어진 문제의 "상황"을 이해하고, 그 문제를 어떻게 컴퓨터 언어를 통해서 풀어낼 것인가를 곰곰히 생각해보는 것이 중요하다.

이때, 당연히 알고리즘 종류에 대해서 정확히 이해해서 어떻게 적용시킬수 있을까를 생각하는 것과,

적절한 자료구조를 이용해서 풀어내는 것이 중요할 것.

창의적인 풀이도 좋지만 어느정도 정석적인 풀이로 접근하는 것이 좋아보인다 ( 이것이 꼭 코테가 천재들만 할 수 있는 영역이 아닌 이유)

 

 

[그리디 문제 풀이]

 

 

 

 

 

처음에는 아래와 같이 풀었다.

def solution(li):  
    key = list(Counter(li).keys())
    value = list(Counter(li).values())
    cnt = 0
    dummy = 0
    for i in range(len(key)):
        target = value[i] // key[i]
        target2 = value[i] % key[i]
        cnt +=target
        dummy +=target2
        if target2 != 0:
            cnt += dummy // key[i]
            dummy = dummy - (key[i]-1)
	return cnt

전에 collections에서 Counter을 이용해서 list에 value를 딕셔너리에 넣는 걸 알고 이용했는데,

모든 테이스케이스를 아우를수 있을지 확신하지 못하는 코드라서 쓰레기인거 같다.

data = list(map(int, input().split( )))
data.sort()

member_num = 0
result = 0

for i in range(len(data)):
	member_num += 1 
    if data[i] =< member_num:
    	result += 1
        member_num = 0

# answer = result
	

이 문제가 왜 greedy인지를 확실히 알고 이를 활용해서 푼 정석적인 코드이다.

최대한 많이 그룹을 만들어주는 것이 목표기 때문에, 최소한의 인원으로 그룹이 결성되면 바로바로 count해주는 구조

특히 sort를 해주고 if문 하나로만 이를 check하는 부분이 너무 인상깊었다 !