백준 2109 순회강연 Java

그리디알고리즘 문제로 추정되는 순회강연 문제이다.

원래 스스로 푼 문제는 올리지 않지만 

중간에 못풀 것 같아서 구글에 쳐봤는데 파이썬 코드와 부족한 설명이 있는 글 들 밖에 없어서

내가 Java로 성공하고 헤매고있는 누군가에게 도움이 되라고 올린다.

 

강연 시 받는 페이 p와 와야하는 기한 d가 주어진다.

처음엔 주어진 기한인 줄 모르고 

그 날에 강연을 해달라는 건줄 알아서

강연 날 순으로 정렬을 해서 페이값을 더하는 코드를 제출했다가 틀렸다.

 

그 날와서 강연을 해달라는 것이 아니라  d일 안에 와서 강연을 해달라는 것이었다.

그렇게 생각해보니까 복잡해보이는 문제였다.

 

우선 강연료순으로 정렬을 했다.

그리고

n과 p와 d의 주어진 수가 10000 이하여서

시간초과를 생각안하고

ArrayList를 만들어서

기한인 d가 리스트에 없으면

d를 더해주고

d가 리스트에 있으면 for문으로 d를 -1 해가며 빈자리가 있는지

찾아서 리스트에 더해줬다.

이런식으로 하니 바로 시간초과가 나왔다.

 

찾으면 break를 해주고 Scanner 를 BufferedReader로 바꿔주는 등

여러가지 시간 초과를 해결하기 위해 노력했지만 실패했다.

 

그렇게 헤매던 도중 문득 ArrayList에서 d가 있는 지 찾기위해썼던 메소드인 contains가 

O(n)이란 것이 생각이 나서 d가 있는지 찾기 위해 배열을 사용해서 직접탐색한다면

O(1)이기 때문에 시간초과가 나오지 않을 것 같다.란 생각을 했다.

그렇게 풀고 제출하니 바로 성공했다.

 

결론적으로 이 문제는

1. 강의료인 p순으로 정렬한다.

2. 강의료와 기한이 있는 배열을 순차적으로 탐색해서 그 기한에 아무것도 없으면 강의료를 더한다.

3. 그 기한에 강의가 있다면 기한을 -1해가며 1이될때 까지 찾는다.

   비는 곳이 있다면 강의료를 더해주고 그 곳을 채워준다.

 

나보다 빠른 효율로 푼 사람의 코드를 보니 가중치 큐인 Priority Queue를 사용했더라.

가중치 큐도 언제 한번 제대로 공부해봐야겠다...

 

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
//순회강연
public class Q2109 {
 
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        Lecture [] a = new Lecture[n];
        boolean [] b = new boolean[100001];
        
        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(reader.readLine());
            int p = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            a[i] = new Lecture(p, d);
        }
        Arrays.sort(a);
 
        int ans = 0;
        for(int i=0; i<n; i++) {
            if(!b[a[i].d]) {
                ans += a[i].p;
                b[a[i].d] = true;
            }
            else
                for(int j=a[i].d-1; j>=1; j--) {
                    if(!b[j]) {
                        ans += a[i].p;
                        b[j] = true;
                        break;
                    }
                }
        }
        System.out.println(ans);
    }
 
}
class Lecture implements Comparable<Lecture> { //강의료와 기한을 저장하기 위한 클래스
    int p;
    int d;
    
    public Lecture(int p, int d) {
        this.p = p;
        this.d = d;
    }
 
    @Override
    public int compareTo(Lecture o) {
        int r = (this.p - o.p) *-1; //강의료 순으로 정렬
        if(r==0)
            r= this.d - o.d ;
        return r;
    }
    
}