문제번호	제목	난이도
1202번	보석 도둑	골드 2
17612번	쇼핑물	골드 2
1700번	멀티탭 스케줄링	골드 1

1202번 보석 도둑

해결 코드:

import java.io.*;
import java.util.*;




class Jewelry{
    int weight;
    int price;

    public Jewelry(int weight, int price) {
        this.weight = weight;
        this.price = price;
    }
}

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        Jewelry[] je = new Jewelry[n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            je[i] = new Jewelry(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        int[] bag = new int[k];
        for (int i = 0; i < k; i++) {
            bag[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(bag);

        long ans = 0;

        //전체 보석을 담고 있을 pq
        PriorityQueue<Jewelry> pq = new PriorityQueue<>((o1,o2) -> {
           if(o1.weight == o2.weight){
               return o2.price - o1.price;
           }
           return o1.weight - o2.weight;
        });

        // 가능한 보석을 담고 있을 qp
        PriorityQueue<Jewelry> qp = new PriorityQueue<>((o1,o2) -> {
            return o2.price - o1.price;
        });

        for (int i = 0; i < n; i++) {
            pq.add(je[i]);
        }

        int start = 0;
        for (int i = 0; i < k; i++) {
            for (int j = start; j < n; j++) {
                if(pq.isEmpty()){
                    break;
                }
                if(pq.peek().weight <= bag[i]){
                    qp.add(pq.poll());
                }else{
                    start = j;
                    break;
                }

            }

            if(qp.isEmpty()){
                continue;
            }
            ans += qp.poll().price;
        }

        bw.write(ans+"");
        br.close();
        bw.close();
    }
}

해결 키포인트:

1. 우선순위 큐를 활용하자! 이때 우선순위 큐를 두개 사용해서 상태를 관리하자!
2. 그리디하게 푸는 문제라서 최적의 경우를 찾으면 된다
3. 이때 최적의 경우는 가방을 오름차순해서 작은 것부터 가능한 모든 보석을 찾아 가장 비싼 보석부터 넣으면 된다!

고민/풀이흐름:

1. 각 보석의 정보를 관리할 클래스를 하나 만들고, 해당 클래스 배열을 만들어준다
2. 가방도 일단은 배열에다가 가방별 무게를 관리한다.
3. 각 가방에는 하나씩만 담을 수 있으므로, 해당 가방의 크기에서 담을 수 있는 보석들을 확인해야한다
4. 만약 한개라면 그 보석만 담으면 되지만 여러개라면 그 중 가장 비싼 보석을 담는 것이 방법 일 수도 있다
5. 하지만 이렇게 하면, 비싼 보석이 엄청 크기가 작아 다른 가방에도 담을 수 있는데 현재 가방에 담아서 그다음 보석을 다른 가방에 넣지 못할 수도 있다
6. 반대의 경우도 똑같다. 가방을 단순히 내림차순, 오름차순으로 정렬해서는 풀리지 않는 문제다. 따라서 다른 방법을 모색해야한다.
7. 그리디하게 뽑기 위해 최적의 경우를 한번 생각해보자.
8. 최적의 방법은 현재 가방의 무게를 오름차순 정렬을 해주고, 해당 가방에 들어갈 수 있는 보석의 무게를 추리는 것이다
9. 그리고 그 보석들 중에서 가장 비싼 보석을 훔친다
10. 가방을 오름차순 정렬해놓았기 때문에 가장 작은 가방부터 탐색한다
11. 따라서 현재 가방에 들어갈 수 있는 보석이라면 이후 들어갈 가방에도 들어갈 것이고, 각 가방에 넣을 때마다 가장 비싼 보석을 그리디하게 훔치면 된다
12. 이를 위해 우선순위 큐를 두개 놓고 풀었다. 첫번째 우선순위 큐는 보석들을 담고 있는데, 무게를 기준으로 오름차순하고 같으면 가격을 기준으로 내림차순한다
13. 이어서 두번째 우선순위 큐는 현재 가방에 들어갈 수 있는 보석들을 관리한다. 해당 우선순위 큐에서는 가격만을 기준으로 내림차순 정렬을 해준다
14. 이제 이중 포문으로 진행하는데 먼저 k개의 가방을 순회한다
15. 이제 start 변수를 활용해서 n만큼 순회하는데, 가방의 무게보다 작은 보석이면 qp에 넣고 만약 작지 않은 보석일 경우 그 지점을 그 다음에 다시 시작하도록 start에 기록해둔다
16. 이렇게 하면 k*n이 아니라 k+n으로 시간복잡도 문제를 해결할 수 있다
17. 내부 순회 탐색 도중 만약 pq가 빈다면 break하고 탈출하면 된다
18. 이어서 qp가 비어있는지를 탐색한다. 만약 비어있다면 넣을 보석이 없으므로 continue한다
19. 이어서 ans에 qp의 가격을 더해준다
20. ans는 long타입으로 지정해주었다 입력값을 확인했을 때, 충분히 int형의 범위를 벗어난다
21. 완성한 ans를 출력하면 정답이 된다

링크:

1202번 - 보석 도둑

17612번 쇼핑물

해결 코드:

import java.io.*;
import java.util.*;


class Member{
    int id;
    int buy;

    public Member(int id, int buy) {
        this.id = id;
        this.buy = buy;
    }
}

class Counter{
    int id;
    int buy;
    int number;

    public Counter(int id, int buy, int number) {
        this.id = id;
        this.buy = buy;
        this.number = number;
    }
}

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        Queue<Member> members = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            members.add(new Member(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }


        PriorityQueue<Counter> pq = new PriorityQueue<>((o1,o2)->{
            if(o1.buy == o2.buy){
                return o2.number - o1.number;
            }
            return o1.buy - o2.buy;
        });

        for (int i = 0; i < k; i++) {
            if(members.isEmpty()){
                break;
            }
            Member tmp = members.poll();
            pq.add(new Counter(tmp.id, tmp.buy, i+1));
        }

        long ans = 0;
        int nowTime = 0;
        List<Integer> answers = new ArrayList<>();
        PriorityQueue<Integer> qp = new PriorityQueue<>();

        while(!pq.isEmpty()){
            if(!members.isEmpty()){
                Counter exit = pq.poll();
                nowTime = Math.max(nowTime, exit.buy);
                qp.add(exit.number);
                answers.add(exit.id);
                while(!pq.isEmpty()){
                    if(pq.peek().buy == nowTime){
                        Counter tmp = pq.poll();
                        qp.add(tmp.number);
                        answers.add(tmp.id);
                        continue;
                    }

                    break;
                }

                while(!qp.isEmpty()){
                    if(members.isEmpty()){
                        break;
                    }
                    Member member = members.poll();
                    int next = qp.poll();
                    pq.add(new Counter(member.id, member.buy + nowTime, next));
                }
                continue;
            }
            if(pq.isEmpty()){
                break;
            }
            Counter tmp = pq.poll();
            answers.add(tmp.id);
        }

        for (int i = 0; i < n; i++) {
            ans += (long)answers.get(i) * (i+1);
        }

        bw.write(ans+"");
        br.close();
        bw.close();
    }
}

해결 키포인트:

• 이것도 우선순위 큐를 두개 활용하는 문제다
• 우선순위 큐의 상태 관리를 떠올리기 쉽지 않았지만,
  조금 생각하면 답을 찾을 수 있다
• 하나는 계산대 정보, 하나는 고객이 나간 카운터의 번호를 관리한다
• 갱신은 현재 누적된 시간과 비교해서 추가한다

고민/풀이흐름:

1. 4번의 이유때문에 현재 줄서 있는 대기고객을 큐로 관리하였다
2. 이때 고객의 정보는 Member 클래스로 관리하였다
3. 이제 우선순위 큐를 사용해서 계산대를 관리해야하는데 Member 클래스 만으로는 계산대 번호를 매기기 어렵다
4. 따라서 Counter 클래스를 하나 더 만들었고 Member 클래스의 필드에 number 필드를 추가하였다
5. 계산대를 관리하는 우선순위 큐는 가장 빨리 나오는 산 물건이 가장 적은 것이 먼저 나오도록 오름차순 정렬을 하는데, 만약 같으면 number를 기준으로 내림차순에서 더 큰 number가 나오도록 한다
6. 일단 k개 만큼 멤버 큐에서 뽑아서 pq에 넣는다. 이때 n보다 k가 작을 수도 있기 때문에 해당 예외를 처리해준다
7. 정답을 처리하기 까다로워서 그냥 따로 리스트로 빼서 관리하였다
8. nowTime 변수를 0으로 초기화하고, 빠져나가서 비어있는 카운터를 관리해줄 qp 우선순위 큐를 하나 더 선언한다
9. 이제 순회를 진행하는데 카운터를 관리하는 우선순위 큐가 비어있지 않은 동안 순회한다
10. 일단 멤버 큐에 남아 있는 멤버가 있는동안 pq에서 값을 하나 뽑고 nowTime과 비교해서 더 큰 값을 넣어준다
11. 정답 리스트에는 pq.id를 넣고 qp에는 pq.number를 넣어준다
12. nowTime이랑 같은 값이 더 남아있을 수 있으므로 더 찾아서 빼준다
13. 이어서 qp가 빌떄까지 비어있는 계산대에 새로운 멤버를 채워넣는다. 만약 채워넣는 도중 대기 멤버가 더이상 없으면 종료한다
14. 새로운 맴버를 넣을 때는 멤버가 구매한 개수 + nowTime으로 넣도록 하여, 시간을 갱신하도록 한다
15. 멤버 큐가 비어있어도 순회는 계속된다. 아직 계산대 큐에 멤버가 남아있을 수 있기 때문이다
16. 해당 경우도 정답 리스트에 넣어주고 빌때까지 반복한다
17. 이제 정답 리스트을 순회해서 각 값과 i+1을 곱해서 ans에 더해준다
18. 이때 ans는 long타입이고 정답을 출력하면 정답이 된다.

링크:

17612번 - 쇼핑물

1700번 멀티탭 스케줄링

해결 코드:

import java.io.*;
import java.util.*;



class Pair{
    int number;
    int value;
    int findPos;

    public Pair(int number, int value, int findPos) {
        this.number = number;
        this.value = value;
        this.findPos = findPos;
    }
}


public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[k];
        for (int i = 0; i < k; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Set<Integer> set = new HashSet<>();
        int ans = 0;
        for (int i = 0; i < k; i++) {
            if(set.contains(arr[i])) {
                continue;
            }
            if(set.size()<n){
                set.add(arr[i]);
                continue;
            }

            int max = -1;
            int pos = -1;
            for (Integer s : set) {
                int tmp = 0;
                List<Integer> list = new ArrayList<>();
                for (int j = i+1; j < k; j++) {
                    list.add(arr[j]);
                }
                if(list.contains(s)){
                    tmp = list.indexOf(s)+1;
                }else{
                    tmp = k-i-1;
                }

                if(tmp > max){
                    max = tmp;
                    pos = s;
                }
            }
            set.remove(pos);
            set.add(arr[i]);
            ans++;

        }

        bw.write(ans+"");
        br.close();
        bw.close();
    }
}

