공부 기록

일단 아이디어 자체는 왼쪽에서 포함되는 점의 위치 leftIndex와 오른쪽에서 포함되는 점의 위치 rightIndex를 각각 구한 뒤,

rightIndex - leftIndex + 1 을 하여 구해 보자는 생각이었다.

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));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int points = Integer.parseInt(st.nextToken());
		int lines = Integer.parseInt(st.nextToken());

		int point[] = new int[points];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < points; i++) {
			point[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(point);

		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		for (int i = 0; i < lines; i++) {
			st = new StringTokenizer(br.readLine());
			int left = Integer.parseInt(st.nextToken());
			int right = Integer.parseInt(st.nextToken());

			int rightIndex = getRightIndex(right, points - 1, point);
			int leftIndex = getLeftIndex(left, points - 1, point);
			// System.out.println(leftIndex + " " + rightIndex);
			int sum = rightIndex - leftIndex + 1;
			sum = Math.max(0, sum);
			bw.write(sum + "\n");
		}
		bw.flush();
		br.close();
	}

	private static int getLeftIndex(int target, int length, int[] point) {
		int start = 0;
		int end = length;
		int answer = end;

		while (start <= end) {
			int mid = (start + end) / 2;

			if (target < point[mid]) {
				answer = Math.min(answer, mid);
				end = mid - 1;
			} else if (target == point[mid]) {
				return mid;
			} else {
				start = mid + 1;
			}
		}
		return answer;
	}

	private static int getRightIndex(int target, int length, int[] point) {
		int start = 0;
		int end = length;
		int answer = 0;

		while (start <= end) {
			int mid = (start + end) / 2;

			if (point[mid] < target) {
				answer = Math.max(answer, mid);
				start = mid + 1;
			} else if (point[mid] == target) {
				return mid;
			} else {
				end = mid - 1;
			}
		}
		return answer;
	}
}

하지만, 0이나 40과 같이 범위를 벗어나는 선분인 경우 따로 처리가 필요했다.

(예를 들어 선분 40 40 의 경우 기존 코드에서는 범위에 벗어난 선분이지만 점 1개를 리턴하고 있었다.)

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));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int points = Integer.parseInt(st.nextToken());
		int lines = Integer.parseInt(st.nextToken());

		int point[] = new int[points];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < points; i++) {
			point[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(point);

		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		for (int i = 0; i < lines; i++) {
			st = new StringTokenizer(br.readLine());
			int left = Integer.parseInt(st.nextToken());
			int right = Integer.parseInt(st.nextToken());

			int rightIndex = getRightIndex(right, points - 1, point);
			int leftIndex = getLeftIndex(left, points - 1, point);
			// System.out.println(leftIndex + " " + rightIndex);
			int sum = calcPoints(leftIndex, rightIndex, points);
			bw.write(sum + "\n");
		}
		bw.flush();
		br.close();
	}

	private static int calcPoints(int leftIndex, int rightIndex, int length) {
		if (rightIndex < 0 && leftIndex < 0) {
			return 0;
		}

		if (rightIndex >= length && leftIndex >= length) {
			return 0;
		}

		if (leftIndex < 0 && rightIndex >= length) {
			return length;
		}

		if (leftIndex < 0) {
			return rightIndex + 1;
		}

		if (rightIndex >= length) {
			return length - leftIndex;
		}

		return rightIndex - leftIndex + 1;
	}

	private static int getLeftIndex(int target, int length, int[] point) {
		int start = 0;
		int end = length;
		int answer = end;

		if (target < point[0]) {
			return -1;
		}
		if (point[end] < target) {
			return end + 1;
		}

		while (start <= end) {
			int mid = (start + end) / 2;

			if (target < point[mid]) {
				answer = Math.min(answer, mid);
				end = mid - 1;
			} else if (target == point[mid]) {
				return mid;
			} else {
				start = mid + 1;
			}
		}
		return answer;
	}

	private static int getRightIndex(int target, int length, int[] point) {
		int start = 0;
		int end = length;
		int answer = 0;

		if (target < point[0]) {
			return -1;
		}
		if (point[end] < target) {
			return end + 1;
		}

		while (start <= end) {
			int mid = (start + end) / 2;

			if (point[mid] < target) {
				answer = Math.max(answer, mid);
				start = mid + 1;
			} else if (point[mid] == target) {
				return mid;
			} else {
				end = mid - 1;
			}
		}

		return answer;
	}
}

