[pg] 프로그래머스 프로세스

0.  개요

오늘도 난 힘겹게 코딩테스트 문제를 푼다.. 알고리즘은 넘나 어려운 것!! 리팩토링할 기력도 없다.. 그럼 문제를 시작하자..

 

1.  문제 정의

 문제는 다음과 같다.

1. 큐에 프로세스들이 들어 있는데 각 프로세스는 우선순위를 가지고 있다.

2. 우선순위가 높으면 높을수록 먼저 실행되야 한다.

3. 그렇기 때문에 큐에서 poll 하더라도 큐에 우선순위가 더 높은 프로세스가 존재하면 큐에 다시 프로세스를 집어 넣는다.

 

주어지는 것: 우선순위 배열, 알고자하는 프로세스의 인덱스 location

output: location으로 주어지는 프로세스가 몇 번째에 실행되는지

 

2.  나의 시도

일단 문제에서도 큐를 언급하였고, 순서대로 실행해야하는 부분이 있어 큐로 진행했다.

1. 일단 우선순위로 배열의 우선순위 값과 그 값의 위치를 index로 하여 prior이라는 객체를 만들어 진행했다.

2. 그리고 이 객체들을 큐에 모두 집어 넣고 시작했다.

3. 그리고 처음에 매개변수로 넘겨 받은 우선순위 배열을 sort하였다.

4. 우선순위 배열을 역순으로 순회하면서, 큐에서 poll.

5. 큐에서 꺼낸 프로세스의 우선순위와 우선순위 배열에서 이번에 실행할 우선순위와 일치하는지 값을 비교한 후 값이 맞으면

6. 현재 그 프로세스가 우리가 target으로하는 인덱스에 있었던 프로세스인지 확인하고 맞다면 바로 index 리턴 아니라면 위의 과정 (4번부터)을 반복. 

 

3.  Code

/**
 * @author 
 * @since 2023-07-17
 *
 * 주제: 큐/스택
 * 문제: 프로세스
 * 접근방법: 큐를 이용.
 * 1. 우선순위 값 객체를 선언하고 객체를 큐에 넣는다.
 * 2. 우선순위 값 배열을 정렬.
 * 3. 우선순위 값 배열을 역으로 순회하면서 큐에서 하나씩 꺼내서 값이 동일한지 확인 후 처리.
 * 4. 값이 같고 처리 된 경우 우리가 목표로하던 location인지 확인 후 맞다면 리턴 아니면 계속 루프 진행.
 */
public class Solution {

    public static void main(String[] args) {
        int solution = solution(new int[]{1, 1, 9, 1, 1, 1}, 5);
    }

    public static int solution(int[] priorities, int location) {
        // return 할 정답.
        Integer count = 0;

        // 인덱스와 우선순위 값이 포함된 객체를 넣을 큐
        Queue<Prior> priorQueue = new LinkedList<>();

        // 큐에 객체 삽입.
        for (int i = 0; i < priorities.length; i++) {
            priorQueue.offer(new Prior(i, priorities[i]));
        }

        // 우선순위대로 처리할 것이므로 우선순위 값이 담긴 배열을 정렬.
        Arrays.sort(priorities);

        // 현재의 처리 할 우선순위 값의 위치 (처리하면 한칸씩 마이너스 할꺼임)
        Integer presentLocation = priorities.length - 1;

        // 큐가 계속해서 돌면서 아까 정렬해둔 배열의 우선순위 값과 현재 큐의 값을 비교해가면서 루프를 돔.
        while (!priorQueue.isEmpty()) {

            Prior presentObject = priorQueue.poll();
            // -> 값이 일치할 경우: count 증가시키고, 다음 우선순위 값의 위치로 location 변경.
            if (presentObject.getValue().equals(priorities[presentLocation])) {
                count++;
                presentLocation--;
                // 목표했던 로케이션일 경우 바로 처리한 순서번호를 리턴.
                if (presentObject.getIndex().equals(location)) {
                    return count;
                }
            // -> 값이 다를 경우: 빼냈던 객체를 다시 큐에 집어 넣음
            } else {
                priorQueue.offer(presentObject);
            }
        }
        return count;
    }

    /**
     * 인덱스와 우선순위 값을 가진 객체
     */
    static class Prior {
        private Integer index;
        private Integer value;

        public Prior(Integer index, Integer value) {
            this.index = index;
            this.value = value;
        }

        public Integer getIndex() {
            return index;
        }

        public void setIndex(Integer index) {
            this.index = index;
        }

        public Integer getValue() {
            return value;
        }

        public void setValue(Integer value) {
            this.value = value;
        }
    }
}

 

4.  회고 및 깨달은 점

 문제 푸는 속도도 느리고 쉽게 답을 찾아내지 못하는 것 같다. 문제를 많이 풀어서 다양한 유형에 익숙해 져야 할 듯 하다. + 빨리 작성해야해서 귀찮긴 하지만, 코드 품질도 신경쓸 수 있다면 하자.

 

참조

https://school.programmers.co.kr/learn/courses/30/lessons/42587