해결 키포인트:

• Set을 사용해서 해결하였다.
• 가장 그리디하게 풀 수 있는 최적의 방법은 현재 Set에 있는 값들 중 일부만 나타나는 경우와 모두 다 나타나는 경우를 고려한뒤, 일부만 나오면 나오지 않는 수를 제거하고, 모두 다 나오면 가장 늦게 나오는 경우를 제거하면된다

고민/풀이흐름:

1. 가장 그리디하게 푸는 방법은 먼저 현재지점 + 1에 현재 플러그 번호가 있는지 체크하고 없는 것을 우선적으로 제거한다
2. 만약 모두 있다면 가장 늦게 사용하는 것을 우선적으로 제거한다
3. max와 pos를 사용하였고, list를 사용해서 i+1부터 k까지의 수를 담았다
4. list의 contains를 사용해서 만약 해당하는 수가 있다면 indexOf(s) + 1을 통해 가장 처음 발견되는 인덱스 위치 + 1을 해준다
5. 만약 발견되지 않는다면 k-i-1을 통해 나올 수 있는 가장 큰 수로 보내서 최우선적으로 제거되도록 한다
6. tmp가 max보다 크다면 max에 tmp를 넣고 pos에 s를 넣는다
7. 위 과정 종료 후에 set에서 해당하는 pos를 remove한다
8. 그리고 현재 arr[i]를 set에 add한다
9. ans값을 이어서 증가시키고, 위 과정이 모두 끝나면 완성된 ans를 출력하면 정답이 된다.

링크:

1700 - 멀티탭 스케줄링