이렇게 귀찮아질 바에는 반대로 생각하면 조금 더 쉬워진다. 지금은 포함되는 점의 시작점, 끝점을 구했지만

포함되지 않는 부분의 점들을 구하게 된다면 풀이는 조금 더 간단해 질 수 있음..

1~n 까지 합 n(n+1)/2 <= S 의 방정식을 풀면 된다.

이 방정식을 풀면 n^2+n-2S<=0 이고, 방정식의 해를 구하면 n이 (-1+√ (1+8s))/2 와 (-1-√ (1+8s))/2 사이에 있으면 되고, 그 중에 큰 값이므로 (-1+√ (1+8s))/2을 버림하여 구하면 된다. 풀이는 아래와 같다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		long s = in.nextLong();
		long n = (long) ((-1 + Math.sqrt(1 + 8 * s)) / 2);

		System.out.println(n);

	}
}

근데 문제 조건에 이분탐색으로 풀라는 이야기가 있었기 때문에.. 이분탐색으로 풀어보자면

n(n+1)/2를 s와 비교하여 아래와 같이 이분탐색으로 풀 수도 있다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		long s = in.nextLong();
		long end = s;
		long start = 0;
		long answer = 0;

		while (start <= end) {
			long mid = (start + end) / 2;
			long sum = sum(mid);

			if (sum <= s) {
				answer = Math.max(answer, mid);
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}

		System.out.println(answer);
	}

	private static long sum(long n) {
		return n * (n + 1) / 2;
	}
}

2021/01/15 - [알고리즘 공부/boj] - boj 3745: 오름세

위 문제와 동일하다. 지난번에 푼 기억이 있어서 비교적 수월하게 풀었다.

세그먼트 트리로도 한번 구현해 봐야하는데 언제하지...

class Solution {
	public int lengthOfLIS(int[] nums) {
		int n = nums.length;
		int[] lis = new int[n];

		lis[0] = nums[0];
		int lastIndex = 0;

		for (int i = 1; i < n; i++) {
			if (lis[lastIndex] < nums[i]) {
				lastIndex++;
				lis[lastIndex] = nums[i];
			} else {
				int index = findIndex(lis, nums[i], lastIndex);
				lis[index] = nums[i];
			}
		}
		return lastIndex + 1;
	}

	public static int findIndex(int[] lis, int target, int right) {
		int left = 0;

		while (left < right) {
			int mid = (left + right) / 2;
			if (lis[mid] == target) {
				return mid;
			}

			if (lis[mid] > target) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}

		return right;
	}
}

칸의 높이차가 height 보다 큰 경우 사다리를 설치해야 하는데, 사다리 설치 비용은 두 칸의 높이차이다.

최대한 적은 비용이 들도록 사다리를 설치해서 모든 칸을 방문 하도록 하는 문제이다.

역시나 사다리를 설치하는 모든 경우를 구하게 되면 시간초과가 날 것이므로 다른 방법을 사용해야 한다.

맨 처음에 든 생각은 사다리 설치 비용을 이분탐색으로 구해두고 모든 칸을 방문 가능한지 보면 되지 않나?였다.

하지만 이 경우 사다리 설치 비용을 구한다고 하더라도 사다리의 위치, 갯수 등을 정하는 것이 쉽지 않겠다는 생각이 들었다.

일단 문제에서 제공하는 예시를 보도록 하자.

예시 그림에서는 일단 구역 컬러링 하고 사다리를 최소한으로 배치했다.

따라서 예시 그림과 마찬가지로 가장 먼저 할 일은 bfs를 돌면서 사다리를 사용하지 않고 갈 수 있는 구역을 먼저 나누는 것이다. 

그 다음으로는 구역 간을 잇는 사다리를 한개씩 배치해 주면 된다.

사다리를 배치해 줄 때에는 인접한 위치 중에서,

구역간의 차이가 최소가 되는 한 개의 사다리를 골라야 한다.

즉, 위 문제는 구역을 나눈후 아래와 같이 최단 거리 문제로 변하게 된다.

