쌉쌀한 무화과의 개발로그

[문제]

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

[입력]

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

[출력]

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

[예제]

[힌트]

두 번째 예제의 경우 첫 번째 보석을 두 번째 가방에, 세 번째 보석을 첫 번째 가방에 넣으면 된다.

>문제 풀이

주어진 보석들의 무게와 값어치를 Gem(weight, price)를 이용하여 Gem[] gem에 저장해줍니다.

우리는 주어진 가방안에 담을 수 있는 무게의 보석들 중에 가장 높은 값어치의 보석을 담아야 합니다.

​

보석: 처음에는 무게를 기준으로 정렬을 해야하고, 가방에 담을 수 있는 보석들을 대상으로 다시 값이 가장 높은 보석을 구해줍니다.

가방: 무게 기준으로 오름차순 정렬을 해주고 보석을 담아야합니다. 그래야 가방이 담을 수 있는 무게보다 더 적은 무게의 보석들을 고려할 수 있습니다.

ex) 가방= 3, 10 보석: (3, 40) (5, 30) (7, 15) (10, 20) =>이럴 경우 첫번째 가방에 (3, 40)을 담고, 두번째 가방에 (5, 30)을 담아야 합니다.

​

1. 보석들을 무게 기준으로 오름차순 정렬을 합니다.

(2차원 배열이라 weight과 price 중에 기준을 정해줘야합니다.)

​

2. 가방을 무게기준으로 오름차순 정렬을 해줍니다.

​

3. Priority Queue를 선언해줍니다. 이 때 기준을 정해줘야하는데, 값을 기준으로 할 것입니다.

포인터 gIndex=0;

​

4. 연산

for(i: 가방) {
     while(포인터를 옮겨주며 N보다 작고, gem[gIndex]가 가방의 무게 i보다 작은) {
          조건의 보석들을 pq에 넣어줍니다.
     }
     pq가 비어있지 않다면 result+=pq.poll().price;
}

>전체 코드

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner scan= new Scanner(System.in);
		
		int N= scan.nextInt();
		int K= scan.nextInt();
		Gem[] gem= new Gem[N];
		int[] bags= new int[K];
		
		int w, p;
		for(int i=0; i<N; i++) {
			w= scan.nextInt();
			p= scan.nextInt();
			gem[i]= new Gem(w, p);
		}
		
		for(int i=0; i<K; i++) {
			bags[i]= scan.nextInt();
		}
		
		// 가방 오름차순 정렬
		Arrays.sort(bags);
		// 보석 무게순 정렬(ascending)
		Arrays.sort(gem, (g1, g2)-> Integer.compare(g1.weight, g2.weight));
		// 보석 높은 값 기준 힙
		PriorityQueue<Gem> pq= new PriorityQueue<>((g1, g2)-> Integer.compare(g2.price, g1.price));
		
		int gIndex=0;
		long result=0;
		//1. 남은 가방 중 제일 작은 가방을 선택
		for(int i=0; i<bags.length; i++) {
			//2. 선택된 가방에 넣을 수 있는 남은 보석 중 가장 비싼 보석을 선택(1가방, 1보석)
			while(gIndex<N && gem[gIndex].weight<=bags[i]) {
				pq.add(gem[gIndex++]);
			}
			if(!pq.isEmpty()) result+=pq.poll().price;
		}
		
		System.out.println(result);
		
	}//main
	
	static class Gem {
		int weight;
		int price;
		
		public Gem(int weight, int price) {
			this.weight= weight;
			this.price= price;
		}
	}
}

https://www.acmicpc.net/problem/1202

[문제 설명]

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

​

[제한 사항]

numbers의 길이는 1 이상 100,000 이하입니다.

numbers의 원소는 0 이상 1,000 이하입니다.

정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

​

<입출력 예>

>문제 풀이

문제의 숫자가 꼭 한자릿수만 나오는게 아니기 때문에 잘 생각해야합니다.

예를 들어 만약 10, 6 의 경우 610> 106 이기 때문에 마냥 배열을 오름차순으로 정렬할 수 없습니다.

그래서 숫자를 정렬할 때 comparator을 써서 10 과 6을 붙여본 결과를 비교하여 오름차순으로 정렬 했습니다. 106과 610을 비교한 결과로 정렬을 하는 것이죠.

        Arrays.sort(str, new Comparator<String>(){ //정렬하기
            public int compare(String o1, String o2){
                return -(o1+o2).compareTo(o2+o1);
            }
        });

>전체 코드

import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        String[] str= new String[numbers.length];
        
        int j=0;
        for(int i: numbers){
            str[j++]= String.valueOf(i);
        }
        
        Arrays.sort(str, new Comparator<String>(){
            public int compare(String o1, String o2){
                return -(o1+o2).compareTo(o2+o1);
            }
        });
        
        for(String i: str){
            answer+=i;
        }
        
        for(int i=0; i<answer.length(); i++){
            if(answer.charAt(i)!='0'||i==answer.length()-1){
                answer= answer.substring(i);
                break;
            }
        }
        
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/42746

[문제]

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

[입력]

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

[출력]

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

[제한]

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

[예제]

>문제 풀이

정렬하는 방법과 hashmap 사용할 줄만 알면 쉬운 문제였다.

(근데 hashmap 딱 한번 써보고 안써서 까먹어서 다시 찾아봄..ㅎㅎ;)

<로직>

1. N, arr[] 입력 받고
2. arr_v= arr.clone(); // arr_v[] 배열에다가 깊은 복사로 붙여넣는다.
3. arr.sort
4. N만큼 반복문을 돌리며
   : arr값을 중복되지 않게 hashmap에 넣는다.
5. N만큼 반복문을 돌리며
   : StringBuilder sb에다가 hashmap에서 키값이 arr_v인 value를 붙여준다.(append)
6. sb.toString()을 출력한다.

>전체 코드

import java.util.*;

public class Main {
	
	public static void main(String [] args) {
		int N, before, arr[], arr_v[];
		
		Scanner scan= new Scanner(System.in);
		
                //입력받기
		N= scan.nextInt();
		arr= new int[N];
		arr_v= new int[N];
		HashMap<Integer, Integer> map= new HashMap<>();
		
		for(int i=0; i<N; i++) {
			arr[i]= scan.nextInt();
		}
        
		arr_v= arr.clone(); //arr를 arr_v로 (깊은)복사
		Arrays.sort(arr); //정렬
		
		before= (int)Math.pow(10, 9)+1;
		for(int i=0, j=0; i<N; i++) {
			if(before!=arr[i]) { //중복아닌 값만
				map.put(arr[i], j++);//map에 저장
				before=arr[i];
			}
		}
		
		StringBuilder sb= new StringBuilder();
		for(int i=0; i<N; i++) {
			sb.append(map.get(arr_v[i])+" "); //arr_v값을 키로 가진 map을 get
		}
		System.out.println(sb.toString()); //출력~~
		
    }//end	
}

https://www.acmicpc.net/problem/18870