[백준] 1966 프린터 큐

문제 링크 : https://www.acmicpc.net/problem/1966

1966번: 프린터 큐

풀이

문제는 내가원하는 문서가 몇번째 출력되는가? 이다.

1 --> 입력받을 test case 갯수 6 0 --> 6은 배열의 크기이다 , 0은 내가 찾고싶은 문서의 INDEX위치이다. 1 1 9 1 1 1 --> 주어진 문서이다.

예시로 위처럼 입력을 받은경우에 1 1 9 1 1 1 로 정렬 된 문서에서 0번째 문서가 몇번째로 출력되는지 찾는것이다.

 

전체문서에서 처리중인 문서보다 중요도가 높은 문서가 하나라도 있다면, 인쇄하지 않고 맨 뒤로 보낸다.

 

위의 테스트 테스트케이스 에서는 아래와같이 처리가 진행 될 것이다.

 

 

핵심은 찾고자하는 index와 value를 기준으로( 위 예시에서는 index : 0 , value: 1 ) 

 

value보다 큰 대상이 존재하지 않고, index가 0번째일때까지 삭제하고, 뒤로 미뤄주는 작업을 반복해주는것이다.

 

0번째인덱스의 값은 종료되기 전까지는 계속 바뀌게 되므로 처리 대상보다 큰 값이 없으면 삭제, 있으면 미뤄주었다.

 

미뤄주고 삭제하는 작업을 위해서 LinkedList를 사용하였다.

 

이걸 코드로 풀어내기까지 정말 많은시간이 걸렸다.. ㅜㅜ

 

package PracticeETC;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
 
public class LevelCheck3 {
 
    public static void main(String[] args) throws IOException{
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int n = Integer.valueOf(br.readLine());
        
        int[] output = new int[n];
 
        for ( int i = 0 ; i < n ; i ++ ) {
 
            String[] inputs= br.readLine().split(" ");
 
            int len = Integer.valueOf(inputs[0]);
            int location = Integer.valueOf(inputs[1]);
 
            int[] intP = new int[len];
 
            String[] priorities= br.readLine().split(" ");
 
            for ( int j = 0 ; j < len; j++ ) {
                intP[j] = Integer.valueOf(priorities[j]);
            }
            
            int answer = 0;
            answer = solution(intP,location);
            output[i] = answer;
        }
        
        for ( int a : output ) {
            System.out.println(a);
        }
    }//main
 
    /*
      - location : 찾고자하는 대상의 위치이다. 
                   location에 해당하는 값을 key로 저장한 후 List에 key보다 큰 값이 존재하지 않으면서, location = 0 일때 까지 찾는다.
     
      - visit : 현재 처리 값보다 높은 level이 있으면 true 없다면 false 이다.
      
      - cnt : List에서 remove된 대상을 계산한다.
                
    */
    public static int solution(int[] p, int location) {
 
        int answer = 0;
 
        LinkedList<Integer> link = new LinkedList<Integer>();
 
        int key = 0;
        key = p[location];
 
        for ( int i = 0 ; i < p.length; i ++) link.add(p[i]);
 
        int cnt = 0 ; 
 
        while ( !link.isEmpty() ) {
 
            //System.out.print( link.toString() + "  ---> location : " + location + ", cnt : " + cnt );
 
            int obj = link.get(0);
            link.remove(0);
 
            // 현재 처리되는 대상보다 큰 level이 존재하면 뒤로 옮겨준다.
            boolean visit = false ;
 
            for ( int j = 0 ; j < link.size(); j++ ) {
                if ( link.get(j) > obj ) {
                    // 큰 값이 존재한다.
                    visit = true ;
                    // 뒤로 옮긴다.
                    link.add(obj);
                    break;
                }
            }
 
            // 큰 값이 존재하지 않는다는것은, 삭제 되었다는 의미이다.
            // 1. 삭제 된 대상이 존재 할 때마다 cnt를 늘려준다. 
            // 2. 현재의 가장 큰 값이 처리하려는 대상(key)인 경우. location이 0이면 종료한다. ( location이 0이 아니라면, 앞에 같은 level이 존재 할 수 있기 때문이다. )
            if ( !visit ) {
                if( obj == key  && location == 0 ) {
                    answer= cnt + location + 1 ;
                    break;
                }
                else cnt ++ ;
            }
 
            // location은 return조건에 만족하지 않는경우에는 무조건 -1 씩 계산한다.
            // 삭제 되었을때나, 뒤로 옮겨졌을때나 index의 위치에는 변동이 생기기 때문이다.
            // location이 0인경우에는 현재 List크기의 맨뒤로 옮겨준다.
            if ( location == 0 ) location = link.size()-1;
            else location--;
        }
 
        return answer;
    }
 
}//class
 

 

 

혹시.. 잘안되실 분들을위해서 반례 몇개를 추가합니다.

 

입력 9 87 22 6 3 7 6 8 5 2 9 7 7 4 5 8 1 2 3 3 2 8 1 8 9 9 5 7 2 2 8 2 1 5 6 3 2 9 8 4 1 7 9 7 1 4 4 2 3 4 2 4 9 9 9 8 8 2 5 1 4 1 9 4 5 3 4 4 3 2 8 1 9 7 8 7 8 9 6 9 1 5 1 9 2 1 7 1 9 9 38 21 7 5 4 3 8 7 4 8 7 9 8 4 4 4 1 3 3 5 9 1 9 9 7 9 7 2 7 7 1 5 9 8 7 2 8 3 6 2 47 35 6 5 7 8 9 2 9 8 4 5 8 4 8 7 5 8 2 4 9 4 4 6 4 6 6 4 5 1 7 6 8 2 2 6 9 8 5 6 4 8 8 9 9 6 5 5 4 90 68 3 8 7 7 2 1 3 3 5 1 8 9 9 9 8 3 6 6 7 9 7 3 5 6 3 2 1 5 3 5 8 4 1 6 1 9 6 1 2 9 2 7 8 1 4 4 3 7 7 7 6 4 9 2 9 9 1 8 4 1 1 3 4 1 6 2 9 2 3 8 8 2 4 4 2 7 7 2 5 4 8 8 7 7 7 5 7 5 1 8 34 21 7 9 7 2 8 7 3 7 3 7 1 1 1 2 3 5 1 5 5 7 5 9 5 6 2 7 8 9 1 1 1 5 1 7 69 34 2 5 3 4 2 1 2 3 2 2 5 1 6 9 5 8 9 9 2 8 5 9 5 5 1 5 7 8 2 1 4 3 3 7 4 5 7 5 5 7 6 9 5 9 6 9 7 3 7 6 1 9 5 3 4 3 7 8 8 6 6 3 6 9 9 9 2 4 2 19 16 5 2 4 7 3 1 7 9 9 2 1 8 5 5 8 2 3 6 2 91 16 1 2 6 5 4 1 2 7 7 1 2 6 3 7 6 3 4 5 2 6 6 7 8 8 6 8 1 2 9 4 8 7 3 2 3 4 3 2 2 7 2 3 3 4 9 8 4 2 4 3 5 7 1 3 5 6 1 4 7 1 5 3 5 8 4 7 2 6 8 3 3 8 4 3 9 1 2 4 2 3 6 4 7 4 7 9 9 5 1 4 3 21 10 8 8 1 4 4 8 5 8 2 8 1 2 1 2 7 2 2 7 1 7 1   출력 3 4 13 68 2 47 13 49 20