[백준/BOJ] 1700 멀티탭 스케줄링 - JAVA - 골드1
문제
https://www.acmicpc.net/problem/1700
문제 분석
조건
- N개의 플러그가 있고 K번의 전기 용품을 사용한다.
- 전기 용품의 이름은 K이하의 자연수로 순서대로 주어진다.
- 플러그를 가장 적게 뽑을 때 플러그를 뽑는 횟수를 출력한다.
풀이방법
그리디 방법으로 접근한다.
- 이미 플러그에 꼽혀있는 물품일 경우 넘어간다.
- 플러그가 비어있으면 빈 곳을 사용한다.
- 플러그가 가득 차있으면
- 뒤에 사용하지 않는 용품이 있는지 검사하여 사용하지 않는 용품을 뽑는다.
- 전부 다시 사용되는 용품일 경우 가장 마지막에 사용되는 용품을 뽑는다.
골드1 치고는 간단한 문제이다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int maxPlug;
static int K;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
maxPlug = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
int[] order = new int[K];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < K; i++) {
order[i] = Integer.parseInt(st.nextToken());
}
int[] plugs = new int[maxPlug];
int answer = 0;
for (int use = 0; use < K; use++) {
int plugNum = 0;
for (int inPlugMachine : plugs) {
//이미 플러그에 있는지 확인
if (inPlugMachine == order[use]) {
plugNum = -1;
break;
}
}
if (plugNum == -1) {
continue;
}
plugNum = getEmptyPlugNum(plugs);
if (plugNum >= 0) {
//플러그 꽂을 위치 있음
plugs[plugNum] = order[use];
//continue;
} else {
answer++;
plugNum = getNotUse(use, order, plugs);
if (plugNum >= 0) {
plugs[plugNum] = order[use];
} else {
plugs[getLastUse(use, order, plugs)] = order[use];
}
}
}
System.out.println(answer);
}
//가장 마지막에 사용하는 플러그 반환
private static int getLastUse(int use, int[] order, int[] plugs) {
if (use == order.length - 1) {
return 0;
}
HashMap<Integer, Integer> m = new HashMap<>();
for (int plug = 0; plug < plugs.length; plug++) {
m.put(plugs[plug], plug);
}
for (int i = use + 1; i < order.length; i++) {
m.remove(order[i]);
if (m.size() == 1) {
break;
}
}
for (Integer machine : m.keySet()) {
return m.get(machine);
}
return 0;
}
/**
* 뒤에 사용하지 않는 플러그 찾아 반환
*/
private static int getNotUse(int use, int[] order, int[] plugs) {
if (use == order.length - 1) {
return 0;
}
int[] machine = new int[K + 1];
Arrays.fill(machine, -1);
for (int i = 0; i < plugs.length; i++) {
machine[plugs[i]] = i;
}
for (int i = use + 1; i < order.length; i++) {
if (machine[order[i]] >= 0) {
machine[order[i]] = -1;
}
}
for (int i = 0; i < K + 1; i++) {
if (machine[i] >= 0) {
return machine[i];
}
}
return -1;
}
/**
* 플러그 꽂을 위치 반환
*
* @return 자리 없으면 -1
*/
private static int getEmptyPlugNum(int[] plugs) {
for (int i = 0; i < plugs.length; i++) {
if (plugs[i] == 0) {
return i;
}
}
return -1;
}
}
결과
728x90