프로그래머스 프린터 문제풀이

사용한 자료구조: 링크드리스트, 원형링크드리스트

현재 우선순위보다 큰 문서가 존재한다면 다시 뒤로 넣어야 하므로 삽입과 삭제가 쉬운 링크드리스트를 사용하였다.

찾아낸 규칙

현재 문서보다 우선순위가 큰 문서가 존재하면 다시 뒤로 넣어야 하니까 원형링크드리스트를 활용하기로 했다.

그리고 문서를 다시 뒤로넣거나 확인을 위해 문서를 하나 꺼내면 index가 바뀌게 되므로 우선순위와 처음의 index를 묶어서 저장해 둬야 한다.

또한 문서를 꺼내고 난 뒤 남은 문서들과의 우선순위를 비교할 때, 남은 문서들에서 높은 우선순위를 가진 문서를 찾았을때 나머지 문서들은 비교하지 않아도 되므로 이를 판별해줄 변수(isbigger)를 하나 둔다.

코드 및 코드 설명

package linkedListPractice;

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

class Solution {

    public int solution(int[] priorities, int location) { // 원형 링크드리스트로 풀겠어
        int answer = 0;
        LinkedList<int[]> list = new LinkedList<>(); // 우선순위와 문서위치 같이 저장해둘 연결리스트
        for(int i = 0; i<priorities.length; i++){{
            list.add(new int[]{priorities[i], i}); // 우선순위와 위치를 함깨 저장한다.
        }}

        ArrayList<int[]> result = new ArrayList<>(); // 우선순위 순서대로 출력될 결과를 담을 arraylist

        while(!list.isEmpty()){
            int[] doc = list.pollFirst(); // 맨앞의 문서를 꺼낸다.
            int prior = doc[0]; // 꺼낸 문서의 우선순위를 저장한다.
            boolean isbigger = false; // 문서를 꺼내고 남은 리스트에서 꺼낸 문서보다 우선순위가 큰 문서가 있는지 확인하는 변수
            
            for(int[] document : list){ // 문서를 꺼내고 남은 리스트를 돌면서
                if(document[0] > prior){ // 현재 문서보다 우선순위가 높은 문서가 있다면
                    list.add(doc); // 꺼낸 문서를 다시 넣어준다.
                    isbigger = true; // 현재문서보다 높은 우선순위를 가진 문서가 있다고 표시한다.
                    break;
                }
            }
            if(!isbigger){ // list에 남은 문서중에 높은 우선순위를 가진 문서가 없다면
                result.add(doc); // 꺼낸 문서의 우선순위가 가장 높으므로 결과에 추가해준다.
            }
        }
        for(int i = 0; i< result.size(); i++){
            if(result.get(i)[1] == location){ // 결과를 순회하며 언제 location의 문서가 출력되는지 세어본다.
                answer = i+1;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().solution(new int[]{2, 1, 3, 2}, 2));
        System.out.println(new Solution().solution(new int[]{1, 1, 9, 1, 1, 1}, 0));

    }
}