1. 막대기 길이 중 제일 작은 길이를 찾는다. 2. 소유한 막대에서 1번 값을 빼주고, 0이 있다면 해당 막대는 없는 것으로 간주. 3. 2번에서 마지막 막대 비교 후 총 몇개의 막대기가 남았는지 체크. 4. 존재하는 막대기가 있다면 다시 1번 연산 반복, 막대기가 없으면 연산 종료.
구현방법은 다양하겠지만 저는 아래와 같은 방법으로 구현을 생각했습니다. 먼저 두 개의 List를 사용하고, 하나는 결과를 담을 List를 주고, 하나는 막대기를 담는 List를 선언합니다.
1번의 경우 Java 컬렉션을 이용할 경우 Collections.min(inputList); 를 통해서 구할 수 있습니다. 2번의 경우 담고있는 막대기에서 1번 연산 값을 빼고, 해당 값이 0일 경우 remove를 통해서 지워줍니다. 3번과 4번은은 풀이 코드를 참고해주세요.
풀이 코드
위의 방법을 통해서 아래와 같은 결과 코드를 만들었습니다. 실질적으로 코드 동작 부분은 cutTheSticks 메서드를 참고해주세요.
staticint[] cutTheSticks(int[] arr) { List<Integer> inputList = new ArrayList<>(); // 막대기를 담을 리스트 List<Integer> resultList = new ArrayList<>(); //결과값 저장 리스트 resultList.add(arr.length); //결과 리스트에 처음 막대기 값을 저장
for(int i : arr) { inputList.add(i); } //막대기를 담아준다.
while (true) { int min = Collections.min(inputList); //최소 값 구하기 for (int j=0; j<inputList.size(); j++) { //막대기 값을 순회 inputList.set(j, inputList.get(j)-min); //최소값을 빼준다. if(inputList.get(j) == 0) { //만약 0이라면 해당 값을 빼주고 리스트 인덱스가 줄었으니 -1을 해준다. inputList.remove(j); j-=1; } } if(inputList.size() !=0) { resultList.add(inputList.size()); } //막대기가 남아있는 경우 남은 막대기를 결과 리스트에 저장 if (inputList.size() == 1 | inputList.size() == 0) { break; } //막대기가 하나 남거나 없는 경우 순회 종료 }