1. 문제를 일고 처음에 이해가 되지 않았는데, 예제를 보고선 도킹을 할 때 현재 번호보다 낮은 번호에만 도킹을 할 수 있다는 사실을 알게되었다.
코드
정답 코드 : gate[index] == index 일때만 도킹을 해준다. 도킹을 했을댄 index의 값을 -1해줘서 해당 인덱스에는 다신 도킹할 수 없게 하였다. gate[index] != index 경우에는 해당 게이트보다 낮은 게이트를 재귀로 모두 다 돌아본 다음 도킹 가능한 게이트가 있으면 도킹, index가 0까지 가는 경우 도킹을 종료한다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int G, P;
static int[] gate, airplane;
public static void main(String[] args) throws Exception {
SetData();
System.out.println(FindMaxValue());
}
private static void SetData() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
G = Integer.parseInt(br.readLine());
P = Integer.parseInt(br.readLine());
gate = new int[G + 1];
airplane = new int[P + 1];
for (int i = 1; i <= G; i++)
gate[i] = i;
for (int i = 1; i <= P; i++)
airplane[i] = Integer.parseInt(br.readLine());
}
private static int FindMaxValue() {
int count = 0;
for (int i = 1; i <= P; i++) {
if (docking(airplane[i]) < 0)
break;
count++;
}
return count;
}
private static int docking(int index) {
// basecase (게이트 번호의 값이 0이면 도킹 불가)
if (gate[index] == 0) return -1;
if (gate[index] == index) // 도킹을 아직 시도하지 않은 게이트라면
gate[index]--;
else // 도킹을 한 게이트라면 현재 게이트보다 낮은 게이트를 찾기 위해 재귀를 돔.
gate[index] = docking(gate[index]);
return gate[index];
}
}
1. DFS - 멀티탭의 모든 칸이 꽉 찰때마다 모든 멀티탭의 플러그를 한번씩 빼가며 DFS를 돌림. 정확하지만 시간초과 가능성 높음
2. 멀티탭에 꽂으면서 꽉찼을 때만 뽑을 콘센트를 찾는 작업을 진행함. 콘센트를 빼는 것은 뒤에 가장 적게오는 콘센트를 뽑는다.
코드
정답 코드 : 2번 방법으로 콘센트가 꽉 찼을 때만 뒤에 남아있는 콘센트 번호 중에 가장 적게 나오는 번호를 뽑는다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N, K;
static int[] array;
static HashSet<Integer> powerSocket; // 멀티탭에 먼저 꽂았는지 꽂지 않았는지는 상관이 없다. HashSet 사용
public static void main(String[] args) throws Exception {
SetData();
System.out.println(FindMinValue());
}
private static void SetData() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
powerSocket = new HashSet<Integer>();
array = new int[K];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < K; i++)
array[i] = Integer.parseInt(st.nextToken());
}
private static int FindMinValue() {
int count = 0;
for(int i = 0; i < K; i++) {
// 콘센트가 꽉차지 않거나 콘센트에 꽂혀있는 번호이면 continue
if(powerSocket.contains(array[i]) || isPossible(array[i]))
continue;
// 콘센트가 꽉차고 콘센트에 꽂혀있는 번호가 아닐 시
int max = -1, pick = -1;
for (int num : powerSocket) {
int temp = 0; // temp를 통해 뒤에 가장 적게 오는 수를 지워줌
for (int j = i + 1; j < K; j++) {
if (num == array[j]) {
break;
}
temp++;
}
if (temp > max) {
pick = num;
max = temp;
}
}
powerSocket.remove(pick);
powerSocket.add(array[i]);
count++;
}
return count;
}
private static boolean isPossible(int item) {
if (powerSocket.size() < N) {
powerSocket.add(item);
return true;
}
return false;
}
}
정답 코드 : 1번 방법은 시간초과가 나올 것 같아서 2번 방법을 시행했다. 2번 방법을 쉽게 푸는 팁이 있다면 array.sort로 배열을 오름차순으로 정렬 후 pritorityqueue 우선순위 큐(큐에 있는 값들이 2개 이상이면 오름차순으로 큐에 들어감)를 사용하여 쉽게 해결할 수 있었다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N, K;
static int[][] jewelry;
static int[] bag;
static long maxValue;
public static void main(String[] args) throws Exception {
SetData();
FindMaxValue();
System.out.println(maxValue);
}
private static void SetData() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
maxValue = 0;
jewelry = new int[N][2];
bag = new int[K];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
jewelry[i][0] = Integer.parseInt(st.nextToken());
jewelry[i][1] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < K; i++)
bag[i] = Integer.parseInt(br.readLine());
// 2차원 배열 sort
Arrays.sort(jewelry, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
// TODO Auto-generated method stub
return o1[0] - o2[0];
};
});
Arrays.sort(bag);
}
private static void FindMaxValue() {
// 우선 순위 큐로 해야지 오름차순 정렬이 되서 작은 값이 맨 먼저 나오게됌
Queue<Integer> queue = new PriorityQueue<>();
int j = 0;
for (int i = 0; i < K; i++) {
while (j < N && jewelry[j][0] <= bag[i]) { // 앞에서 담은것은 제외해야 하므로 while문과 j를 사용
queue.add(-jewelry[j][1]); // -를 해주는 이유는 -를 해야지 양수 최대값이 음수로 넣었을 때 오름차순에서 맨 앞으로 가져올 수 있게한다.
j++;
}
if (!queue.isEmpty()) { // for문 한번에 한번만 더한다.
maxValue += Math.abs(queue.poll()); // 음수로 바꿔줬던 수에 절대값을 씌워서 양수로 다시 나오게함
}
}
}
}
- 어떤 일을 하는 순서를 찾는 알고리즘이다. 즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것
- DAG(Directed Acyclic Graph: 사이클이 존재하지 않는 방향 그래프)에만 적용할 수 있다.
코드
정답 코드 : 위상 정렬을 큐를 사용하여 구현한 코드이다. 위상 정렬을 처음 접해 보았는데 코드가 깔끔하다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int N = Integer.parseInt(br.readLine());
ArrayList<ArrayList<Integer>> preBuildingNumber = new ArrayList<>();
for (int i = 0; i <= N; i++) {
preBuildingNumber.add(new ArrayList<>());
}
int[] indegree = new int[N + 1]; // 특정 건물을 짓기 전에 먼저 지어야 할 건물의 개수
int[] times = new int[N + 1]; // 특정 건물을 짓는 데 걸리는 시간
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
times[i] = Integer.parseInt(st.nextToken()); // 해당 건물을 짓기 위한 시간
while (true) {
int preBuildingNumberTemp = Integer.parseInt(st.nextToken());
if (preBuildingNumberTemp == -1)
break;
preBuildingNumber.get(preBuildingNumberTemp).add(i);
indegree[i]++; // 해당 건물을 짓기 전 지어야 할 건물의 수를 더해준다.
}
}
String timeForBuilding = topologicalSort(preBuildingNumber, indegree, times, N);
System.out.print(timeForBuilding);
}
// 위상 정렬
public static String topologicalSort(ArrayList<ArrayList<Integer>> a, int[] indegree, int[] times, int N) {
Queue<Integer> queue = new LinkedList<>();
StringBuilder sb = new StringBuilder();
// 먼저 지어야할 건물이 없는 건물을 큐에 집어 넣음. 해당 큐에 있는 건물을 먼저 짓는다.
for (int i = 1; i <= N; i++) {
if (indegree[i] == 0) {
queue.offer(i);
}
}
// 특정 건물을 짓기 전까지 걸린 시간 누적
int[] result = new int[N + 1];
while (!queue.isEmpty()) {
int now = queue.poll();
for (int next : a.get(now)) {
indegree[next]--;
// indegree를 줄여나가는 과정
// result[next] = max(result[next], result[now] + times[now])
// 위의 수식을 활용하여 result의 값을 초기화하는 것이 핵심
result[next] = Math.max(result[next], result[now] + times[now]);
if (indegree[next] == 0) {
queue.offer(next);
}
}
}
// 특정 건물을 짓기 전 먼저 지어야할 건물의 시간 + 특정 건물을 짓는 시간
for (int i = 1; i <= N; i++) {
sb.append((result[i] + times[i]) + "\n");
}
return sb.toString();
}
}
