[자바] 백준 1700번: 멀티탭 스케줄링

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

1700번: 멀티탭 스케줄링

 

첫 시도 실패했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class P1700 {

	static LinkedList<Integer> list;
	static HashSet<Integer> powerBar = new HashSet<>();
	static int n, count = 0, result = Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine());

		list = new LinkedList<>();
		for (int i = 0; i < k; i++) {
			list.add(Integer.parseInt(st.nextToken()));
		}

		perm(0, k);

		System.out.println(result);
	}

	static void perm(int i, int m) {
		if (i == m) {
			if (result > count)
				result = count;
		} else if (powerBar.size() < n || powerBar.contains(list.peek())) {
			// 멀티탭에 자리가 빈 경우 또는 이미 꽂혀있는 경우
			int cur = list.poll();
			powerBar.add(cur);
			perm(i + 1, m);

			list.add(0, cur);
		} else {
			// 콘센트 하나 뽑아야 하는 경우

			int cur = list.poll();
			Object[] arr = powerBar.toArray();
			for (Object value : arr) {
				powerBar.remove(value); // 하나 뽑음
				count++;

				powerBar.add(cur);
				perm(i + 1, m);

				count--;
				powerBar.remove(cur);// 원상복구
				powerBar.add((int) value);
			}
			list.add(0, cur);
		}
	}
}

백트래킹 방법으로 풀었는데,

메모리초과가 났다.

 

아마 powerBar.toArray() 해서 배열로 받는 과정에서

스택이 쌓이면서 배열이 아주 많이 만들어지고 그것 때문에 메모리초과가 나지 않았을까 싶다.

 

오늘 시간이 없어 내일 다시 풀어보겠다.

---

2차 시도

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class P1700 {

	static LinkedList<Integer> list;
	static LinkedList<Integer> powerBar = new LinkedList<>();
	static int n, k, count = 0, result = Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine());

		list = new LinkedList<>();
		for (int i = 0; i < k; i++) {
			list.add(Integer.parseInt(st.nextToken()));
		}

		perm(0, k);

		System.out.println(result);
	}

	static void perm(int i, int m) {
		if (i == m) {
			if (result > count)
				result = count;
		} else if (powerBar.size() < n || powerBar.contains(list.peek())) {
			// 멀티탭에 자리가 빈 경우 또는 이미 꽂혀있는 경우
			int cur = list.poll();
			if (!powerBar.contains(cur))
				powerBar.add(cur);
			perm(i + 1, m);

			list.add(0, cur);
		} else {
			// 콘센트 하나 뽑아야 하는 경우

			int cur = list.poll();
			for (int j = 0; j < n; j++) {
				int delete = powerBar.poll();

				count++;
				powerBar.add(cur);
				perm(i + 1, m);
				count--;

				powerBar.remove((Object) cur);
				powerBar.add(delete);
			}
			list.add(0, cur);
		}
	}
}

배열이 많이 생기는 게 문제라고 생각해서

powerBar를 HashSet에서 LinkedList로 바꾸고,

배열을 만들지 않고 반복문을 돌면서 요소를 하나씩 뺐다 더했다 할 수 있도록 수정했다.

하지만 여전히 메모리초과가 났다.

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class P1700 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine());

		LinkedList<Integer> list = new LinkedList<>();
		for (int i = 0; i < k; i++) {
			list.add(Integer.parseInt(st.nextToken()));
		}

		int count = 0;
		HashSet<Integer> powerBar = new HashSet<>();
		for (int i = 0; i < k; i++) {
			int cur = list.poll();

			if (powerBar.contains(cur))
				continue;

			if (powerBar.size() < n) {
				powerBar.add(cur);
				continue;
			}

			count++;
			for (int use : powerBar) {
				if (!list.contains(use)) {
					// 앞으로 사용할 일 없는 플러그
					powerBar.remove(use);
					break;
				}
			}

			if (powerBar.size() == n) {
				// 다 사용할 일 있는 플러그라서 아무것도 못 뻈을 때
				int delete = -1;
				int idx = -1;
				for (int use : powerBar) {
					if (idx < list.indexOf(use)) {
						idx = list.indexOf(use);
						delete = use;
					}
				}
				powerBar.remove(delete);

			}
			powerBar.add(cur);
		}
		System.out.println(count);
	}

}

다시 푼 코드

 

완전히 갈아엎었다.

 

전기용품 목록을 list에 받은 다음,

list에서 하나씩 poll한다. 이것을 cur이라는 변수에 넣었다.

 

만약 멀티탭에 cur이 꽂혀있다면 다음 전기용품을 뽑는다.

 

그렇지 않고 만약 멀티탭이 비었다면 cur을 꽂고 다음 전기용품을 뽑는다.

 

여기까지 아무것도 해당되지 않았다면 멀티탭에서 코드 하나를 뽑아야 한다.

count를 1증가시킨다.

 

멀티탭에 꽂힌 코드들을 순회하면서, 앞으로 사용할 일 없는 코드가 있다면 그 코드를 뽑는다.

만약 모든 멀티탭이 다 쓸일이 있다면,

가장 늦게 사용할 코드를 뽑는다.

 

뽑은 이후에 cur을 멀티탭에 꽂고 다음 전기용품을 뽑는다.