[백준] 1655번 : 가운데를 말해요 - 자바(JAVA)

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

1655번: 가운데를 말해요

 

문제 해석

Boj(백준이)가 정수를 하나씩 외칠 때마다 Brother(동생)이 지금까지 말한 수 중에서 중간값을 말해야 한다.
만약 Boj가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중 작은 수를 말한다.

---

입력

첫째 줄에는 백준이가 외치는 정수의 개수 N

그다음 N 줄에 걸쳐 백준이가 외치는 정수가 차례대로 주어진다.

 

제약조건

1<= 자연수 N <= 100,000

-10,000 <= 외치는 정수 <= 10,000

---

출력

한 줄에 하나씩 N 줄에 걸쳐 동생이 말해야 하는 수를 출력한다.

---

문제 풀이 전 설계

입력값 받기

백준이가 외치는 정수의 개수 N을 입력받고 N번 반복하여 외치는 정수에 대해 입력받는다.

 

핵심 기능

백준이가 말하는 수를 입력받고 이를 정렬한다.

이후에 동생은 반복문을 순회하며 middle = Size/2 부분을 출력한다.

---

풀이하면서 고민해본 점

 

입력은 어떻게 받는것이 효율적인가( Scanner vs BufferedReader)

https://junuuu.tistory.com/7?category=968252 

[Java] Scanner 와 BufferedReader의 차이점

출력은 어떻게 하는것이 효율적인가 ( System.out.println vs BufferedWriter) (String vs StringBuilder)

https://blog.naver.com/scyawer/222072629287

자바)System.out.println vs. BufferedReader

https://junuuu.tistory.com/10

[Java ] String, Stringbuffer, Stringbuilder의 차이 및 장단점(+속도 비교)

 

 

Boj 클래스와 Brother 클래스를 만들어 구현해보고자 했다.

Boj 클래스에서는 입력을 받는다.

Brother 클래스에서는 입력값을 받아 어떤 값을 말해야 할지 계산한다.

 

이 과정속에서

반복문을 순회하면서 ArrayList <Integer> 배열을 사용하고 Collections.sort()를 사용하여 정렬하였다.

 

핵심 로직은 아래와 같습니다

List<Integer> numList = new ArrayList<Integer>();

for (int i = 0; i < numArray.length; i++) {
	for (int j = 0; j <= i; j++) {
		numList.add(numArray[j]);
	}
    	Collections.sort(numList);
    	int numSize = numList.size();
    	int middle = numSize / 2;
    	if (isOdd(numSize)) {
        	resultList.add(numList.get(middle));
    	} else {
        	resultList.add(numList.get(middle - 1));
    	}

    	numList.clear();
}

numArray는 인자로 받아온 int [] 타입입니다.

첫 번째 for문을 통해 내부 for문의 반복을 점진적으로 증가시킵니다.

내부 for문은 ArrayList인 numList에 값을 추가합니다.

이후에 Collections.sort(numList)를 통해 numList를 정렬합니다.

그렇게 되면 동생이 말해야 하는 중간값은 자연스럽게 ArrayList의 중간 index에 존재하게 됩니다.

반복을 위해 numList.clear()를 통해 numList를 비웁니다.

 

하지만 위와 같이 구현했을 때 출력 값을 올바르게 나오나 메모리 초과가 발생합니다!

 

어떻게 풀어야 할까 고민하다가 도저히 모르겠어 다른 분들의 풀이를 보았습니다.

풀이법은 2개의 우선순위 큐를 사용하는 것이었습니다.

우선순위 큐는 먼저 들어온 값이 먼저 나가는 일반적인 큐와는 다르게 우선순위가 가장 높은 값이 먼저 나갑니다.

 

최소 우선순위 큐와 최대 우선순위 큐를 사용하여 두 큐의 원소의 개수를 균형을 이루도록 하여 최대 우선순위 큐의 루트 값이 항상 중앙값을 가리키도록 합니다.

최소 우선순위 큐는 값이 작을수록 우선순위를 가지고 최대 우선순위 큐는 값이 클수록 우선순위를 갖습니다.

 

1. 최대 우선순위 큐와 최소 우선순위 큐의 크기가 같다면 최대 우선순위 큐에 숫자를 입력한다. 

2. 만약 크기가 같지 않다면 최소 우선순위 큐에 숫자를 입력합니다.

3. 최대/최소 우선순위 큐가 비어있지 않고, 최대 큐의 루트 값이 더 크다면 최소 큐의 루트 값과 자리를 바꾸어 줍니다.

4. 최대 우선순위 큐의 루트 값을 출력합니다.

 

◆  위와 같은 작업을 하게 되면 아래와 같이 값이 저장됩니다. (왼쪽[] -> maxHeap, 오른쪽[] -> minHeap)

 

 1 입력 ▶ [1] [ ]  → 1 출력

 5 입력 ▶ [1] [5]   → 1 출력

 2 입력 ▶ [1 2] [5]  → 2 출력

