[백준] 21939번: 문제 추천 시스템 Version 1 - java

명령어

이 문제는 사실상 단순 구현이다.

그러나 어떤 자료구조를 사용할지에 따라 속도에서 차이가 날 수 있을 듯 하다.

처음에는 PriorityQueue를 사용해서 최대힙, 최소힙을 두개 구했었다.

 

그러나 treeset 을 이용하면 한 개의 객체만으로도 first(), last() 메소드를 통해 최대,최소 데이터를 구할 수 있기에,

treeset을 사용하기로 하였다.

 

 

TreeSet & HashMap

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {

	static class Problem {
		int p; // 문제번호
		int l; // 난이도

		public Problem(int p, int l) {
			this.p = p;
			this.l = l;
		}
    
	}

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());

		// => 최대 난이도, 최소 난이도를 반환하기 위한 treeset
		TreeSet<Problem> ts = new TreeSet<>((o1, o2) -> {
			if (o1.l == o2.l) { // 문제 난이도가 같다면
				return o1.p - o2.p; // 문제 번호가 작은 것 순서대로
			}
			return o1.l - o2.l; // 문제 난이도 오름차순
		});

		Map<Integer, Integer> map = new HashMap<Integer, Integer>(); // 문제번호-난이도 쌍을 관리하기 위한 map

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int p = Integer.parseInt(st.nextToken());
			int l = Integer.parseInt(st.nextToken());
			Problem problem = new Problem(p, l);
			ts.add(problem);
			map.put(p, l);
		}

		int M = Integer.parseInt(br.readLine());
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			switch (st.nextToken()) {
			case "add":
				int p = Integer.parseInt(st.nextToken());
				int l = Integer.parseInt(st.nextToken());
				Problem problem = new Problem(p, l);
				ts.add(problem);
				map.put(p, l);
				break;
			case "recommend":
				int num = Integer.parseInt(st.nextToken());
				if (num == 1) { // 가장 어려운 문제의 번호를 출력 => 최대힙
					System.out.println(ts.last().p);
				} else if (num == -1) { // 가장 쉬운 문제의 번호를 출력 => 최소힙
					System.out.println(ts.first().p);
				}
				break;
			case "solved":
				int s_p = Integer.parseInt(st.nextToken());
				int s_l = map.get(s_p);
				ts.remove(new Problem(s_p, s_l));
				break;
			default:
				break;
			}
			
		}
	}

}

 

먼저, 문제 번호와 난이도를 쌍으로 쉽게 관리하기 위해, Problem 이라는 객체를 만들었으며,

멤버변수로 p(문제번호), l(난이도)를 주었다.

 

최소 난이도, 최대 난이도 문제를 O(1) 로 구하기 위해 TreeSet<> 자료구조를 사용하였다.

TreeSet이란?

TreeSet은 Set 인터페이스를 구현한 클래스로써 객체를 중복해서 저장할 수 없고 저장 순서가 유지되지 않는다는 Set의 성질을 그대로 가지고 있다.

TreeSet은 이진 탐색 트리(BinarySearchTree)의 구조로 이루어져 있다. 이진 탐색 트리는 추가와 삭제에는 시간이 조금 더 걸리지만 정렬, 검색에 높은 성능을 보이는 자료구조다.

TreeSet은 이진탐색트리의 형태로 데이터를 저장하기에 기본적으로 nature ordering을 지원하며 생성자의 매개변수로 Comparator 객체를 입력하여 정렬 방법을 임의로 지정해 줄 수도 있다.

나는 TreeSet<Problem> 를 할당하였으므로, Problem 객체를 커스텀 정렬하기 위해 compare 함수를 오버라이드 해야 했다.

따라서 람다식을 이용해 다음과 같이 정렬을 커스텀하였다.

문제 난이도가 작은순으로 오름차순 정렬하되, 문제 난이도가 같다면 문제 번호가 작은 것 순서대로 정렬하도록 하였다.

		// => 최대 난이도, 최소 난이도를 반환하기 위한 treeset
		TreeSet<Problem> ts = new TreeSet<>((o1, o2) -> {
			if (o1.l == o2.l) { // 문제 난이도가 같다면
				return o1.p - o2.p; // 문제 번호가 작은 것 순서대로
			}
			return o1.l - o2.l; // 문제 난이도 오름차순
		});

