백준 1202번 보석 도둑

문제

나의 풀이

import java.util.*;

public class Main {
    static class Jewel implements Comparable<Jewel> {
        public int m, v, w; // 무게, 가격, w가 0: 보석, 1: 가방
        Jewel(int m, int v, int w) {
            this.m = m;
            this.v = v;
            this.w = w;
        }
        public int compareTo(Jewel that) {
            if(this.m < that.m) { // 무게를 기준으로 오름차순
                return -1;
            } else if(this.m == that.m) { // 무게가 같은 경우
                if(this. w < that.w) { // 가격을 기준으로 오름차순
                    return -1;
                } else if(this.w == that.w) { // 가격이 같은 경우
                    return 0;
                } else {
                    return 1;
                }
            } else {
                return 1;
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        Jewel a[] = new Jewel[n + k];
        for(int i = 0; i < n; i++) { // 보석 입력
            int m = sc.nextInt();
            int v = sc.nextInt();
            a[i] = new Jewel(m, v, 0);
        }
        for(int i = 0; i < k; i++) { // 가방 입력
            int m = sc.nextInt();
            a[n + i] = new Jewel(m, 0, 1); 
        }
        
        Arrays.sort(a); // 무게 기준 오름차순 정렬
        
        PriorityQueue<Integer> q = new PriorityQueue<Integer>();
        long answer = 0;
        for(Jewel p : a) {
            if(p.w == 0) { // 보석인 경우
                q.offer(-p.v); // 최소 힙을 최대 힙처럼 사용하기 위해서 음수로 넣었다가 뺄때 양수로 바꿈
            } else { // 가방인 경우
                if(!q.isEmpty()) { // 후보 보석이 있는 경우 
                    answer += (long) -q.poll(); // 가장 가격이 큰 보석 빼기
                }
            }
        }
        System.out.println(answer);
    }
}

각각의 가방에 들어갈 수 있는 가장 가격이 높은 보석을 조사하는 방식으로 구현한다. 보석과 가방을 하나로 합치고 무게를 기준으로 오름차순 정렬해서 가방이 나올 때 마다 앞에 있는 보석 중에서 가장 가격이 큰 보석을 정답에 더해주면 된다. 앞에 있는 보석들은 후보로 두게 되는데 이때 우선순위 큐를 이용한다.

결과

백준 2109번 순회강연

문제

나의 풀이

import java.util.*;

public class Main {
    static class Lecture implements Comparable<Lecture> {
        int p, d;
        Lecture(int p, int d) {
            this.p = p;
            this.d =d;
        }
        public int compareTo(Lecture that) {
            if(this.d < that.d) { // 날짜를 기준으로 내림차순
                return 1;
            } else if(this.d == that.d) { // 날짜가 같은 경우
                if(this.p < that.p) { // 강연료를 기준으로 오름차순
                    return -1;
                } else if(this.p == that.p) {
                    return 0;
                } else {
                    return 1;
                }
            } else {
                return -1;
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Lecture a[] = new Lecture[n];
        for(int i = 0; i < n; i++) { 
            a[i] = new Lecture(sc.nextInt(), sc.nextInt());
        }
        
        Arrays.sort(a); // 날짜기준 내림차순 정렬
        
        PriorityQueue<Integer> q = new PriorityQueue<Integer>();
        int answer = 0;
        int k = 0;
        for(int i = 10000; i >= 1; i--) {
            while(k < n && a[k].d == i) { // 같은 날짜일 때까지
                q.offer(-a[k].p);
                k += 1;
            }
            if(!q.isEmpty()) {
                answer += -q.poll(); // 가장 큰 강연료 정답에 더하기
            }
        }
        
        System.out.println(answer);
    }
}

보석 도둑 문제와 매우 비슷하게 풀 수 있다. 가방을 기준으로 보석 도둑 문제를 푼 방법에서 무게를 내림차순으로 정렬하고 문제를 해결하면 순회강연 문제와 같은 의미를 갖는다. 강연을 기준으로 내림차순 정렬했고 각각의 날짜마다 앞에 있는 강연 중에서 p가 가장 큰 것을 고르면 된다.

결과

인프런 좌석 번호

문제

나의 풀이

import java.util.Arrays;

public class SeatNumber {
    static public int[] solution(int c, int r, int k) {
        int answer[] = new int[2];
        if(k > c * r) { // 범위 밖인 경우
            return new int[] { 0, 0 };
        }
        int seat[][] = new int[c][r];
        int dx[] = { -1, 0, 1, 0 };
        int dy[] = { 0, 1, 0, -1 };
        int x = 0, y = 0, count = 1, d = 1;
        while(count < k) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if(nx < 0 || nx >= c || ny < 0 || ny >= r || seat[nx][ny] > 0) { // 범위 밖이거나 이미 사람이 있는 경우
                d = (d + 1) % 4; // 90도 회전
                continue;
            }
            seat[x][y] = count;
            count++; // 횟수 증가
            x = nx; // 이동하기
            y = ny;
        }
        answer[0] = x + 1; // (1,1)부터 시작이기 때문에
        answer[1] = y + 1;
        return answer;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(SeatNumber.solution(6, 5, 12)));
        System.out.println(Arrays.toString(SeatNumber.solution(6, 5, 20)));
        System.out.println(Arrays.toString(SeatNumber.solution(6, 5, 30)));
        System.out.println(Arrays.toString(SeatNumber.solution(6, 5, 31)));
    }
}

결과