import java.util.*;
class Solution {
	public static int dr[] = { 0, 0, 1, -1 };
	public static int dc[] = { 1, -1, 0, 0 };

	public int solution(int[][] land, int height) {
		int length = land.length;
		int[][] colored = new int[length][length];

		int color = 1;
		for (int i = 0; i < length; i++) {
			for (int j = 0; j < length; j++) {
				if (colored[i][j] == 0) {
					colorLand(color++, colored, i, j, length, height, land);
				}
			}
		}

		int mat[][] = new int[color][color];
		HashSet<Integer> connections[] = new HashSet[color + 1];
		for (int i = 0; i < color; i++) {
			Arrays.fill(mat[i], Integer.MAX_VALUE);
			connections[i + 1] = new HashSet<Integer>();
		}

		minLadder(mat, colored, land, connections);

		return prim(mat, color, connections);
	}

	private int prim(int[][] mat, int length, HashSet<Integer> connections[]) {
		int sum = 0;

		PriorityQueue<Node> queue = new PriorityQueue<Node>();
		boolean[] isVisited = new boolean[length];

		queue.add(new Node(1, 0));

		while (!queue.isEmpty()) {
			Node node = queue.poll();

			if (!isVisited[node.name]) {
				isVisited[node.name] = true;
				sum += node.value;

				for (int next : connections[node.name]) {
					queue.add(new Node(next, mat[node.name][next]));
				}
			}
		}

		return sum;
	}

	private void minLadder(int mat[][], int colored[][], int land[][], HashSet<Integer> connections[]) {
		int length = colored.length;

		for (int i = 0; i < length; i++) {
			for (int j = 0; j < length; j++) {
				for (int dir = 0; dir < 4; dir++) {
					int newRow = i + dr[dir];
					int newCol = j + dc[dir];

					if (isBoundary(newRow, newCol, length) && colored[i][j] != colored[newRow][newCol]) {
						int v1 = colored[i][j];
						int v2 = colored[newRow][newCol];
						int diff = Math.abs(land[i][j] - land[newRow][newCol]);

						mat[v1][v2] = Math.min(mat[v1][v2], diff);
						mat[v2][v1] = Math.min(mat[v2][v1], diff);

						connections[v1].add(v2);
						connections[v2].add(v1);
					}
				}
			}
		}
	}

	private void colorLand(int color, int colored[][], int row, int col, int length, int height, int land[][]) {
		colored[row][col] = color;

		Queue<Position> queue = new LinkedList<Position>();
		queue.add(new Position(row, col));

		while (!queue.isEmpty()) {
			Position position = queue.poll();
			colored[position.row][position.col] = color;

			for (int i = 0; i < 4; i++) {
				int newRow = position.row + dr[i];
				int newCol = position.col + dc[i];

				if (isBoundary(newRow, newCol, length) && colored[newRow][newCol] == 0 && Math.abs(land[position.row][position.col] - land[newRow][newCol]) <= height) {
					queue.add(new Position(newRow, newCol));
				}
			}
		}
	}

	private static boolean isBoundary(int row, int col, int length) {
		if (row < 0 || col < 0) {
			return false;
		}
		if (row >= length || col >= length) {
			return false;
		}
		return true;
	}
}

class Position {
	int row;
	int col;

	public Position(int row, int col) {
		this.row = row;
		this.col = col;
	}

	@Override
	public String toString() {
		return "(" + row + ", " + col + ")";
	}
}

class Node implements Comparable<Node> {
	int name;
	int value;

	public Node(int name, int value) {
		this.name = name;
		this.value = value;
	}

	@Override
	public int compareTo(Node o) {
		return Integer.compare(this.value, o.value);
	}
}

정확성: 70.0

합계: 70.0 / 100.0

시간초과 & 메모리 초과 발생 -> prim말고 kruskal을 사용하도록 해보자.

kruskal은 좀 더 뭐랄까... 띄엄띄엄 이어져있는 그래프에서 유리하다고 한다.

import java.util.*;
class Solution {
	public static int dr[] = { 0, 0, 1, -1 };
	public static int dc[] = { 1, -1, 0, 0 };

