(HackerRank) Cut the sticks 문제

풀이코드 첨부하였습니다.

오늘의 문제는…

오늘 문제는 HackerRank의 기본 문제 중에 Cut the sticks 이라는 문제를 풀어보려 합니다.
문제 링크는 이곳 입니다.

문제의 대략적인 내용은…
샘플 케이스를 보면 알겠지만, 처음에는 막대기의 갯수가 들어오고, 다음은 막대기 길이가 들어옵니다.
그래서 들어온 막대기 길이 중 가장 작은 값으로 막대기를 자르게 됩니다.

샘플 0번 케이스를 보면 금방 이해가 되실 겁니다.

sticks-length        length-of-cut   sticks-cut
5 4 4 2 2 8             2               6
3 2 2 _ _ 6             2               4
1 _ _ _ _ 4             1               2
_ _ _ _ _ 3             3               1
_ _ _ _ _ _           DONE            DONE

풀이 방법

먼저 간단하게 생각해보면 아래의 방법으로 간단하게 생각할 수 있습니다.

1. 막대기 길이 중 제일 작은 길이를 찾는다.
2. 소유한 막대에서 1번 값을 빼주고, 0이 있다면 해당 막대는 없는 것으로 간주.
3. 2번에서 마지막 막대 비교 후 총 몇개의 막대기가 남았는지 체크.
4. 존재하는 막대기가 있다면 다시 1번 연산 반복, 막대기가 없으면 연산 종료.

구현방법은 다양하겠지만 저는 아래와 같은 방법으로 구현을 생각했습니다.
먼저 두 개의 List를 사용하고, 하나는 결과를 담을 List를 주고, 하나는 막대기를 담는 List를 선언합니다.

1번의 경우 Java 컬렉션을 이용할 경우 Collections.min(inputList); 를 통해서 구할 수 있습니다.
2번의 경우 담고있는 막대기에서 1번 연산 값을 빼고, 해당 값이 0일 경우 remove를 통해서 지워줍니다.
3번과 4번은은 풀이 코드를 참고해주세요.

풀이 코드

위의 방법을 통해서 아래와 같은 결과 코드를 만들었습니다.
실질적으로 코드 동작 부분은 cutTheSticks 메서드를 참고해주세요.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    static int[] 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; } //막대기가 하나 남거나 없는 경우 순회 종료
            
        }

		 //반환 작업
        int[] retu = new int[resultList.size()];
        for(int i=0; i<resultList.size(); i++) {
            retu[i] = resultList.get(i);
        }
        
        return retu;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for(int arr_i = 0; arr_i < n; arr_i++){
            arr[arr_i] = in.nextInt();
        }
        int[] result = cutTheSticks(arr);
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i] + (i != result.length - 1 ? "\n" : ""));
        }
        System.out.println("");


        in.close();
    }
}

정리

사실 푸는데 집중해서 약간 지저분하게 풀었습니다.
처음부터 resultList를 int[] 로 선언하고 사용한다면 더욱 깔끔하게 작성될 수 있을 것 같습니다.

그리고 사실 ArrayList에서 remove는 작은 값에서는 사용해도 되지만… 실무에서는 위와 같은 방법을 쓰면 연산 속도 때문에 성능 하락이 오게 됩니다.
그래서 Linked List로 구현을 해야 됩니다.

오늘부터 하나하나 차근차근 다시 기본기를 다져봐야겠습니다.