ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [백준][자바][1021]회전하는 큐
    코딩/알고리즘 2018. 10. 11. 22:21

    와...진짜 문제를 잘읽어야한다

    그냥 덱을 생각하고 짯는데 알고보니까 뒤로 뺴는게 안되더라

    전체적으로 문제를 이해하는데 시간도 오래걸렸다...


    오늘 문제를 제대로 이해하고 다시해보니...

    20분만에 풀어버렸다...


    ...문제는 다음과같다


    예를 들어 

    7 4 

    4 6 7 5

    라고 하면 


    1 2 3 4 5 6 7 이라는 큐에서 4 6 7 5숫자를 찾으면된다 .

    숫자위치라는데 해당 숫자를  찾는거다...이거때문에도 한참 해맷다..


    한번 해보자면


    1 2 3 4 5 6 7  중 4 앞에 3개, 뒤에도 3개가 있다 이럴 경우는 앞에서 부터 뒤로 보낸뒤 poll 하면된다.  3번이 카운트 된다 ans = 3   

    5 6 7 1 2 3  중 6을 뽑으면 된다  6앞에는 1개 뒤에는 4개가 있다

    볼것도 없이 앞에 것을 뒤로 밀고 poll하면 된다 1번이 카운트 된다 ans = 4

    7 1 2 3 5 은 큐 앞에 있으므로 바로 뽑는다  0번이 카운트 돤다 ans = 4

    1 2 3 5 중 5를 뽑으면 된다 앞에 것이 많으므로  뒤에것을 앞으로 밀고 뽑으면 된다 1번이 카운트 된다 ans =5 


    이런 식으로 차근차근 하면 순식간에 풀리는...그런 문제였다..

    이번엔 함수를 좀 많이 써봤는데

    함수가 주어진 역할만 딱! 수행하도록 만들어 봤다.

    조금 비효율적이지만 나중에 디버깅하기엔 괜찮은거같은데...



    import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.Deque;
    import java.util.Iterator;
    import java.util.Scanner;
    
    public class backjoon_1021_큐 {
    	static Deque q = new ArrayDeque();
    	static ArrayList arr = new ArrayList();
    	static int n ;
    	static int m ;
    	static int number_2 = 0;
    	static int number_3 = 0; 
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		n = sc.nextInt();
    		m = sc.nextInt();
    		/* input */
    		for (int i = 0 ; i < m; i++) {
    			int value = sc.nextInt();
    			arr.add(value);
    		}
    		for(int i =1; i <= n; i++) {
    			//System.out.println(i);
    			q.add(i);	
    		}
    		//System.out.print("맨처음");
    		//printQueue();
    		for ( int i = 0 ; i < arr.size(); i++) {
    			 //System.out.println("-------------");
    			 //System.out.println("찾아야할  data" + arr.get(i));
    			 int findIdx = find ( arr.get(i)); 
    			 //System.out.println("findIdx = " + findIdx);
    			 int judgeValue = judge(findIdx); // judge value return 
    			 //System.out.println("judgeValue = " + judgeValue);
    			 q_Remake(judgeValue,findIdx);
    			 //printQueue();
    			 //System.out.println("-------------");
    			
    		}
    		System.out.println(number_2 + number_3);
    		
    		
    		
    	}
    	public static void printQueue() {
    		Iterator e = q.iterator();
    	       while(e.hasNext()){
    			int val =(e.next());
    			System.out.print(val + " ");
    		}
    	       System.out.println();
    	}
    	
    	public static void q_Remake(int judgeValue, int findIdx) {
    		/* 앞이 더 많은 경우 */
    		if( judgeValue == 0 ) {
    			int loopCNT = ( q.size() - findIdx ) + 1 ; //자기자신까지 넘겨야함으로
    			number_2 += loopCNT;
    			//System.out.println("JUDGE = 0 loopCNT "+ loopCNT);
    			for(int i =0; i < loopCNT; i++ ) {
    				int qpl = q.pollLast();
    				q.push(qpl);
    			}
    			q.poll();
    			
    		}
    		/* 뒤가  더 많은 경우 */
    		if( judgeValue == 1 ) {
    			int loopCNT = findIdx - 1;
    			number_3 += loopCNT;
    			//System.out.println("JUDGE = 1 loopCNT "+ loopCNT);
    			for(int i =0; i < loopCNT; i++ ) {
    				int qpf = q.pollFirst();
    				q.add(qpf);
    			}
    			//앞에꺼 빼기 
    			q.poll();
    		}
    		//같은 경우
    		if ( judgeValue == 2 ) {
    			q.poll();
    		}
    		// 앞이랑 뒤가 같은 경우 
    		if( judgeValue == 3 ) {
    			int loopCNT = findIdx - 1;
    			number_3 += loopCNT;
    			//System.out.println("JUDGE = 1 loopCNT "+ loopCNT);
    			for(int i =0; i < loopCNT; i++ ) {
    				int qpf = q.pollFirst();
    				q.add(qpf);
    			}
    			//앞에꺼 빼기 
    			q.poll();
    		}
    		
    		
    		
    	}
    	/* 앞이 크면 0, 뒤가 크면  1 return  */
    	public static int judge(int idx) {
    		//바로 앞이면 
    		if( idx == 1) {
    			return 2;
    		}
    		
    		int front = idx -1 ; // 앞에거 개수 
    		int back =  q.size() - (idx); //뒤에꺼 개수 
    		
    		if ( front > back) {
    			return 0;
    		}
    		else if ( front < back) {
    			return 1;
    		}
    		//같은 경우 
    		return 3;
    		
    	}
    	// 찾고자 하는 값 인덱스 리턴 
    	public static int find(int value) {
    		Iterator e = q.iterator();
    		int idx = 1;
    	       while(e.hasNext()){
    			int val =(e.next());
    			//System.out.print("pop value " +val + " ");
    			if ( val == value ) {
    				return idx;
    			}
    			idx++;
    		}
    		return 0;
    	}
    }
    
    


    '코딩 > 알고리즘' 카테고리의 다른 글

    [백준[자바][13458 시험감독]  (0) 2018.10.13
    [백준][자바][11559 Puyo Puyo]  (0) 2018.10.13
    [백준][자바][2146 다리] 해결못함  (0) 2018.10.07
    [백준][자바][5427 불]  (0) 2018.10.07
    [백준][자바][1063]킹  (0) 2018.10.02

    댓글

Designed by Tistory.