Today's Algorithm(2018-10-25)

programmers 기능개발

최근에 이 문제를 시도하였다가 실패했던 적이 있었습니다. 그 때 저의 가장 큰 실수는 문제를 잘못 이해했던 것이었고 그 때문에 시간은 시간대로 날리고 문제도 해결하지 못했던 기억이 있습니다. 그래서 알고리즘 문제풀이에서 가장 기본 중의 기본인 문제를 다시 꼼꼼하게 읽고 시작하였습니다.

이 문제에서 가장 핵심은 제일 앞부분부터 완료되어야 한다는 것입니다. 앞부분부터 나가야 뒤에도 나갈 수 있는 터널과 같은 구조인 것입니다. 그래서 Queue를 써야겠다는 생각이 들었습니다.

 

그리고 테스트코드를 통해 하나하나씩 접근하였습니다. 제가 먼저 궁금했던 것은 큐가 반복되는 환경에서 큐의 개수를 줄여나갈 수 있는지였습었습니다. 왜냐하면 앞 부분부터 하나씩 빠져나가려면 이런 환경에서 제대로 작동하는지 확인해야 했기 때문입니다.

    @Test
    public void 큐_테스트() {
        LinkedList<Integer> queue = new LinkedList<>(Arrays.asList(1, 2, 3, 4, 5));

        while (!queue.isEmpty()) {
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; i++) {
                System.out.print(queue.get(i));
            }
            System.out.println();
            queue.poll();
        }
    }

처음에 반복문 내에서 poll()메서드도 시도해봤지만 오류가 발생하였습니다. 왜냐하면 인덱스 개수에 따라 돌아가고 있는 와중에 내용이 변경되었기 때문입니다. 하지만 위와 같이 반복문 밖에서 poll()를 호출하고 매번 큐의 개수를 파악하여 이에 따라 반복문 돌리니 위와 같은 결과가 확인되었습니다. 의도한대로 나온 것입니다.

 

이제는 Queue에 원하는 형태의 값들을 넣고 문제에 맞게 해결하면 됩니다. 이것 역시 테스트코드에서 먼저 접근해나갔니다. 하다보니 처음엔 큐 안에 Integer로 선언하였는데 progresses와 speeds의 인덱스를 맞춰주려면 이 2개의 값을 동시에 가지고 있으면서 일이 끝나면 이것도 같이 없애는게 좋겠다라는 생각이 들었습니다. 따라서 Job이라는 Inner Class를 다음과 같이 만들고 이를 Queue안에 넣었습니다.

        class Job {
            int progress;
            int speed;

            public Job(int progress, int speed) {
                this.progress = progress;
                this.speed = speed;
            }
        }

 

이젠 문제에 맞게 구현하면 되는데요. 간단하게 다음과 같이 접근할 수 있습니다.

1. Queue의 개수에 따라 반복문을 돌면서 각각의 progress에 speed를 더한다
2. progress가 100보다 크고 비어있지 않을 때를 조건으로 while 반복문 돌려 조건에 만족하면 poll()로 꺼내고 꺼낸 갯수를 세아린다

 

결국은 다음과 같은 코드를 작성하였습니다.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        List<Integer> tempAnswer = new ArrayList<>();
        LinkedList<Job> queue = new LinkedList<>();

        for (int i = 0; i < progresses.length; i++) {
            Job job = new Job(progresses[i], speeds[i]);
            queue.add(job);
        }

        while(!queue.isEmpty()) {
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; i++) {
                queue.get(i).progress += queue.get(i).speed;
            }

            int count = 0;
            while(!queue.isEmpty() && queue.peek().progress >= 100) {
                queue.poll();
                count++;
            }

            if(count > 0) {
                tempAnswer.add(count);
            }
        }

        int[] answer = new int[tempAnswer.size()];
        for (int i = 0; i < tempAnswer.size(); i++) {
            answer[i] = tempAnswer.get(i);
        }

        return answer;
    }

    class Job {
        int progress;
        int speed;

        public Job(int progress, int speed) {
            this.progress = progress;
            this.speed = speed;
        }
    }
}

차근차근 테스트코드로 다양한 시도를 시도를 해가면서 접근하니 크게 어려웠지 않았던 것 같아요. 물론 이렇게 짜는게 비효율적일 수도 있겠지만 지금 단계에선 테스트코드도 연습할 겸 재미있었습니다.