99클럽 코테 스터디 19일차 TIL

비기너

문제

1927번: 최소 힙

# 우선순위 큐

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

풀이

우선순위 큐를 이용하여 최소 힙을 구현하는 문제이다.

코드

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> pq = new PriorityQueue<>();

		while (n-- > 0) {
			int x = Integer.parseInt(br.readLine());
			if (x == 0) {
				if (pq.isEmpty())
					bw.write("0\n");
				else
					bw.write(pq.poll() + "\n");
			} else
				pq.add(x);
		}
		bw.flush();
		bw.close();
	}
}

미들러

문제

1374번: 강의실

# 그리디 # 우선순위 큐

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

풀이

강의의 시작 시간과 종료 시간이 주어질 때 필요한 강의실의 개수를 구하는 문제이다.

우선 n개의 강의 사간을 2차원 배열로 관리한다.

해당 배열을 강의 시작 시간을 기준으로 오름차순 정렬한다.

배열을 순회하면서 강의실을 배정한다.

우선순위 큐를 사용해서 강의 종료 시간을 관리하여 새 강의 정보가 주어졌을 때 강의실을 새로 배정해야 하는지를 체크한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		int[][] a = new int[n][2];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			st.nextToken();
			a[i][0] = Integer.parseInt(st.nextToken());
			a[i][1] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(a, (o1, o2) -> o1[0] - o2[0]);

		PriorityQueue<Integer> pq = new PriorityQueue<>();
		int ans = 0;
		for (int[] i : a) {
			if (pq.isEmpty() || pq.peek() > i[0]) {
				pq.add(i[1]);
				ans++;
			} else {
				pq.poll();
				pq.add(i[1]);
			}
		}

		bw.write(ans + "");
		bw.flush();
		bw.close();
	}
}

챌린저

문제

1022번: 소용돌이 예쁘게 출력하기

# 구현

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

풀이

정수로 구성된 소용돌이에서 일부분을 출력하는 문제이다.

전체 소용돌이를 저장하려면 10000 * 10000 배열이 필요하므로 전체 소용돌이를 저장하면 메모리 초과가 발생한다.

출력해야되는 영역이 주어지면 해당 영역의 소용돌이만 저장한다.

그 뒤에 출력형식을 맞춰주기 위해 가장 길이가 긴 정수의 길이를 구하고 그것보다 길이가 작은 정수에 대해 공백을 추가하여 출력한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int[] dy = { 0, -1, 0, 1 };
	static int[] dx = { 1, 0, -1, 0 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int r1 = Integer.parseInt(st.nextToken());
		int c1 = Integer.parseInt(st.nextToken());
		int r2 = Integer.parseInt(st.nextToken());
		int c2 = Integer.parseInt(st.nextToken());
		int[][] a = new int[r2 - r1 + 1][c2 - c1 + 1];

		int n = 1, cnt = 0, tmp = 1, d = 0, y = 0, x = 0, mx = 0;
		while (true) {
			if (a[0][0] != 0 && a[r2 - r1][0] != 0 && a[0][c2 - c1] != 0 && a[r2 - r1][c2 - c1] != 0)
				break;
			if (y >= r1 && x >= c1 && y <= r2 && x <= c2) {
				a[y - r1][x - c1] = n;
				mx = Math.max(mx, n);
			}

			n++;
			cnt++;
			y = y + dy[d];
			x = x + dx[d];

			if (cnt == tmp) {
				cnt = 0;
				if (d == 1 || d == 3)
					tmp++;
				d = (d + 1) % 4;
			}
		}

		int mx_len = (int) (Math.log10(mx) + 1);
		for (int i = r1; i <= r2; i++) {
			for (int j = c1; j <= c2; j++) {
				int l = (int) (Math.log10(a[i - r1][j - c1]) + 1);
				for (int k = 0; k < mx_len - l; k++)
					bw.write(" ");
				bw.write(a[i - r1][j - c1] + " ");
			}
			bw.write("\n");
		}
		bw.flush();
		bw.close();
	}
}