Problem Solving/Baekjoon

[백준/boj.kr] 21939번 문제 추천 시스템 Version1(JAVA)

머직타드 2022. 4. 17. 00:43
문제 추천 시스템 Version1 문제 보기

 

1. 문제 정의

"문제번호, 난이도"로 정의된 아이템들을 가지고 아래의 3가지 명령어에 대해 처리해 주는 문제 입니다.

명령어 상세 내용 비고
recommend x(x = ±1) x = 1: 가장 어려운 문제의 번호를 출력 가장 어려운 문제가 여러개면,
가장 큰 문제 번호 출력
x = -1: 가장 쉬운 문제의 번호를 출력 가장 쉬운 문제가 여러개면,
가장 작은 문제 번호 출력
add P L 난이도 L인 문제 번호 P를 추가 1. 리스트에 없는 문제번호 P만 add
2. 이전에 있던 문제번호 P가
   다른 난이도로 add 가능
solved P 문제 번호 P를 제거 리스트에 있는 문제 번호 P만 delete

 

 

2. 풀이 방법 탐색

"문제번호, 난이도" 쌍(Pair)을 저장하고, 주어지는 명령어에 따라 지지고 볶으면 됩니다. 

 

1) Collection 인터페이스

Java Collection Framework의 기본 상속 구조

 

2) Collection 인터페이스의 특징

인터페이스 구현 클래스 특징
List LinkedList 1. 순서가 있는 데이터의 집합
2. 데이터의 중복 허용
Stack
Vector
ArrayList
Set HashSet 1. 순서가 없는 데이터의 집합
2. 데이터의 중복 허용 불가
TreeSet
Map HashMap 1. Key-Value 쌍의 순서가 없는 데이터의 집합
2. Key의 중복 허용 불가
3. Value의 중복 허용 가능
TreeMap
HashTable
Properties

 

3) 자료형 선정

recommend 명령어의 수행 내용은 가장 어렵거나 가장 쉬운 문제의 번호를 출력하도록 되어 있는데, 난이도가 동일한 문제가 2개 이상이라면 x값에 따라 문제 번호도 오름차순/내림차순 으로 정렬할 필요도 있어 보입니다. 이러한 특성을 활용해 아이템을 저장할 Collection으로 Map을 선정하고, 난이도에 따라 아이템의 순서를 정렬해주면 됩니다.

 

1. '문제번호 - 난이도'의 쌍으로 아이템 저장

2. Key 순으로 아이템 정렬

 

문제번호, 난이도 모두 비교해서 정렬해야 하기해 TreeSet을 활용해 문제를 풀이하고, 순서를 정렬할 때는 Comparator/Comparable 인터페이스를 재정의하면 됩니다.

 

 

 

3. 문제 풀이

(1) 조건 체크

문제 번호는 100,000 이하의 자연수 이고, 문제 난이도는 100 이하의 자연수로 int 범위에도 포함되며 크기가 크지 않습니다. 그리고 주어지는 명령어의 개수가 10,000로 많지가 않아 별도로 오버헤드에 대해 고려할 건 없습니다.

 

 

(2) "문제번호, 난이도" Pair 구현

class Pair{
	int P, L;
	
	Pair(int p, int l){
		this.P = p;
		this.L = l;
	}
}

 

 

(3-1) Comparator 구현

//Comparator 비교
class AscendingComparator implements Comparator<Pair>{
	
	@Override
	public int compare(Pair a, Pair b) {
		if(a.L < b.L) return -1;
		else if(a.L == b.L) {
			//가장 쉬운 문제가 여러개라면
			//문제 번호 오름차순 정렬
			if(a.P < b.P) return -1;
			else if(a.P == b.P) return 0;
			else return 1;
		}
		else return 1;
	}
}

 

 

(3-2) Comparable 구현

public static class Pair implements Comparable<Pair>{
	int P, L;
	
	Pair(int p, int l){
		this.P = p;
		this.L = l;
	}
	
	//Comparable 비교
	@Override
	public int compareTo(Pair p) {
		
		if(this.L == p.L) {
			return this.P - p.P;
		}
		else {
			return this.L - p.L;
		}
	}
}

 

 

(4) 명령어 처리 구현

for(int j=0; j<M; j++) {
	StringTokenizer st = new StringTokenizer(br.readLine());
	String cmd = st.nextToken();
				
	if(cmd.equals("recommend")) {
		// recommend x
		int x = Integer.parseInt(st.nextToken());
		
		if(x == 1) {
			//가장 어려운 문제
			System.out.println(asc.last().P);
		}
		else {
			// 가장 쉬운 문제
			System.out.println(asc.first().P);
		}
	} 
	else if(cmd.equals("add")){
		// add P L
		int P = Integer.parseInt(st.nextToken());
		int L = Integer.parseInt(st.nextToken());
		
		asc.add(new Pair(P, L));
		map.put(P, L);
	}
	else {
		//solved P
		int P = Integer.parseInt(st.nextToken());
		int L = map.get(P);
		
		asc.remove(new Pair(P, L));
		map.remove(P);
	}
}

 

 

