문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

문제

여러 길이의 막대가 주어진다. 가장 짧은 막대를 버리면서 반복적으로 작게 자른다. 각 반복에서 가장 짧은 막대를 결정하고, 해당 길이를 긴 막대에서 잘라내고 그 최소 길이의 막대를 모두 버린다. 남은 막대가 모두 같은 길이일 때 더 이상 줄일 수 없으므로 해당 막대들을 버린다.
n개의 막대가 주어졌을 때, 남은 막대의 개수를 각 반복 전까지 출력해라.

Example

arr = [1, 2, 3]

가장 짧은 막대의 길이는 1이고, 두 개의 막대에 그 길이만큼 자르고, 자른 조각은 버린다. 지금 길이는 arr = [1, 2]이다. 다시, 가장 짧은 막대의 길이는 1이고, 그 길이만큼 자르고 버린다. 단 하나의 막대 arr = [1]만 있고, 버린다. 각 반복의 답은 answer = [3, 2, 1]이다.

Function Description

cutTheSticks 함수를 완성해라. 이 함수는 각 반복이 수행되기 전의 막대 개수를 나타내는 정수 배열을 출력한다.
cutTheSticks 함수는 아래와 같은 매개변수를 가지고 있다.

• int[]: 각 막대의 길이 배열

Return

• int[]: 각 반복 후의 길이

Constraints

• 1 <= n <= 1000
• 1 <= arr[i] <= 1000

풀이

결과를 담을 배열을 선언하고, 매개변수로 넘어오는 배열을 정렬을 한다.

List<Integer> answer = new ArrayList<>();
        
arr.sort(Comparator.naturalOrder());

while문을 통해 arr의 길이가 0보다 클때까지 반복해준다. 시작할 때, answer에 arr의 길이를 추가한다.

while(arr.size() > 0){
	answer.add(arr.size());

	int min = arr.get(0);
	int idx = 0;
}

그리고 arr의 최소값인 0번째 값과 해당 인덱스인 0을 할당한다. 그리고 while문을 한번 더 사용한다.

while(arr.size() > 0){
	answer.add(arr.size());

	int min = arr.get(0);
	int idx = 0;
    
    while(idx < arr.size()){
    	// ...
    }
}

while문 안에 if문을 사용해서 배열에서 뺄 값은 빼주고, 값에서 최소값을 빼준다.

while(idx < arr.size()){
	if(arr.get(idx) - min == 0){
    	arr.remove(idx);
    }else{
    	arr.set(idx, arr.get(idx) - min);
        idx++;
    }
}

마지막에 answer를 반환한다.

return answer;

전체 코드

public static List<Integer> cutTheSticks(List<Integer> arr) {
	List<Integer> answer = new ArrayList<>();

	arr.sort(Comparator.naturalOrder());

	while(arr.size() > 0){
		answer.add(arr.size());

		int min = arr.get(0);
		int idx = 0;

		while(idx < arr.size()){
			if(arr.get(idx) - min == 0){
				arr.remove(idx);
			}else{
				arr.set(idx, arr.get(idx) - min);
				idx++;
			}
		}
	}

	return answer;
}