Greedy 01 모험가 길드

01 ) 모험가 길드

처음엔 문제도 이해가 안가서 문제만 3번 읽은 거 같다...ㅎ

문제 이해한 뒤 공포도가 높은 순서대로 정렬해서 그룹이 지어진대로 인원을 착착 빼면 될 거라고 생각했다.

**리스트 정렬 방법

• list.sort() : 원본리스트를 직접 정렬(리스트만 정렬 가능하지만 sorted 보다 빠름)
• sorted(list) : 정렬한 새 리스트를 반환(리스트 외에 문자열, 튜플, 딕셔너리 등에도 사용 가능)

**리스트의 요소를 삭제하는 방법

• del 구문: 인덱스나 슬라이스로 특정 범위의 요소를 삭제(메서드 아님)
• clear(): 리스트의 모든 요소를 삭제
• remove(): 입력한 값을 검색해서, 첫 번째 검색 결과를 삭제
• pop(): 맨 뒤의 값을 삭제. 인자를 지정할 경우 특정 위치의 값을 삭제

[처음에 짠 코드]

n = 5 # N명의 모험가
data = [2, 3, 1, 2, 2] # 공포도 X data
data.sort(reverse=True) # 공포도가 높은 순으로 정렬

result = 0 # 그룹 수

while n != 0:
    print(data[0])
    n - data[0]
    for i in range(data[0]):
        del data[i]
        print(data)
    result += 1

print(result)

i 갯수만큼 for문 돌려서 0, 1, 2 이렇게 순서대로 착착 빼주면 될 거라고 생각했다.

돌려보니까 IndexError: list assignment index out of range 오류가 남. 왜지???

print로 data를 찍어보니까 [3, 2, 2, 2, 1] 에서 0, 1, 2번째가 빠져나가고 [2, 1]이 남아야 하는데 [2, 2]가 남아있음. ???

이 때부터 뭔가 이상함을 감지.

0번이 빠진 후에 다음 for문이 돌면 [2, 2, 2, 1] 에서 1번이 빠지는 거니까 쟤가 빠질 거고

1번이 빠진 후에 다음 for문이 돌면 [2, 2, 1] 에서 2번이 빠지는 거니까 1이 빠져서 최종적으로 [2, 2]만 남았던 거다...!

for문 돌릴 때마다 계속해서 첫번째 요소를 빼줘야 하는 거 였음. (이런 간단한 오류 찾는데도 꽤 걸렸다.)

그러고 다시 돌렸는데 한가지 간과한 것이 있었다.

n이 0이 아닐 때 계속 while문이 돌게 코드를 짰는데 (다 빼면 0이 될테니까)

n - data[0]

이렇게 짜놨던 거!

n -= data[0]

이렇게 마이너스 한 값이 n에 저장되도록 -=로 고쳐줬다.

    if n < 1 :
        break

혹시라도 무한루프에 빠지지 않도록 n이 1보다 작을 때 while문 빠져나가게 if문도 추가

(제대로 된 데이터라면 최종적으론 n = 0 이겠지만 1보다 작음으로 설정해뒀다.) 

[최종코드]

n = 5 # N명의 모험가
data = [2, 3, 1, 2, 2] # 공포도 X data
data.sort(reverse=True) # 공포도가 높은 순으로 정렬

result = 0 # 그룹 수

while n != 0: # 그룹이 없는 모험가가 없을 때까지 while 문 돌리기
    if n < 1 :
        break
    print(data[0])
    n -= data[0] # 가장 큰 수만큼 그룹 묶기
    for i in range(data[0]): # 그룹이 만들어지는 인원
        del data[0] # 그룹이 만들어진 인원은 리스트에서 제거
        print(data)
    result += 1 # 그룹 수 추가

print(result)

> 디버깅하면 1.9초대, 그냥 실행했을 땐 0.7초대가 나온다.

 

 

# 책 해설
n = int(input())
data = list(map(int, input().split()))
data.sort()

result = 0 # 총 그룹의 수
count = 0 # 현재 그룹에 포함된 모험가의 수

for i in data: # 공포도를 낮은 것부터 하나씩 확인하며
    count += 1 # 현재 그룹에 해당 모험가를 포함시키기
    if count >= i: # 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성
        result += 1 # 총 그룹의 수 증가시키기
        count = 0 # 현재 그룹에 포함된 모험가의 수 초기화

print(result)

책 해설 보면서 뭔가 이상함을 깨달음ㅋㅋㅋㅋㅋㅋㅋㅋ 왜 나랑 반대로 오름차순 정렬을 하지?

문제를 다시 차근차근 읽어보니

"또한 몇 명의 모험가는 마을에 그대로 남아 있어도 되기 때문에, 모든 모험가를 특정한 그룹에 넣을 필요는 없습니다."

다같이 모험을 떠나야지 왜 남기고 가요ㅜㅜㅜㅜㅋㅋㅋㅋ 이 문구를 못읽고 풀어서 풀이방법이 완전 반대가 됐다... :<

오늘의 교훈 : 문제를 끝까지 잘 읽자.