[99클럽 코테 스터디] 28일차 TIL 스택/큐

 

 

오늘의 문제는 프로그래머스

 

프로세스

 

 

문제

 

 

 

문제 설명 

프로세스의 우선순위가 담긴 배열 priorities와 몇 특정 프로세스의 위치를 나타내는 location이 매개변수로 주어졌을 때 해당 위치의 프로세스가 몇 번째로 실행되는지를 반환하는 문제입니다. 

예를 들어 입력이 priorities = [2, 1, 3, 2], location = 2 인 경우 1이 반환돼야 합니다. 

 

 

 

문제 풀이 시간 

권장 풀이 시간은 60분이었고, 저는 55분이 걸렸습니다.

 

 

 

문제 접근 방식

큐를 사용한 방식으로 문제를 풀었습니다. 먼저 큐에 priorities의 인덱스와 요소를 저장합니다. 그리고 요소를 하나씩 탐색하며 우선순위를 확인합니다. 현재 프로세스 보다 우선순위가 높은 프로세스가 있다면, 현재 프로세스를 큐의 맨 뒤로 이동시키고, 그렇지 않다면 실행 순서를 증가시킵니다. 그리고 해당 프로세스가 location에 위치한 프로세스일 경우 즉시 실행 순서를 반환합니다.

 

 

 

문제 풀이

import java.awt.Point;
import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        
        Queue<Point> queue = new LinkedList<Point>(); 
        
        int len = priorities.length;
        
        // 큐에 priorities 배열의 인덱스와 요소를 매핑해 저장 
        for(int i = 0; i < len; i++) {
            queue.add(new Point(i, priorities[i]));
        }
        
        int answer = 0; 
        
        // 요소를 꺼내 우선순위 확인하기 
        while(!queue.isEmpty()) { 
            Point current = queue.poll(); 
            boolean isHigher = false; 
            
            for(Point p : queue) {
                if(p.y > current.y) {
                    isHigher = true;
                    break;
                }
            }
            
            // 우선 순위가 높은 요소가 있으면 현재 요소를 다시 큐에 넣음 
            if(isHigher) {
                queue.add(current);
            } else {
                answer++;
                if(current.x == location) {
                    return answer; 
                }
            }           
              
        }
        
        return answer; 

    }
}

 

 

첫 번째 시도

첫 번째 시도에선 큐에서 요소를 꺼낼 때 해당 요소가 가장 우선순위가 높은지를 확인을 하려고 했습니다. 이를 확인하기 위해 priorities 배열을 오름차순으로 정렬하고 정렬된 배열에서 가장 큰 값과 비교했습니다.

문제는 priorities  배열을 오름차순으로 정렬하면 각 요소의 원래 인덱스 정보가 사라진다는 것입니다. 이로 인해 큐에서 요소를 꺼낸 후 그 요소가 원래 어느 위치에 있었는지 판단할 수 없게 되었습니다. 

import java.util.Queue;
import java.util.LinkedList;
import java.util.Arrays;

class Solution {
    public int solution(int[] priorities, int location) {
        
        Queue<Integer> queue = new LinkedList<>(); 
        LinkedList<Integer> lc = new LinkedList<>();
        
        int len = priorities.length; 
        
        // 큐에 priorities 요소 넣기 
        for(int pri : priorities) {
            queue.add(pri);
        }
        
        // priorities 배열을 오름차순으로 정렬
        Arrays.sort(priorities); 
        
        int printOrder = 0;
        int i = len - 1; // 현재 최대값의 인덱스
        
        // 요소를 꺼내 우선순위 확인하기 
        while(!queue.isEmpty()) { 		// 큐가 비어있지 않을 때까지 반복
            int a = queue.poll(); 		
            if(a == priorities[i]) { 	// 큐에서 꺼낸 값이 현재 최대값과 같다면
                lc.addLast(a); 			// 링크드 리스트에 추가
                i--; 					// 다음 최대값으로 이동
                printOrder++;
                if (queue.size() == location) {
                    return printOrder;
                }
            } else {
                queue.add(a); // 큐에 다시 추가하여 나중에 다시 비교
            }
        }

    }
}

 

 

두 번째 시도

두 번째 시도에서는 첫 번째 시도의 문제를 보완하고자 했습니다. 두 번째 시도에서는 priorities 배열을 복사해 원래 배열과 비교하려 했으나, 큐에서 꺼낸 값과 복사된 배열의 값을 비교하는 과정에서 location에 해당하는 프로세스의 출력 순서를 정확히 알기 어려웠습니다. 특히 우선순위가 같은 경우에 문제점이 발생했습니다.

import java.util.Queue;
import java.util.LinkedList;
import java.util.Arrays;

class Solution {
    public int solution(int[] priorities, int location) {
        
        Queue<Integer> queue = new LinkedList<>(); 
        LinkedList<Integer> lc = new LinkedList<>();
        
        int len = priorities.length; 
        int[] priority = new int[len];
        
        // 큐에 priorities 요소 넣기 
        for(int pri : priorities) {
            queue.add(pri);
        }
        
        for(int i = 0; i < len; i++) {
            priority[i] = priorities[i];
        }
        
        Arrays.sort(priority);
        
        int i = len - 1; 
        
        // 요소를 꺼내 우선순위 확인하기 
        while(!queue.isEmpty()) { 
            int a = queue.poll(); 
            if(a == priority[i]) { 
                lc.addLast(a); 
                i--; 
            } else {
                queue.add(a);
            }
        }
        
        int order = priorities[location];
        int answer = lc.indexOf(order);
        
        
        return answer; 

    }
}

 

 

java.awt.Point 사용하기 

java.awt.Point 클래스를 사용하면 큐에 두 개의 값을 함께 저장할 수 있습니다. 이를 통해 각 프로세스의 인덱스를 유지하면서 우선순위를 비교할 수 있었고, location에 해당하는 프로세스가 언제 출력되는지를 추적할 수 있었습니다.

데이터의 연관성을 유지하면서 복수의 값을 관리해야 하는 경우 Point와 같은 클래스나 튜플을 사용하는 것이 효과적입니다. 

 

 

 

다른 풀이 

아래 코드는 priorities 배열을 오름차순으로 정렬한 뒤, 큐에서 하나씩 요소를 꺼내면서 해당 요소가 현재 가장 높은 우선순위인지를 비교하는 방식입니다. 큐에 priorities 배열의 요소를 모두 넣은 후, 큐에서 꺼낸 값이 정렬된 배열의 가장 큰 값과 같다면 그 프로세스는 실행된 것이므로 실행 순서를 증가시킵니다. 만약 이때 location에 해당하는 프로세스가 실행된다면 그때의 순서를 반환합니다. 반면, 큐에서 꺼낸 요소가 현재 가장 높은 우선순위가 아니면 큐의 맨 뒤로 다시 넣어 나중에 다시 비교합니다. 이 과정에서 location 값을 지속적으로 추적하여 특정 프로세스가 언제 실행되는지를 정확히 파악합니다. 

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        int l = location;

        Queue<Integer> que = new LinkedList<Integer>();
        for(int i : priorities){
            que.add(i);
        }

        Arrays.sort(priorities);
        int size = priorities.length-1;



        while(!que.isEmpty()){
            Integer i = que.poll();
            if(i == priorities[size - answer]){
                answer++;
                l--;
                if(l <0)
                    break;
            }else{
                que.add(i);
                l--;
                if(l<0)
                    l=que.size()-1;
            }
        }

        return answer;
    }
}

 

 

 

 

 

 

이렇게 오늘 28일차 TIL을 작성해 보았습니다.