[자료구조] 백준 - 프린터 큐

https://www.acmicpc.net/problem/1966

1966번: 프린터 큐

 

-문제해설

처음에 큐를 이용했다가 자바에서는 특정 인덱스의 원소를 출력하는 기능이 없어서 arraylist로 사용했다.

arraylist에는 .get( index ) 메소드가 있기 때문이다.

 

로직은 간단하다. 먼저 입력받을 때 point객체로 입력받는데 point.x는 입력받는 순서, point.y는 중요도를 입력받는다.

point.x는 나중에 m값과 비교해서 정답을 출력하기 위해서 필요하다.

 

그리고 이중포문으로 제일 첫 번째 중요도보다 큰 중요도를 가지는 원소가 있을 경우 첫 번째 원소를 맨 뒤로 보내준다.

이렇게 앞에 원소를 뒤로 보내주는 식으로 중요도에 대해서 내림차순 정렬한다.

 

무작정 중요도로 내림차순 정렬하면 앞에 원소를 뒤에 삽입한다는 문제의 조건에 맞지 않는다.

 

그리고 다시 반복문을 돌면서 m과 각 원소의 point.x값과 비교하여 같을 경우 반복횟수를 출력한다.

 

 

-자바

package dataStructure;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ1966 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt( br.readLine() );
		int n, m;
		StringTokenizer st;
		
		for( int i=0; i<t; i++ ) {
			st = new StringTokenizer( br.readLine() );
			n = Integer.parseInt( st.nextToken() );
			m = Integer.parseInt( st.nextToken() );
			
			//입력받은 값들을 ArrayList에 저장
			ArrayList<Point> que = new ArrayList<Point>();
			st = new StringTokenizer( br.readLine() );
			for( int j=0; j<n; j++ ) 
				que.add( new Point( j, Integer.parseInt( st.nextToken() ) ) );
			
			//j위치의 값보다 큰 값이 있을 경우 j위치 값을 뒤에 삽입
			for( int j=0; j<n-1; j++ ) {
				for( int k=j+1; k<n; k++ ) {
					if( que.get(j).y < que.get(k).y ) {
						que.add( que.get(j) );
						que.remove( j );
						k = j;
					}
				}
			}
			
			//m값과 같은 point.x값을 출력
			for( int j=0; j<n; j++ ) {
				if( m == que.get( j ).x ) {
					System.out.println( j+1 );
					break;
				}
			}
		}
		
	}
}

 

-파이썬

import sys
from collections import deque
l = sys.stdin.readline
t = int( l() )

for _ in range( t ):
    que = deque()
    n, m = map( int, l().split() )

    tmp = list( map(int, l().split()) )
    for i in range( n ):
        que.append( [ i, tmp[i] ] )
    
    for i in range( n-1 ):
        j = i+1
        while j < n:
            if que[i][1] < que[j][1]:
                tmp = que[i]
                que.remove( tmp )
                que.append( tmp )
                j = i+1
            else: j += 1
            
    for i in range( n ):
        if m == que[i][0]: print( i+1 )