[백준] 단계별로 풀어보기(단계:19,큐/덱,JAVA)1021번, 회전하는 큐

문제 링크

1021번: 회전하는 큐

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

기본적으로 덱은 큐(FIFO), 스택(LIFO)처럼 나오는 순서가 한 곳으로 한정된 것이 아닌 양방향에서 출력할 수 있는 자료구조입니다. 그래서 스택으로 사용할 수도 있고 큐로 사용할 수 있는 자료구조입니다.

예를 들어 3, 2, 1을 순서대로 덱에 저장한 뒤 하나씩 꺼내보겠습니다.

1. 3을 덱에 넣었을 때

3

2. 2을 덱에 넣었을 때

3

2

3. 1을 덱에 넣었을 때

3

2

1

4. 덱에서는 자료를 출력할 때 First인지 Last인지 정할 수 있습니다.

First인 경우

3

2

1

Last인 경우

3

2

1

5. 결과

First인 경우

2

1

Last인 경우

3

2

위에 표를 보면서 덱은 First와 Last를 구분하여 저장 및 출력할 수 있습니다.

Java에서 덱를 표현하려면 ArrayDeque<>()로 선언해주어야 하므로 덱을 선언해주었습니다.

문제에서 연산의 최소값을 구하려면 왼쪽에서 검색하는 횟수와 오른쪽에서 검색하는 횟수를 비교한 뒤에 더 작은 값을 통해 데크에 연산 후 입력값에서 찾는 값을 poll()하는 방식을 반복하는 방식으로 알고리즘을 설계해야 합니다.

1. 주 데크를 초기화 및 입력값들을 저장합니다.

2. 주 데크에서 오른쪽 검색/왼쪽 검색할 때 수행하는 연산의 횟수를 구합니다.

3. 연산 횟수를 비교하여 적은 연산을 수행합니다.

4. 그 이후 입력값에서 찾는 값을 poll()하여 주 데크에서 제거합니다.

5. 위 과정을 반복하여 입력값에 해당하는 값들을 모두 poll()하고 지금까지 연산한 횟수를 모두 더하여 결과로 출력합니다.

예제 입력 2번째 항목을 살펴보자면

N = 10, M = 3

찾는값 = 2 9 5

주 데크 초기화 = 12345678910

처음 찾는 값 : 2왼쪽 검색시 : 23456789101 -> 연산횟수 1번

오른쪽 검색시 : 23456789101 -> 연산횟수 9번

왼쪽 검색시 더 적으므로 왼쪽 연산을 수행합니다.

그 이후에 주 데크 맨 앞에 있는 1을 poll()을 진행하고 연산횟수 1번을 결과에 더합니다.

이 과정을 9 5도 반복합니다.

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해서 입력값을 띄어쓰기 기준으로 나누었습니다.
• for문을 통해서 주 데크를 초기화하였습니다.
• 연산 횟수와 연산을 진행하는 leftpoll/rightpoll/poll 함수를 만들었습니다.
• 모든 연산이 끝난 후 연산횟수를 다 더한 값을 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값 출력하였습니다.

• leftpoll 함수는 주 데크와 임시 데크를 이용하여 값들을 이동시키며 왼쪽부터 검색하는 연산 횟수를 구하였습니다.
• rightpoll 함수는 주 데크와 임시 데크를 이용하여 값들을 이동시키며 오른쪽부터 검색하는 연산 횟수를 구하였습니다.
• poll 함수는 왼쪽/오른쪽 연산횟수를 비교하고 더 작은 연산횟수에 값에 대하여 연산을 진행하고 입력된 값과 동일한 값을 poll을 진행한 뒤에 연산횟수를 반환하도록 하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static Deque<Integer> deque = new ArrayDeque<>();	//주 데크
	static Deque<Integer> temp = new ArrayDeque<>();	//임시 데크
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //출력값 처리하는 BufferedWriter
        //---------입력값 저장 및 주 데크 초기화---------
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int result = 0;
        for(int i=1;i<=N;i++)
        	deque.offer(i);
        
        st = new StringTokenizer(br.readLine(), " ");
        //---------함수 실행------------
        for(int i=0;i<M;i++) {
        	int findNum = Integer.parseInt(st.nextToken());
        	int leftNum = leftpoll(findNum);
        	int rightNum = rightpoll(findNum);
        	result += poll(leftNum,rightNum);
        }
        bw.write(result + "\n");	//결과 BufferedWriter에 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //----------최소값을 이용한 데크 결과 뽑기--------
    public static int poll(int left, int right) {
    	if(left<=right) {	//left가 작을 경우
    		for(int i=0;i<left;i++) {
    			deque.offerLast(deque.pollFirst());
    		}
    		deque.pollFirst();
    		return left;
    	}else {			//right가 작을 경우
    		for(int i=0;i<right;i++) {
    			deque.offerFirst(deque.pollLast());
    		}
    		deque.pollFirst();	//데크 뽑아내기
    		return right;	//연산 횟수 반환
    	}
    }
    //-----------left로 검색시 연산 횟수 찾는 함수-----------
    public static int leftpoll(int findNum) {
    	int result = 0;
    	int size = deque.size();
    	for(int i=0;i<size;i++) {
    		int n = deque.pollFirst();
    		temp.offerFirst(n);
    		if(n==findNum)
    			break;
    		result++;
    	}
    	for(int i=0;i<result+1;i++) {
    		int n = temp.pollFirst();
    		deque.offerFirst(n);
    	}
    	return result;
    }
    //-----------right로 검색시 연산 횟수 찾는 함수-----------
    public static int rightpoll(int findNum) {
    	int result = 1;
    	int size = deque.size();
    	for(int i=0;i<size;i++) {
    		int n = deque.pollLast();
    		temp.offerFirst(n);
    		if(n==findNum)
    			break;
    		result++;
    	}
    	for(int i=0;i<result;i++) {
    		int n = temp.pollFirst();
    		deque.offerLast(n);
    	}
    	return result;
    }
}