[백준] 단계별로 풀어보기(단계:22,우선순위 큐,JAVA)1655번, 가운데를 말해요

문제 링크

1655번: 가운데를 말해요

---

주의사항

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

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

---

문제 설명

---

접근 방법

우선순위 큐는 일반적인 큐와 조금의 차이점이 존재합니다.

우선순위 큐에 입력될 때마다 우선순위 조건에 따라서 순서가 바뀌어서 poll()값이 우선순위가 가장 높은 것을 나오게 되는 것입니다.

기본적인 우선순위 큐 설정은 숫자 오름차순으로 되어있습니다.

예를들어 우선순위 큐에 1 5 3 7 2를 push() 해보겠습니다.(우선순위는 숫자 오름차순)

1. 숫자 1 push

1

2. 숫자 5 push

1

5

3. 숫자 3 push

1

3

5

4. 숫자 7 push

1

3

5

7

5. 숫자 2 push

1

2

3

5

7

우선순위 큐의 peek() = 1, poll()을 진행하면 1이 나옵니다.

만약 우선순위 조건이 숫자 내림차순이면

7

5

3

2

1

peek() = 7, poll() = 7이 나옵니다.

 

문제에서는 중간값을 구해야하며 짝수일 때에는 중간에 두 수 중에 더 작은 수를 골라야 합니다.

처음에 접근할 때에는 우선순위 큐를 오름차순 조건으로 생성하여 poll(), add()를 사용하여 중간 값을 구해보았지만

시간초과가 발생하였습니다.

고민하다 생각난 것은 이분탐색처럼 중간을 나누어서 관리하는 것이었습니다.

 

나누어 관리하기 위해 두 개의 우선순위 큐를 생성하였으며 중간값 왼쪽에 들어가는 큐는 내림차순

오른쪽에 들어가는 큐는 오름차순으로 설정해주었습니다.

이유는 예시를 들면서 설명하도록 하겠습니다.

예제 입력 1처럼 입력되었을 때 두 개의 우선순위 큐에 대한 표를 보여드리겠습니다.

1. 숫자 1 입력

LeftQueue(내림차순)

1(peek값)

RightQueue(오름차순)

중간값은 LeftQueue에 peek()값 = 1

 

여기서 LeftQueue를 먼저 add하는 이유는 입력값 개수가 짝수일 때 중간의 두 수 중 작은 수를 출력한다는 것은 LeftQueue에 있는 값이 출력한다는 내용이기 때문입니다.

예를 들어 1 3 4 5 로 입력값을 받아서 정렬하였을 때

LeftQueue(내림차순)

3(peek값)

1

RightQueue(오름차순)

4(peek값)

5

LeftQueue에 peek()값이 중간 값이 되기 때문입니다.

입력값이 홀수일 때에도 LeftQueue값을 먼저 추가하였기 때문에 중간값은 LeftQueue에 peek()값이 되는 것입니다.

예를 들어 1 3 4 5 6으로 입력값을 받아서 정렬하였을 때

LeftQueue(내림차순)

4(peek값)

3

1

RightQueue(오름차순)

5(peek값)

6

LeftQueue의 peek()값이 중간값이 됩니다.

만약 짝수일 때 두 수중 큰 값을 출력한다고 문제가 설명한다면 RigthQueue에 먼저 값을 add시키고 결과를 RightQueue의 peek()값이 중간값으로 출력 될 수 있습니다.

2. 숫자 5 입력

LeftQueue(내림차순)

1(peek값)

RightQueue(오름차순)

5(peek값)

중간값은 LeftQueue에 peek()값 = 1

3. 숫자 2 입력

LeftQueue(내림차순)

2(peek값)

1

RightQueue(오름차순)

5(peek값)

중간값은 LeftQueue에 peek()값 = 2

.......마지막 과정

LeftQueue(내림차순)

5(peek값)

2

1

-99

RightQueue(오름차순)

5(peek값)

7

10

중간값은 LeftQueue에 peek()값 = 2

알고리즘을 작성할 때에는 유의할 점이 존재합니다!!

LeftQueue(내림차순)

3(peek값)

2

RightQueue(오름차순)

5(peek값)

7

위와 같은 상황에서 입력이 10이 되었을 때