10 입력 ▶ [1 2] [5 10]  → 2 출력

-99 입력 ▶ [-99 1 2] [5 10]  → 2 출력

 7 입력 ▶ [-99 1 2] [5 7 10]  → 2 출력

 5 입력 ▶ [-99 1 2 5] [5 7 10]  → 5 출력

 

◆  문제에서 주어진 입력 값으로는 정확히 어떻게 변하는지 쉽게 파악하기 어렵습니다.

◆  10 8 5 3 5 -1을 입력받았다고 생각해보겠습니다.

 

10 입력 ▶ [10] [ ]  → 10 출력

 8 입력 ▶ [8] [10]   → 8 출력  ※ minHeap에 8 이 들어간 뒤 10과 swap 된 결과

 5 입력 ▶ [5 8] [10]  → 8 출력

 3 입력 ▶ [3 5] [8 10]  → 5 출력  ※ minHeap에 3 이 들어간 뒤 8과 swap 된 결과

 5 입력 ▶ [3 5 5] [8 10]  → 5 출력

 -1 입력 ▶ [-1 3 5] [5 8 10]  → 5 출력 ※ minHeap에 -1 이 들어간 뒤 5과 swap된 결과

---

어려웠던 점

구현이 끝났으나 메모리 초과가 발생하였습니다.

우선순위 큐에 대해 잘 몰랐기 때문에 문제 해결이 힘들었다.

---

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.util.PriorityQueue;

/*
 * BOJ 1655번 문제 : 가운데를 말해요
 * Boj(백준이)가 정수를 하나씩 외칠때마다 Brother(동생)이 지금까지 말한 수 중에서 중간값을 말해야 한다.
 * 만약 Boj가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중 작은 수를 말한다.
 */

class Boj {

	int[] sayNumbers() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String strNum = br.readLine();
		int num = Integer.parseInt(strNum);
		int[] numArray = new int[num];
		Brother bro = new Brother();
		
		for (int i = 0; i < numArray.length; i++) {
			strNum = br.readLine();
			num = Integer.parseInt(strNum);								
			bro.inputToPQ(num);
			numArray[i] = bro.sayNumber();

		}
		br.close();
		return numArray;
	}
}

class Brother {
	private PriorityQueue<Integer> minPQ = new PriorityQueue<>();
	private PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Collections.reverseOrder());

	int sayNumber() {
		return maxPQ.peek();
	}

	void inputToPQ(int num) {
		if (isSizeSame(minPQ, maxPQ)) {
			maxPQ.offer(num);
		} else {
			minPQ.offer(num);
		}

		if (isBothNotEmpty(minPQ, maxPQ)) {
			if (isNeedSwap(minPQ, maxPQ)) {
				swap(minPQ, maxPQ);
			}
		}
	}

	boolean isSizeSame(PriorityQueue<Integer> minPQ, PriorityQueue<Integer> maxPQ) {
		if (minPQ.size() == maxPQ.size()) {
			return true;
		} else {
			return false;
		}
	}

	boolean isBothNotEmpty(PriorityQueue<Integer> minPQ, PriorityQueue<Integer> maxPQ) {
		if (!minPQ.isEmpty() && !maxPQ.isEmpty()) {
			return true;
		} else {
			return false;
		}
	}

	boolean isNeedSwap(PriorityQueue<Integer> minPQ, PriorityQueue<Integer> maxPQ) {
		if (minPQ.peek() < maxPQ.peek()) {
			return true;
		} else {
			return false;
		}
	}

	void swap(PriorityQueue<Integer> minPQ, PriorityQueue<Integer> maxPQ) {
		int temp = minPQ.poll();
		minPQ.offer(maxPQ.poll());
		maxPQ.offer(temp);
	}

}

public class SayMiddle {

	static int[] numArray;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		inputNumberInfo();
		printNumberInfo();
	}

	static void inputNumberInfo() throws IOException {
		Boj boj = new Boj();
		numArray = boj.sayNumbers();
	}

	static void inputNumberInfoTest() {
		for (int num : numArray) {
			System.out.print(num + " ");
		}
		System.out.println("");
	}

	static void printNumberInfo() throws IOException {

		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder stringBuilder = new StringBuilder();

		for (int i = 0; i < numArray.length; i++) {
			stringBuilder.append(numArray[i]);
			stringBuilder.append("\n");
		}

		bw.write(stringBuilder.toString());
		bw.flush();
		bw.close();

	}

}

Boj 클래스와 Brother 클래스를 사용하여 문제를 풀이하였습니다.

핵심기능을 최대한 함수화하여 가독성을 높이고자 했습니다.

 

 

출처

https://dragon-h.tistory.com/6

[백준 1655 : JAVA] 가운데를 말해요 / PriorityQueue

https://gh402.tistory.com/32

[백준] 1655번 가운데를 말해요 문제풀이 feat.자바 JAVA