또한, solved 명령어가 주어졌을 때 문제번호에 해당하는 문제를 O(1) 로 바로 찾아서 문제번호리스트에서 제거하기 위해,

문제번호를 key로, 난이도를 value 로 가지는 HashMap 을 추가로 할당하였다.

 

먼저, 초기 추천문제리스트에 들어갈 문제들이 주어지면,

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int p = Integer.parseInt(st.nextToken());
			int l = Integer.parseInt(st.nextToken());
			Problem problem = new Problem(p, l);
			ts.add(problem);
			map.put(p, l);
		}

이와 같이 treeset 과 map 에 추가해준다.

 

그런 다음, M개의 명령어를 for문으로 받으면서 해당 명령어에 해당하는 동작을 수행해준다.

1) add

			case "add":
				int p = Integer.parseInt(st.nextToken());
				int l = Integer.parseInt(st.nextToken());
				Problem problem = new Problem(p, l);
				ts.add(problem);
				map.put(p, l);
				break;

add 의 경우, 단순히 treeset 과 map 에 넣어주기만 하면 된다.

 

2) recommend

			case "recommend":
				int num = Integer.parseInt(st.nextToken());
				if (num == 1) { // 가장 어려운 문제의 번호를 출력 => 최대힙
					System.out.println(ts.last().p);
				} else if (num == -1) { // 가장 쉬운 문제의 번호를 출력 => 최소힙
					System.out.println(ts.first().p);
				}
				break;

recommend 의 경우 1이면 가장 어려운 문제를 , -1이면 가장 쉬운 문제의 번호를 출력해준다.

문제를 treeset 에 저장해두었으므로, treeset 의 last() 함수를 사용하면 정렬의 가장 뒷쪽에 있는 객체를, first()를 사용하면 정렬의 0번째 인덱스에 위치하는 객체를 반환해준다.

 

3) solved

			case "solved":
				int s_p = Integer.parseInt(st.nextToken());
				int s_l = map.get(s_p);
				ts.remove(new Problem(s_p, s_l));
				break;

solved의 경우, 문제 번호를 입력받으면 그 문제번호에 해당하는 문제를 추천문제리스트에서 제거해야 한다.

이를 위해 문제번호에 해당하는 난이도를 (문제번호, 난이도) 의 한 쌍인 map으로 관리하고 있기 때문에 O(1)만에 난이도를 찾을 수 있다.

따라서 treeset 에서 해당 (문제번호,난이도)를 가지는 새로운 Problem객체를 만들고 이를 제거하도록 해야 한다.

 

사실, custom 객체의 경우 멤버변수 값이 같더라도 new로 생성하였기 때문에 다른 객체로 인식되어야 한다.

따라서 멤버변수의 값이 같을 때 제대로 remove 가 동작되도록 하려면 equals 와 hashcode 를 override 해야 한다.

그러나, 위 코드로도 remove 가 잘 동작이 되길래 왠지 했더니 compare 을 오버라이딩 한 것이 원인이였다!!

compare 이 객체를 비교하고, 정렬하게 하는 것이므로 사실상 compare 을 override 하는 것은 내부적으로 equals 를 재정의하는 것을 내포하는 것이다!!!!!

실제로, compare 함수 구현부에 들어가보면 다음과 같이 기재되어 있다.

즉, compare(x,y) == 0 과 x.equals(y) 는 성립해야 한다는 것이다.

public interface Comparator<T> {

/*
* It is generally the case, but <i>not</i> strictly required that
* <tt>(compare(x, y)==0) == (x.equals(y))</tt>.  Generally speaking,
* any comparator that violates this condition should clearly indicate
* this fact.  The recommended language is "Note: this comparator
* imposes orderings that are inconsistent with equals."
*/
...

}

 

따라서, 위 코드에서는 equals 와 hashcode 를 재정의하지 않고서도 remove 가 제대로 동작한다.

그러나, 좀 더 명확하게 하고 싶다면 equals 와 hashcode 를 compare 에 일치하도록 재정의하는 것이 맘 편할 것이다..ㅋㅎ