원래는 먼저 LeftQueue에 add()가 되어야 하지만 입력값 10은 현재까지 들어온 수 중 가장 큰 값입니다.

그래서 10을 LeftQueue에 넣지 않고 RightQueue에 추가하는 대신 RightQueue에서 가장 작은 값(peek값)을 LeftQueue로 이동시켜주는 것입니다.

결과는

LeftQueue(내림차순)

5(peek값)

3

2

RightQueue(오름차순)

7(peek값)

10

위 과정을 알고리즘으로 표현하면

LeftQueue와 RightQueue의 크기가 같을 때 먼저 LeftQueue에 값에 추가해야 하지만 큰 값이 들어올 수 있으므로 입력값이 RightQueue의 peek()값보다 큰 경우에는 RightQueue의 peek값이 LeftQueue값으로 이동하고 입력값은 RightQueue에 저장합니다.

 

마찬가지로 LeftQueue의 크기가 RightQueue보다 크면 RightQueue에 값을 추가해야 하지만 작은 값이 들어올 수 있으므로 입력값이 LeftQueue의 peek()값보다 큰 경우에는 LeftQueue의 peek()값은RightQueue값으로 이동하고 입력값은 LeftQueue에 저장합니다.

코드로 표현한다면

//LeftQueue와 RightQueue 크기가 같아서 LeftQueue의 값이 추가되어야 할 때
if(leftQueue.size()==rightQueue.size()) {
    			if(num>rightQueue.peek()) {
    				int temp = rightQueue.poll();
    				rightQueue.add(num);
    				leftQueue.add(temp);
    			}else
    				leftQueue.add(num);
}

//LeftQueue크기가 RightQueue보다 커서 RightQueue의 값이 추가되어야 할 때
if(leftQueue.size>RightQueue.size){ 
    			if(num<leftQueue.peek()) {
    				int temp = leftQueue.poll();
    				leftQueue.add(num);
    				rightQueue.add(temp);
    			}else
    				rightQueue.add(num);
}

 

문제를 해결한 알고리즘의 과정입니다.

1. 우선순위 큐를 2개를 선언해줍니다.(LeftQueue는 내림차순, RightQueue는 오름차순)

2. 입력값을 두 개의 큐의 크기에 따라서 값을 저장합니다.(위에 알고리즘 참조)

3. 입력값이 저장되고 난 뒤에 LeftQueue에 peek값을 결과에 저장합니다.

4. 모든 입력값을 저장한 뒤에 지금까지 저장된 peek값을 모두 출력합니다.

 

※내림차순 조건을 사용할 때에는 Collections.reverseOrder를 사용하면 됩니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• 우선순위 큐 LeftQueue(내림차순), RightQueue(오름차순)으로 선언해주었습니다.
• 위 알고리즘에 조건대로 우선순위 큐에 입력값을 저장하였습니다.
• BufferedWriter에 입력될 때마다 해당 범위의 중간값(LeftQueue.peek())을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	//Left(내림차순),Right(오름차순) 우선순위 큐 작성
	private static PriorityQueue<Integer> rightQueue = new PriorityQueue<Integer>();
	private static PriorityQueue<Integer> leftQueue = 
    				new PriorityQueue<Integer>(Collections.reverseOrder());
    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
        //-------입력값 저장 및 큐의 저장-------
    	int N = Integer.parseInt(br.readLine());
    	for(int i=0;i<N;i++) {
    		int num = Integer.parseInt(br.readLine());
    		if(leftQueue.size()==0) 	//첫 숫자일 때
    			leftQueue.add(num);
       		//Left,Right 큐의 크기가 같을 때
    		else if(leftQueue.size()==rightQueue.size()) {
            		//입력값 RightQueue의 Peek보다 클 경우
    			if(num>rightQueue.peek()) {		
    				int temp = rightQueue.poll();
    				rightQueue.add(num);
    				leftQueue.add(temp);
    			}else
    				leftQueue.add(num);
    		}else {
            		//입력값 LeftQueue의 Peek보다 작을 경우
    			if(num<leftQueue.peek()) {
    				int temp = leftQueue.poll();
    				leftQueue.add(num);
    				rightQueue.add(temp);
    			}else
    				rightQueue.add(num);
    		}
    		bw.write(leftQueue.peek() + "\n");		//중간값 BufferedWriter에 저장
    	}
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    	
    }
}