(5-1) 최종 소스(Comarator 재정의 버전)

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

public class Boj21939_comparator {

	public static int N, M;
	public static TreeSet<Pair> asc = new TreeSet<Pair>(new AscendingComparator());
	public static Map<Integer,Integer> map = new HashMap<>(); // 문제번호, 난이도 바로 찾기 위해 사용
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int P = Integer.parseInt(st.nextToken());
			int L = Integer.parseInt(st.nextToken());
			
			asc.add(new Pair(P, L));
			map.put(P, L);
		}
		
		M = Integer.parseInt(br.readLine());
		
		for(int j=0; j<M; j++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String cmd = st.nextToken();
						
			if(cmd.equals("recommend")) {
				// recommend x
				int x = Integer.parseInt(st.nextToken());
				
				if(x == 1) {
					//가장 어려운 문제
					System.out.println(asc.last().P);
				}
				else {
					// 가장 쉬운 문제
					System.out.println(asc.first().P);
				}
			} 
			else if(cmd.equals("add")){
				// add P L
				int P = Integer.parseInt(st.nextToken());
				int L = Integer.parseInt(st.nextToken());
				
				asc.add(new Pair(P, L));
				map.put(P, L);
			}
			else {
				//solved P
				int P = Integer.parseInt(st.nextToken());
				int L = map.get(P);
				
				asc.remove(new Pair(P, L));
				map.remove(P);
			}
		}
	}
}

//Comparator 비교
class AscendingComparator implements Comparator<Pair>{
	
	@Override
	public int compare(Pair a, Pair b) {
		if(a.L < b.L) return -1;
		else if(a.L == b.L) {
			//가장 쉬운 문제가 여러개라면
			//문제 번호 오름차순 정렬
			if(a.P < b.P) return -1;
			else if(a.P == b.P) return 0;
			else return 1;
		}
		else return 1;
	}
}

class Pair{
	int P, L;
	
	Pair(int p, int l){
		this.P = p;
		this.L = l;
	}
}

 

 

(5-2) 최종 소스(Comparable 재정의 버전)

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

public class Boj21939_comparable {

	public static int N, M;
	
	public static class Pair implements Comparable<Pair>{
		int P, L;
		
		Pair(int p, int l){
			this.P = p;
			this.L = l;
		}
		
		//Comparable 비교
		@Override
		public int compareTo(Pair p) {
			
			if(this.L == p.L) {
				return this.P - p.P;
			}
			else {
				return this.L - p.L;
			}
		}
	}
	
	public static void main(String[] args) throws IOException{
		TreeSet<Pair> asc = new TreeSet<Pair>();
		Map<Integer,Integer> map = new HashMap<>();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int P = Integer.parseInt(st.nextToken());
			int L = Integer.parseInt(st.nextToken());
			
			asc.add(new Pair(P, L));
			map.put(P, L);
		}
		
		M = Integer.parseInt(br.readLine());
		
		for(int j=0; j<M; j++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String cmd = st.nextToken();
						
			if(cmd.equals("recommend")) {
				// recommend x
				int x = Integer.parseInt(st.nextToken());
				
				if(x == 1) {
					//가장 어려운 문제
					System.out.println(asc.last().P);
				}
				else {
					// 가장 쉬운 문제
					System.out.println(asc.first().P);
				}
			} 
			else if(cmd.equals("add")){
				// add P L
				int P = Integer.parseInt(st.nextToken());
				int L = Integer.parseInt(st.nextToken());
				
				asc.add(new Pair(P, L));
				map.put(P, L);
			}
			else {
				//solved P
				int P = Integer.parseInt(st.nextToken());
				int L = map.get(P);
				
				asc.remove(new Pair(P, L));
				map.remove(P);
			}
		}
	}
}

'Problem Solving > Baekjoon' 카테고리의 다른 글

[백준/boj.kr] 6198번 옥상 정원 꾸미기(JAVA)  (0) 2022.04.12
[백준/boj.kr] 5585번 거스름돈 (C/C++, JAVA)  (0) 2022.03.15
[백준/boj.kr] 2748번 피보나치 수 2 (C/C++, JAVA)  (0) 2022.03.15
[백준 6603]로또  (0) 2019.01.17

'Problem Solving/Baekjoon'의 다른글

  • 현재글[백준/boj.kr] 21939번 문제 추천 시스템 Version1(JAVA)

관련글

댓글

티스토리툴바