알고리즘 / 자료구조’ 시리즈

[이.취.코] Chap 11. 그리드 - Q1. 모험가 길드

  • 0
  • 0
0
0

1. 모험가 길드

  • 난이도
  • 풀이 시간
    • 30분
  • 시간 제한
    • 1초
  • 메모리 제한
    • 128MB
  • 기출
    • 핵심 유형

A. 문제

모험가 N명이 있다.
모험가 길드에서는 N명의 모험가를 대상으로 공포도를 측정했다.
모험가 길드장은 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참가해야 여행을 떠날 수 있도록 규정했다.

최대 몇 개의 모험가 그룹을 만들 수 있는가?

몇 명의 모험가는 마을에남아있어도 되기 때문에 모든 모험가를 특정한 그룹에 넣을 필요는 없다

a. 예를 들면.

N = 5 모험가의 공포도 = 2 3 1 2 2

그룹 1에 공포도가 1, 2, 3인 모험가.
그룹 2에 공포도가 2, 2인 모험가.
총 2개의 그룹을 만들 수 있다.

b. 입력 조건
  • 모험가의 수 N
    • 1 <= N <= 100,000
  • 각 모험가의 공포도
    • N 이하의 자연수, 각 자연수는 공백으로 구분
c. 출력 조건
  • 여행을 떠날 수 있는 그룹 수의 최댓값
d. 테스트 케이스
  • 입력 예시

    
    5
    2 3 1 2 2
    
    
    • 내가 만든 입력 예시

      
      5
      1 1 1 1 1
      4 4 4 4 4
      1 2 4 3 1
      2 3 1 2 2
      
      
  • 출력 예시

    
    2
    
    
    • 내가 만든 입력 예시

      
      5
      1
      2
      2
      
      

B. 내 답안

a. 1차 풀이
  
n = int(input())  
arrays = list(map(int, input().split()))   
  
arrays.sort(reverse=True)  
group = 0  
start = 0  
i = 0  
while arrays:  
    if start == i:  
        start = arrays[0]  
        if len(arrays) >= start:  
            group += 1  
            i = 0  
    else:  
        pass  
    arrays.pop(0)  
    i += 1  
print(group)  

b. 시간 복잡도를 줄인 코드

n = int(input())  
arrays = list(map(int, input().split()))  
  
arrays.sort(reverse=True)  
group = 0  
start = 0  
count = 0  
ar = []  
del_array = []  
for i in range(len(arrays)):  
    if start == count:  
        start = arrays[i]  
        # ar.append(start)  
        if len(arrays) - len(del_array) >= start:  
            group += 1  
            count = 0  
    del_array.append(arrays[i])  
    count += 1  
  
print(group)  

c. 좀 더 간단하게 푼 코드

n = int(input())  
arrays = list(map(int, input().split()))  
  
arrays.sort(reverse=True)  
group = 0  
start = [0]  
count = 0  
ar = []  
del_array = []  
for i in range(len(arrays)):  
    if start[-1] == count:  
        start.append(arrays[i])  
        # ar.append(start)  
        if len(arrays) >= sum(start):  
            group += 1  
            count = 0  
 # del_array.append(arrays[i])  
 count += 1  
  
print(group)

a. 회고

풀이

한 그룹에서 가장 공포도가 큰 수만큼 그룹의 인원수를 조정해야한다. 따라서 공포도를 내림차순 정렬하였다. 그리고 모험가 중 가장 큰 공포도만큼 그룹을 짓는 행위를 반복했다.

반성

  • 너무 복잡하게 생각해서, 상당히 오래 걸린 문제.
  • 문제를 그림으로 그리든 해서, 단순화 시키고 간단하게 푸는 연습을 해야겠다.

결론

  • 책의 정답 코드도 틀릴 수 있다.
    • 내가 만든 테스트 케이스에서는 책의 답지가 정상적으로 작동하지 않는다.
  • 일단 문제를 해결하고, 시간 복잡도를 줄여나가는 방법을 찾는 것은 잘한 것 같다.

C. 책의 문제 해설

공포도를 기준으로 오름차순으로 정렬을 수행하자. 공포도가 가장 낮은 모험가부터 하나씩 확인하여, 그룹에 포함될 모험가의 수를 계산할 수 있다. 현재 그룹에 포함된 모험가의 수가 현재 확인하고 있는 공포도보다 크거나 같다면, 그룹을 결성할 수 있다.

a. 책 답안

python-for-coding-test/1.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.