	public int solution(int[][] land, int height) {
		int length = land.length;
		int[][] colored = new int[length][length];

		int color = 1;
		for (int i = 0; i < length; i++) {
			for (int j = 0; j < length; j++) {
				if (colored[i][j] == 0) {
					colorLand(color++, colored, i, j, length, height, land);
				}
			}
		}

		PriorityQueue<Edge> queue = minLadderList(colored, land);

		return kruskal(queue, color);
	}

	private int kruskal(PriorityQueue<Edge> pq, int length) {
		int vSet[] = new int[length + 1];

		for (int i = 1; i <= length; i++) {
			vSet[i] = i;
		}

		int answer = 0;
		if (!pq.isEmpty()) {
			Edge firstEdge = pq.poll();
			answer += firstEdge.cost;
			union(firstEdge.v1, firstEdge.v2, vSet);
		}

		while (!isFinished(vSet) && !pq.isEmpty()) {
			Edge minEdge = pq.poll();

			int v1Contains = find(minEdge.v1, vSet);
			int v2Contains = find(minEdge.v2, vSet);

			if (v1Contains != v2Contains) {
				answer += minEdge.cost;
				union(minEdge.v1, minEdge.v2, vSet);
			}
		}
		return answer;
	}

	private PriorityQueue<Edge> minLadderList(int colored[][], int land[][]) {
		PriorityQueue<Edge> queue = new PriorityQueue<>();

		int length = colored.length;

		for (int i = 0; i < length; i++) {
			for (int j = 0; j < length; j++) {
				for (int dir = 0; dir < 4; dir++) {
					int newRow = i + dr[dir];
					int newCol = j + dc[dir];

					if (isBoundary(newRow, newCol, length) && colored[i][j] != colored[newRow][newCol]) {
						int v1 = colored[i][j];
						int v2 = colored[newRow][newCol];
						int diff = Math.abs(land[i][j] - land[newRow][newCol]);

						queue.add(new Edge(v1, v2, diff));
					}
				}
			}
		}
		return queue;
	}

	private void colorLand(int color, int colored[][], int row, int col, int length, int height, int land[][]) {
		colored[row][col] = color;

		Queue<Position> queue = new LinkedList<Position>();
		queue.add(new Position(row, col));

		while (!queue.isEmpty()) {
			Position position = queue.poll();
			colored[position.row][position.col] = color;

			for (int i = 0; i < 4; i++) {
				int newRow = position.row + dr[i];
				int newCol = position.col + dc[i];

				if (isBoundary(newRow, newCol, length) && colored[newRow][newCol] == 0
						&& Math.abs(land[position.row][position.col] - land[newRow][newCol]) <= height) {
					queue.add(new Position(newRow, newCol));
				}
			}
		}
	}

	private static boolean isBoundary(int row, int col, int length) {
		if (row < 0 || col < 0) {
			return false;
		}
		if (row >= length || col >= length) {
			return false;
		}
		return true;
	}

	public static void union(int x, int y, int[] vSet) {
		int ux = find(x, vSet);
		int uy = find(y, vSet);

		vSet[uy] = ux;
	}

	public static int find(int x, int[] vSet) {
		if (vSet[x] == x) {
			return x;
		}

		vSet[x] = find(vSet[x], vSet);
		return vSet[x];
	}

	public static boolean isFinished(int[] vSet) {
		int now = vSet[1];
		for (int i = 1; i < vSet.length; i++) {
			if (vSet[i] != now) {
				return false;
			}
		}
		return true;
	}
}

class Position {
	int row;
	int col;

	public Position(int row, int col) {
		this.row = row;
		this.col = col;
	}

	@Override
	public String toString() {
		return "(" + row + ", " + col + ")";
	}
}

class Edge implements Comparable<Edge> {
	int v1, v2;
	long cost;

	public Edge(int v1, int v2, long cost) {
		this.v1 = v1;
		this.v2 = v2;
		this.cost = cost;
	}

	@Override
	public int compareTo(Edge o) {
		return Long.compare(this.cost, o.cost);
	}
}

정확성: 93.3

합계: 93.3 / 100.0

결과는 메모리 초과는 넘어갔지만,, 테케 24, 25가 시간초과가 났다.

깨달은 점 - bfs를 돌 때는 Queue에 넣어줄 때 visited를 체크해야한다.

그렇지 않으면 중복되어서 들어가는 경우가 생길 수 있고, 그 때문에 시간 초과가 생길 수 있다.

