[알고리즘] 그리디 알고리즘 (2)

동빈나쌤 강의 참고: https://youtu.be/2zjoKjt97vQ

 

✔️ 문제 풀어보기 - 모험가 길드

 

출처:https://youtu.be/2zjoKjt97vQ

 

이번에는 모험가 길드라는 문제이다.

지난 시간에 이어서 해당 영상에서 풀지 않았던 마지막 문제를

이번 글에서 풀어보려고 한다.

 

우선 문제 해결을 위해서 X는 1차원 배열의 형태로 받는데,

sort()를 이용하여 정렬이 필요하다는 생각을 했다.

예를 들어서 [2 2 3 2 1 4 5] 라는 형태의 입력을 받은 리스트가

[1 2 2 2 3 4 5] 와 같은 형태로 정렬된다면 가장 작은 수부터

그룹을 묶어 나가면서 성립되지 않은 그룹은 마을에 냅두면 될 것이다.

 

N = int(input())
X = list(map(int, input().split()))

result = 0

X.sort()

 

근데, 막상 코드로 작성하려니 쉽게 떠오르지 않았고

for문과 if문을 구성하다가 풀이 시간의 2배가 되었을 때 답안을 확인하였다.

답안과 비교했을 때 같았던 부분은 위에 코드밖에 없었다.. 🥲

 

import time

# 모범답안
n = int(input())
data = list(map(int, input().split))
data.sort()

# 시작
start_time = time.time()
result = 0
count = 0

for i in data:
    count += 1
    if count >= i:
        result +=1
        count = 0

print(result)

# 종료
end_time = time.time()
print("time:", end_time-start_time)

 

일단 주석으로 된 설명과 강의는 보지 않고,

모범 답안의 코드만 보고 이해한 바로는 다음과 같다.

data 리스트 안에 있는 숫자를 하나씩 꺼내서,

count가 해당 숫자보다 크거나 같으면 결과값에 1을 더해준다.

그리고 나서 count를 초기화한다.

 

초기화하는 이유는 인덱스를 건너뛰고 건너뛴 인덱스에서

값이 크거나 같은지 비교하는 연산을 추가로 계속 수행하기 위해서라고

생각했다. 예를 들어서 2라는 숫자가 일치하면 그룹이 하나 결성된 것이니까

1을 result에 추가하고 count를 초기화함으로써 2명의 멤버가 빠진 만큼의

인덱스를 이동하기 위해 초기화 후 2를 다시 더해준 뒤 i 값과 비교하는 것이다.

 

모범 답안은 보면 볼수록 간단하고,

생각했던 코드는 보면 볼수록 계속 복잡하게 생각하는 듯하다.

한 번에 쉽고 빠르게 풀 순 없지만 기초부터 천천히 공부해보자..

 

화이팅 💪