[BOJ/Java] 16435. 스네이크버드

[BOJ/Java] 16435. 스네이크버드

16435번: 스네이크버드

---

문제 해석

이 문제에서는 스네이크버드와 여러 개의 과일이 주어지며, 스네이크버드의 길이를 최대로 늘리는 것이 목표이다. 스네이크버드는 자신의 길이 이하 높이의 과일을 먹을 수 있으며, 과일을 먹을 때마다 길이가 1 증가한다. 과일의 위치(높이)는 무작위로 주어진다.

풀이 과정

• io 메소드에서 입력을 받아 과일의 높이를 우선순위 큐에 저장한다. 이를 통해 가장 낮은 과일부터 접근할 수 있다.
• sol 메소드에서는 우선순위 큐를 사용하여 스네이크버드가 먹을 수 있는 가장 낮은 과일부터 시작하여 스네이크버드의 길이를 증가시킨다. 스네이크버드의 길이보다 높은 과일을 만나면 반복을 종료한다.

코드

package edu.ssafy.im.BOJ.Silver.S5.No16435;

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

public class Main {
	private Queue<Integer> pq; // 과일의 높이를 저장할 우선순위 큐
	int l; // 스네이크버드의 초기 길이

	public static void main(String[] args) throws IOException {
		new Main().io();
	}

	private void io() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()); // 과일의 개수
		l = Integer.parseInt(st.nextToken()); // 스네이크버드의 초기 길이
		pq = new PriorityQueue<Integer>(); // 과일 높이를 저장할 우선순위 큐 초기화
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			pq.offer(Integer.parseInt(st.nextToken())); // 과일 높이를 큐에 추가
		}
		sb.append(sol()); // 문제 해결 메소드 호출
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	private int sol() {
		while (!pq.isEmpty()) {
			if (l >= pq.peek()) { // 스네이크버드의 길이가 큐의 가장 낮은 과일 높이보다 크거나 같다면
				l++; // 스네이크버드의 길이 증가
				pq.poll(); // 과일을 먹고 제거
			} else {
				break; // 먹을 수 없는 과일을 만나면 반복 종료
			}
		}

		return l; // 최종 스네이크버드의 길이 반환
	}
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(nlogn)이다. 여기서 n은 과일의 개수이다. 과일의 높이를 우선순위 큐에 저장하는 과정이 O(nlogn)이며, 모든 과일을 확인하고 먹는 과정 역시 O(nlogn)이다.

느낀점

이 문제는 우선순위 큐를 활용하여 주어진 조건에 맞게 효율적으로 문제를 해결할 수 있었다. 스네이크버드가 먹을 수 있는 과일을 순서대로 접근하면서 문제의 요구사항을 만족시킬 수 있었다.