이 남성은 열심히 개발합니다.

문제

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

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

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

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

나의 코드

import java.util.*;

public class LargestNumber {
	
	public static String solution(int[] numbers) {
        String answer = "";
        String[] arr = new String[numbers.length];
        for(int i=0; i<arr.length; i++) {
        	arr[i] = numbers[i]+"";
        }
        Arrays.sort(arr, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));
        if(arr[0] == "0") return "0";
        for(String ans : arr) {
        	answer+=ans;
        }
        return answer;
    }
}

나의 풀이

처음 접근을 잘못했던 문제다....

예를 들어 3과 32 , 3과 34 를 int로 비교하려니까 10으로 나머지 구하고 몫 구하고 아주 난리가 났었다.

이건 백퍼 시간초과 느낌이어서 정렬 문제는 시간 복잡도가 O(n log n) 안으로 해결해야되기 때문에 다시 생각했다.

그래서 얻은 힌트 String값 비교

1. 먼저 새로운 String array를 numbers의 크기로 할당한다.

2. for문을 통해서 +""를 한 String값을 array에 넣는다.

3. Arrays.sort 를 통해 o1, o2를 더한 값으로 비교를 한다. (이유는 3과 32를 비교했을 때 3을 우선순위에 놔야 하기 때문)

4. 정렬된 수 중 첫번째 인덱스가 0이면 결국은 0이라는 것이라서 return 0

5. for문을 통해 arr에 저장된 값을 answer에 +=로 저장한다.

6. answer return

문제

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어수신 탑(높이)

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

제한사항

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
• operations의 원소는 큐가 수행할 연산을 나타냅니다.
  • 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

나의 코드

import java.util.*;

public class DoublePriorityQueue {
	
	public static int[] solution(String[] operations) {
        int[] answer = new int[2];
       
        PriorityQueue<Integer> dpq = new PriorityQueue<>(Comparator.reverseOrder());
        String change = "";
        for(String s : operations) {
        	if(s.contains("I")) {
        		change = s.replace("I ", "");
        		dpq.offer(Integer.parseInt(change));
        	}else if(s.contains("D")) {
        		change = s.replace("D ", "");
        		if(change.equals("1")) {
        			dpq.poll();
        		}else if(change.equals("-1")) {
        			dpq = removelast(dpq);
        		}
        	}
        }
        System.out.println(dpq);
        if(dpq.size() > 1) {
        	answer[0] = dpq.poll();
        	answer[1] = lastIndex(dpq);
        }
        return answer;
    }
	
	
	public static PriorityQueue<Integer> removelast(PriorityQueue<Integer> dpq) {
	    PriorityQueue<Integer> pqnew = new PriorityQueue<Integer>(Comparator.reverseOrder());
	    while(dpq.size() > 1) {
	        pqnew.add(dpq.poll());
	    }
	    dpq.clear();
	    return pqnew;
	}
	
	public static int lastIndex(PriorityQueue<Integer> dpq) {
		while(dpq.size() > 1) {
			dpq.poll();
		}
		return dpq.poll();
	}
}

나의 풀이

우선 문제가 이중우선순위큐다. 이걸 문제 풀고 다시 생각해보니까 최소큐, 최대큐을 구현해서 하는게 맞는 것 같은데 다 풀고 알았으니..

기회가 된다면 이중우선순위큐를 구현해서 해결해보자.

1. 우선 solution method 제외 두 개의 method를 더 구현했다. 어떤 건지 알아보자.

2. 첫번째 removelast(PriorityQueue<Integer>) 인자로 PriorityQueue를 넘기면 while문을 통해 마지막 값을 삭제한 queue를 return

3. 두번째 lastIndex(PriorityQueue<Integer>) 인자로 받은 PriorityQueue의 마지막 Integer값을 return

4. 본격 soultion method 는 우선 answer array의 크기를 2로 할당한다.

5. String change 변수는 문제에서 주어진 입력되는 인자 값에서 명령 스트링을 제거한 값을 저장한다.

6. 만약 I가 들어가 있다면 "I " 를 공백으로 replace 시켜주고 남은 값을 Integer로 변환시켜 queue에 저장한다.

7. 만약 D가 들어가 있다면 "D "를 공백하로 replace 시켜준다.

8. 7에서 replace한 값이 "1"이라면 우선순위 큐에서 최댓값을 하나 제거한다. (큐를 생성할 때 Comparator.reverseOrder를 이용함)

9. 7에서 replace한 값이 "-1" 이라면 2에서 구현한 메서드(removelast)를 통해 최솟값을 하나 제거한다.

10. 여기서 for문이 끝나며 만약 우선순위큐의 사이즈가 1보다 크다면 answer[0]에는 최댓값을 넣는다.

11. answer[1] 에는 3에서 구현한 lastIndex를 통해 최솟값을 넣는다.

12. 그리고 return

문제

라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다.

해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다.

현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 return 하도록 solution 함수를 완성하세요.

dates[i]에는 i번째 공급 가능일이 들어있으며, supplies[i]에는 dates[i] 날짜에 공급 가능한 밀가루 수량이 들어 있습니다.

제한사항

• stock에 있는 밀가루는 오늘(0일 이후)부터 사용됩니다.
• stock과 k는 2 이상 100,000 이하입니다.
• dates의 각 원소는 1 이상 k 이하입니다.
• supplies의 각 원소는 1 이상 1,000 이하입니다.
• dates와 supplies의 길이는 1 이상 20,000 이하입니다.
• k일 째에는 밀가루가 충분히 공급되기 때문에 k-1일에 사용할 수량까지만 확보하면 됩니다.
• dates에 들어있는 날짜는 오름차순 정렬되어 있습니다.
• dates에 들어있는 날짜에 공급되는 밀가루는 작업 시작 전 새벽에 공급되는 것을 기준으로 합니다. 예를 들어 9일째에 밀가루가 바닥나더라도, 10일째에 공급받으면 10일째에는 공장을 운영할 수 있습니다.
• 밀가루가 바닥나는 경우는 주어지지 않습니다.

