이코테 - 그리디 알고리즘 풀이 Python Java

문제

파이썬 풀이

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)

 

JAVA 풀이

import java.util.*;

public class Main{

  public static int n;
  public static ArrayList<Integer> arrayList = new ArrayList<>();
  public static void main(String [] args){
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();

    for(int i=0 ; i < n ; i++){
      arrayList.add(sc.nextInt());
    }
    Collections.sort(arrayList);

    int result = 0;
    int count = 0;
    for(int i=0; i<n ;i++){
      count+=1;
      if(count >= arrayList.get(i)){
         result += 1;
         count = 0;
      }
    }
    System.out.println(result);
  }
}

 

해설

오름차순으로 정렬하고, 공포도가 낮은 모험가부터 하나씩 확인한다.

그 후 모든 모험가들을 차례대로 검사한다.

• 현재 모험가의 공포도가 그룹인원보다 높다면 그룹인원에 추가하고 다음 모험가를 탐색한다.
• 현재 모험가의 공포도가 그룹인원과 같다면 그룹을 경성해 여행을 떠난다.

그리고 다음 모험가를 탐색하며 새로운 그룹을 만든다.

 

 

좋은 강의를 제공해주는 "동빈나"님께 감사를 드린다