최종 코드

import java.util.*;
class Solution {
	public static int dr[] = { 0, 0, 1, -1 };
	public static int dc[] = { 1, -1, 0, 0 };

	public int solution(int[][] land, int height) {
		int length = land.length;
		int[][] colored = new int[length][length];

		int color = 1;
		for (int i = 0; i < length; i++) {
			for (int j = 0; j < length; j++) {
				if (colored[i][j] == 0) {
					colorLand(color++, colored, i, j, length, height, land);
				}
			}
		}

		PriorityQueue<Edge> queue = minLadderList(colored, land);

		return kruskal(queue, color);
	}

	private int kruskal(PriorityQueue<Edge> pq, int length) {
		int vSet[] = new int[length + 1];

		for (int i = 1; i <= length; i++) {
			vSet[i] = i;
		}

		int answer = 0;
		if (!pq.isEmpty()) {
			Edge firstEdge = pq.poll();
			answer += firstEdge.cost;
			union(firstEdge.v1, firstEdge.v2, vSet);
		}

		while (!isFinished(vSet) && !pq.isEmpty()) {
			Edge minEdge = pq.poll();

			int v1Contains = find(minEdge.v1, vSet);
			int v2Contains = find(minEdge.v2, vSet);

			if (v1Contains != v2Contains) {
				answer += minEdge.cost;
				union(minEdge.v1, minEdge.v2, vSet);
			}
		}
		return answer;
	}

	private PriorityQueue<Edge> minLadderList(int colored[][], int land[][]) {
		PriorityQueue<Edge> queue = new PriorityQueue<>();

		int length = colored.length;

		for (int i = 0; i < length; i++) {
			for (int j = 0; j < length; j++) {
				for (int dir = 0; dir < 4; dir++) {
					int newRow = i + dr[dir];
					int newCol = j + dc[dir];

					if (isBoundary(newRow, newCol, length) && colored[i][j] != colored[newRow][newCol]) {
						int v1 = colored[i][j];
						int v2 = colored[newRow][newCol];
						int diff = Math.abs(land[i][j] - land[newRow][newCol]);

						queue.add(new Edge(v1, v2, diff));
					}
				}
			}
		}
		return queue;
	}

	private void colorLand(int color, int colored[][], int row, int col, int length, int height, int land[][]) {
		colored[row][col] = color;

		Queue<Position> queue = new LinkedList<Position>();
		queue.add(new Position(row, col));

		while (!queue.isEmpty()) {
			Position position = queue.poll();

			for (int i = 0; i < 4; i++) {
				int newRow = position.row + dr[i];
				int newCol = position.col + dc[i];

				if (isBoundary(newRow, newCol, length) && colored[newRow][newCol] == 0
						&& Math.abs(land[position.row][position.col] - land[newRow][newCol]) <= height) {
					colored[newRow][newCol] = color;
					queue.add(new Position(newRow, newCol));
				}
			}
		}
	}

	private static boolean isBoundary(int row, int col, int length) {
		if (row < 0 || col < 0) {
			return false;
		}
		if (row >= length || col >= length) {
			return false;
		}
		return true;
	}

	public static void union(int x, int y, int[] vSet) {
		int ux = find(x, vSet);
		int uy = find(y, vSet);

		vSet[uy] = ux;
	}

	public static int find(int x, int[] vSet) {
		if (vSet[x] == x) {
			return x;
		}

		vSet[x] = find(vSet[x], vSet);
		return vSet[x];
	}

	public static boolean isFinished(int[] vSet) {
		int now = vSet[1];
		for (int i = 1; i < vSet.length; i++) {
			if (vSet[i] != now) {
				return false;
			}
		}
		return true;
	}
}

class Position {
	int row;
	int col;

	public Position(int row, int col) {
		this.row = row;
		this.col = col;
	}

	@Override
	public String toString() {
		return "(" + row + ", " + col + ")";
	}
}

class Edge implements Comparable<Edge> {
	int v1, v2;
	long cost;

	public Edge(int v1, int v2, long cost) {
		this.v1 = v1;
		this.v2 = v2;
		this.cost = cost;
	}

	@Override
	public int compareTo(Edge o) {
		return Long.compare(this.cost, o.cost);
	}
}