나의 코드

import java.util.*;

class Solution {

    public int solution(int stock, int[] dates, int[] supplies, int k) {
        int answer = 0;
        PriorityQueue<Integer> facQ = new PriorityQueue<Integer>(Comparator.reverseOrder());
        int in = 0;
        for(int i=0; i<k; i++) {
        	if(in<dates.length && i==dates[in]) {
        		facQ.offer(supplies[in]);
        		in++;
        	}
        	if(stock == 0) {
        		stock+=facQ.poll();
        		answer++;
        	}
        	stock--;
        }
        return answer;
    }
}

나의 풀이

처음엔 힙을 왜써야하는지 몰라서 우선 리스트로 구현해봤는데 코드가 길어질 뿐 예외사항을 생각할것이 너무 많았다.

시간이 너무 오래걸려 구글링의 힘을 빌렸다. 그렇게 찾은 것이 PriorityQueue

전체적인 흐름은 밀가루가 떨어지지 않는 한 받을 수 있는 밀가루를 다 받고 제일 큰 값부터 구매한다.

1. 우선순위 큐(PriorityQueue) facQ 를 선언한다. Comparator.reverseOrder 를 이용해 내림차순 정렬이 되도록 한다. (MinimumHeap)

2. supplies의 인덱스를 저장할 int in 변수 선언

3. k(원래 구매하던 밀가루 공장이 재가동 할때 까지 남은 기간) 만큼 for문을 돌린다.

4. 만약 in이 dates의 길이보다 작고 i가 dates의 in번째의 값과 같다면

5. facQ에 supplies의 in 번째 값을 넣고, in에 1을 더해준다.

6. 만약 stock이 0이되면 stock에 facQ의 가장 큰 값을 더하면서 answer에 1을 더해준다.

7. stock은 for문이 한번 돌때 마다 계속 1씩 감소시킨다.

8. answer return

문제

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

나의 코드

import java.util.*;

public class MoreSpicy {
	
	 public static int solution(int[] scoville, int K) {
	        int answer = 0;
	        Heap h = new Heap();
	        for(int m : scoville) {
	        	h.insert(m);
	        }
	        
	        while(true) {
	        	int com = h.delete();
	        	if(h.heapSize()==1 && com<K) {
	        		return -1;
	        	}
	        	if(com < K) {	
	        		answer++;
	        		h.insert(com+(h.delete()*2));
	        	}else {
	        		break;
	        	}
	        }
	        return answer;
	    }
}

class Heap {	//MinimumHeap 
    List<Integer> heap;

    public Heap() {
        heap = new ArrayList<Integer>();
        heap.add(0);
    }
    public int heapSize() {
    	return heap.size();
    }
    public void insert(int n) {
        heap.add(n);
        int p = heap.size() - 1;
        while (p < 1 || heap.get(p / 2) > heap.get(p)) {
            // 부모노드와 자식 노드의 값 교환
            int tmp = heap.get(p / 2);
            heap.set(p / 2, heap.get(p));
            heap.set(p, tmp);
            p = p / 2;
        }
    }
    public int delete() {
        if (heap.size() <= 1)
            return 0;
        int deleteItem = heap.get(1); // 삭제할 노드 = 루트노드

        heap.set(1, heap.get(heap.size() - 1));
        heap.remove(heap.size() - 1);

        int pos = 1;
        while ((pos * 2) < heap.size()) {
            int min = heap.get(pos * 2);
            int minPos = pos * 2;

            if (((pos * 2 + 1) < heap.size()) && min > heap.get(pos * 2 + 1)) {
                min = heap.get(pos * 2 + 1);
                minPos = pos * 2 + 1;
            }
            if (heap.get(pos) < min)
                break;
            // 부모노드 자식노드 교환
            int tmp = heap.get(pos);
            heap.set(pos, heap.get(minPos));
            heap.set(minPos, tmp);
            pos = minPos;
        }
        return deleteItem;
    }
}

나의 풀이

1. 먼저 최소 힙을 구현한다.

2. 구현한 Heap의 메서드는 총 3개 ( insert, delete, heapSize )

1. 생성자 : Heap은 트리구조를 구성하기 위해 첫 번째 값에 인덱스 0에 먼저 값을 채워 넣어 인덱스가 1부터 시작할 수 있게 한다.
2. insert : 리스트에 insert인자로 들어온 값을 추가한다. while문을 통해 부모노드보다 작게 되면 부모 노드와 자식 노드를 교환
3. delete : 사이즈가 1이하면 리스트에 값이 없다는 것이기 때문에 return 0 , 아니라면 삭제한 값 리턴,  최솟값을 삭제하며 노드의 구성을     재배치
4. heapSize : 리스트의 사이즈를 리턴한다.

3. for문을 통해 주어진 맵기의 배열을 heap에 추가시킨다.

4. 먼저 무한 루프를 돌린다.

5. 힙의 첫번째 값을 삭제하며 int com에 저장한다.

6. 힙의 사이즈가 1(리스트가 비었음)이고, 첫 번째 값이 원하는 맵기보다 작다면 -1 return

7. 만약 삭제한 값이 원하는 맵기보다 작으면 한번 섞으면서 answer++

8. 그게 아니라면(삭제한 값이 원하는 맵기보다 크면) break;

9. answer를 리턴한다.