5-4 프린터

유태형·2022년 6월 5일

Java 알고리즘 프로그래머스

알고리즘 - Java

목록 보기

14/32

출처

해당 게시글은 [Java] 어서와! 자료구조 알고리즘은 처음이지?https://programmers.co.kr/learn/courses/13577를 간략히 요약한 게시글이며 모든 출처는 해당강의에 있습니다.

문제

문제 분석

맨 앞에 있는 문서의 우선순위를 다른 문서들과 비교하여 우선순위가 가장 높다면 인쇄하고 더 높은 우선순위의 문서가 존재하면 맨 뒤로 보내는 문제입니다.

풀이

2가지를 함께 고려하여야 합니다.
1. 우선순위가 가장 높은지 아닌지
2. 인쇄하고자 하는 문서인지

나의 풀이

	public static int solution(int[] priorities, int location){
        //링크드 리스트 선언
        ArrayList<Integer> list = Arrays.stream(priorities).boxed().collect(Collectors.toCollection(ArrayList::new));
        int priority = 0;
        while(!list.isEmpty()){
            //제일 큰지 비교
            if(list.stream().mapToInt(i->i).max().getAsInt() <= list.get(0)){ //제일 큰 값인지 비교
                //우선순위 1추가(0부터 시작)
                priority++;
                //찾는 문서가 출력 차례면 더이상 찾기 x
                if(location == 0)
                    break;
                else{ //찾는 문서가 아니면
                    location--; //한칸 앞으로
                    list.remove(0); //출력
                }

            }else{ //아니면
                //맨 뒤로 삽입
                int first = list.remove(0);
                list.add(first);
                //찾는 문서가 맨 뒤로 가야하면 location은 맨 뒤로
                if(location == 0)
                    location = list.size()-1;
                else //찾는 문서가 아니면
                    location--; //한칸 앞으로
            }
        }
        return priority; //우선순위 출력
    }

인쇄하고자 하는 문서인가를 if(location == 0)으로 맨앞에 존재하는가로 구분하였고
인쇄하고자하는 문서가 아니면 location--, 인쇄하고자 하는 문서면 location = list.size()-1로 문서의 위치를 추적하였습니다.

강의의 풀이

	class Paper {
        boolean isMine;
        int priority;

        Paper(int p, boolean m) {
            priority = p;
            isMine = m;
        }

    }

    public int solution(int[] priorities, int location) {
        List<Paper> queue = new LinkedList<>(); //문서를 담을 큐
        for (int i = 0; i < priorities.length; i++) {
            queue.add(new Paper(priorities[i], i == location)); //큐에 내용 추가
        }
        
        int answer = 0;
        while (!queue.isEmpty()) {
            Paper now = queue.remove(0);
                
            boolean printable = true;
            for (Paper p : queue) {
                if (now.priority < p.priority) {
                    printable = false;
                    break;
                }
            }

            if (!printable) {
                queue.add(now);
                continue;
            }
                
            answer++;
            if (now.isMine) return answer;
        }
        return answer;
    }

클래스를 만들어 2가지의 정보를 저장하는 자료구조를 만들었습니다. location을 문서하나하나 처리할때마다 이동시키던 저의 풀이와 다르게 강의에서는 자료구조를 만들때 location위치를 단 1번만이용하여 인쇄하고자 하는 문서인지 여부를 저장하였습니다.

저의 풀이와 강의의 풀이는 모두 우선순위와 선택한 문서인지 여부 2가지를 같이 고려하여 경우를 나누었습니다.

소스코드

package StackQueue스택큐;

import java.util.*;
import java.util.stream.*;

public class 프린터 {
    public static int solution(int[] priorities, int location){
        //링크드 리스트 선언
        ArrayList<Integer> list = Arrays.stream(priorities).boxed().collect(Collectors.toCollection(ArrayList::new));
        int priority = 0;
        while(!list.isEmpty()){
            //제일 큰지 비교
            if(list.stream().mapToInt(i->i).max().getAsInt() <= list.get(0)){ //제일 큰 값인지 비교
                //우선순위 1추가(0부터 시작)
                priority++;
                //찾는 문서가 출력 차례면 더이상 찾기 x
                if(location == 0)
                    break;
                else{ //찾는 문서가 아니면
                    location--; //한칸 앞으로
                    list.remove(0); //출력
                }

            }else{ //아니면
                //맨 뒤로 삽입
                int first = list.remove(0);
                list.add(first);
                //찾는 문서가 맨 뒤로 가야하면 location은 맨 뒤로
                if(location == 0)
                    location = list.size()-1;
                else //찾는 문서가 아니면
                    location--; //한칸 앞으로
            }
        }
        return priority; //우선순위 출력
    }

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