[정렬] 프린터

[프로그래머스] 프린터

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

 

 

 

*정답으로 제출한 풀이

-문제에서 제시한 대로 움직임. 목표숫자를 마킹해 놓고 정렬한 뒤 나중에 검색해서 위치를 판별

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {

        List<Print> list = new ArrayList<>();
        for(int i=0; i<priorities.length; i++){
            if(i==location) list.add( new Print(priorities[i], true) );
            else list.add( new Print( priorities[i], false ) );
        }

        int listSize = list.size();
        int cursur = 0;
        while (cursur < listSize){
            boolean isChange=false;
            for(int i=cursur+1; i<listSize; i++){
                if(list.get(cursur).priority < list.get(i).priority){
                    isChange=true;
                    list.add( list.get(cursur) );
                    list.remove( cursur );
                }
            }
            if(isChange==false) cursur++;
        }//while

        int answer=0;
        for(int i=0; i<list.size(); i++){
            if(list.get(i).target==true) answer=i+1;
        }

        return answer;
    }

    static class Print{
        int priority;
        boolean target;

        public Print(int priority, boolean target) {
            this.priority = priority;
            this.target = target;
        }
    }
}

 

 

*시간 지난뒤에 다시 풀어봄. 나중에 검색하는 게 아니라 인쇄하는 과정에서 목표하던 인쇄물이면 바로 카운트 출력,

package com.company;

import java.lang.reflect.Array;
import java.util.*;

public class Solution {
    public static void main(String[] args) {
		int[] priorities = {1, 1, 9, 1, 1, 1};
		int location = 0;

		List<Print> prints = new ArrayList<>();

		//데이터등록
		for(int i=0; i<priorities.length; i++){
			Print print;
			if(location==i) print = new Print(priorities[i], true);
			else print = new Print(priorities[i], false);
			prints.add(print);
		}


		int count=0;
		int answer;

		while(true){

			//자리교체
			boolean isChanged = false;
			for(int i=1; i<prints.size(); i++){
				if(prints.get(0).priority < prints.get(i).priority){
					prints.add( prints.get(0) );
					prints.remove(0);
					isChanged = true;
					break;
				}
			}

			//인쇄
			if(isChanged==false){
				count++;
				if(prints.get(0).mark==true){
					answer = count;
					break;
				}
				prints.remove(0);
			}
		}

		System.out.println("답: " + answer);
	}


	static class Print{
		int priority;
		boolean mark;

		public Print(int priority, boolean mark) {
			this.priority = priority;
			this.mark = mark;
		}
	}
}

 

 

*큐를 이용한 풀이

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

class Solution {
    public int solution(int[] priorities, int location) {
        
        Queue<Integer>  =new LinkedList<>();
        for(int p:priorities) {q.offer(p);}
        int count=0;
        
        while(!q.isEmpty()) {
            int item = q.poll();
            
            //q에 지금item보다 큰 값이 있는지 확인
            boolean check = true;
            for(int s:q) {
                if(item<s) {
                    check=false;
                }
            }
            
            //출력이될때마다 count++ / 아니면 아이템을맨끝에 넣는다.
            if(check) {
                count++;
                if(location==0) return count;
            }else q.offer(item);
            
            //정답의 위치추적
            location--;
            if(location<0)location+=q.size();
        }
        return count;
    }
}

 

 

이런 식으로 큐 내부를 탐색할 수 있다

boolean check = true;
for(int s:q) {
    if(item<s) {
        check=false;
    }
}

 

 

 

 

*안되는 풀이

샘플은 괜찮은데, 테스트 케이스에서 에러난다. 왜 에러가 나는지 아직 생각못함.

package com.company;

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

public class Main {

public static void main(String[] args) {

List<Integer> list = new ArrayList<>();
for(int priority: priorities){
list.add(priority);
}

int listSize = list.size();
int cursor=0;
while(cursor<listSize){

Boolean moving=false;
for(int i=cursor+1; i<list.size(); i++){

//자리교환이 일어남
if(list.get(cursor)<list.get(i)){
list.add( list.get(cursor) );
list.remove(cursor);
moving = true;

if(cursor==location){
location=listSize-1; //타겟이 맨 뒤로 넘어가는 경우
System.out.println("타겟넘어감: " + location);
}
else location--; //다른 애가 맨 뒤로 넘어가는 경우, 타겟은 한칸 앞으로 떠내려온다
}
}

//자리교환 없음
if(!moving){
cursor++;
}
}

System.out.println("answer: " + location);
}
}

 

2022. 7. 27

PriorityQueue를 이용한 풀이

import java.util.*;

class Solution {
    Queue<Work> queue = new LinkedList<>();
    PriorityQueue<Work> pq = new PriorityQueue<>();

    public int solution(int[] priorities, int location) {

        int count = 0;
        for(int i=0; i<priorities.length; i++) {
            Work work = new Work(priorities[i], i);
            queue.add(work);
            pq.add(work);
        }

        while(!queue.isEmpty()) {
            Work work = queue.poll();

            if(work.priority >= pq.peek().priority) {
                count++;
                if(work.index == location) return count;
                pq.remove(work);
            } 
            else {
                queue.add(work);
            }
        }
        return -1;
    }

    static class Work implements Comparable<Work> {
        int priority;
        int index;

        Work(int priority, int index) {
            this.priority = priority;
            this.index = index;
        }

        @Override
        public int compareTo(Work w) {
            if(this.priority > w.priority) return -1;
            return 1;
        }
    }
}