[백준 32387] 충전하기 (골드 4)

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

 

문제를 읽으면서 대충 요약하면서 정리해보았다.

Node 클래스가 필요하다는 것을 먼저 파악하고 어떤 값이 들어갈지 고민해보았고,

먼저, 인덱스와 전력 그리고 행동 순서 를 기억하고 있어야겠다고 생각했다.

그리고 예시를 직접 테스트해보면서 내가 이해한 바가 맞는지 확인하였다.

첫 코드

package baekjoon._32387;

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

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

public class Main {
	
	static int N, Q;
	static List<Node> multitab;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		Q = Integer.parseInt(st.nextToken());
		multitab = new ArrayList<>(N+1);
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i <= N; i++) {
			multitab.add(null);
		}
		
		for (int i=1; i<=Q; i++) {
			st = new StringTokenizer(br.readLine());
			int action = Integer.parseInt(st.nextToken());
			int machine = Integer.parseInt(st.nextToken());
			
			if (action == 1) {
				if (multitab.get(machine) == null) {
					multitab.set(machine, new Node(machine, machine, i));
					sb.append(machine).append("\n");
				} else {
					boolean isPut = false;
					for (int j= machine+1; j<N+1; j++) {
						if (multitab.get(j) == null) {
							multitab.set(j, new Node(j, machine, i));
							sb.append(j).append("\n");
							isPut = true;
							break;
						}
					}
					if (!isPut) {
						sb.append(-1).append("\n");
					}
				}
			} else {
				if (multitab.get(machine) != null) {
					int num = multitab.get(machine).actionNum;
					sb.append(num).append("\n");
					multitab.set(machine, null);
				} else {
					sb.append(-1).append("\n");
				}
				
			}

		}
		System.out.println(sb.toString());
	}
	
	static class Node{
		int idx;
		int power;
		int actionNum;
		
		Node(int idx, int power, int actionNum){
			this.idx = idx;
	        this.power = power;
	        this.actionNum = actionNum;
		}
	}

}

간과한 부분이 있었다.

N과 Q가 10^6까지 가능하기 때문에 for문으로 Q까지 순회하는데 중간에 N을 순회하면서 비어있는 포트를 찾는 것은 2억을 넘어가는 상황이었다.

이 때 시간 복잡도를 계산하지 않고 그냥 정리 후 구현해버린 큰 실수가 발생했다는 것을 깨달았다.

이를 해결하기 위해서는 TreeSet을 사용해야하는 것을 알았다...!

처음에 TreeSet을 선언해주고, 초기화 해준다!

TreeSet<Integer> available = new TreeSet<>();
for (int i = 1; i <= N; i++) available.add(i);

사실 treeset을 많이 사용해보지 않아서 정보를 찾아보면서 진행했다.

여기서 ceiling 함수를 사용해서 제공된 값보다 크거나 같은 값 중 가장 작은 값을 반환하도록 해서

Integer idx = available.ceiling(machine);

해당 값이 null이면 -1을 출력하고, 있다면 Node를 세팅해주고, TreeSet에서 available 수 중에 remove로 제거해준다.

또, 코드를 뽑는 연산이 실행된다면 다시 available에 해당 값을 추가해주면 된다.

[ TreeSet Class ]

• 중복 없는 데이터 집합을 다룸
• HashSet에 비해 상대적으로 데이터 처리 속도가 느리지만 다른 컬렉션에 비해 빠름

[ 생성자 ]

• new TreeSet<값 제네릭>()
• 인자값으로 다른 컬렉션을 줄 수 있음

---

[ add() ]

• 값 추가, 중복값은 무시
• 객체의 경우 중복값을 피하기 위해 hashcode()와 equals() 메소드를 오버라이딩 해야한다.

[ first() / last() ]

• 가장 큰 값, 가장 작은 값 반환한다.

[ lower() / higher() / floor() / ceiling() ]

• lower : 제공된 값보다 작은 값 중 가장 큰 값 (인자값 미포함)
• higher : 제공된 값보다 큰 값 중 가장 작은 값 (인자값 미포함)
• floor : 제공된 값과 같거나 작은 값 중 가장 큰 값 (인자값 포함)
• ceiling : 제공된 값보다 크거나 같은 값 중 가장 작은 값 (인자값 포함)

[ pollFirst / pollLast ]

• 가장 작은 값 / 가장 큰 값을 반환 후 삭제한다.

최종 코드

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

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

public class Main {
	
	static int N, Q;
	static List<Node> multitab;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		Q = Integer.parseInt(st.nextToken());
		multitab = new ArrayList<>(N+1);
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i <= N; i++) {
			multitab.add(null);
		}
		
		TreeSet<Integer> available = new TreeSet<>();
		for (int i = 1; i <= N; i++) available.add(i);
		
		for (int i=1; i<=Q; i++) {
			st = new StringTokenizer(br.readLine());
			int action = Integer.parseInt(st.nextToken());
			int machine = Integer.parseInt(st.nextToken());
			
			if (action == 1) {
				Integer idx = available.ceiling(machine);
		        if (idx == null) {
		            sb.append(-1).append("\n");
		        } else {
		            multitab.set(idx, new Node(idx, machine, i));
		            available.remove(idx);
		            sb.append(idx).append("\n");
		        }
			} else {
				if (multitab.get(machine) != null) {
					int num = multitab.get(machine).actionNum;
					sb.append(num).append("\n");
					available.add(machine);
					multitab.set(machine, null);
				} else {
					sb.append(-1).append("\n");
				}
				
			}
		}
		System.out.println(sb.toString());
	}
	
	static class Node{
		int idx;
		int power;
		int actionNum;
		
		Node(int idx, int power, int actionNum){
			this.idx = idx;
	        this.power = power;
	        this.actionNum = actionNum;
		}
	}

}