K번째 수
문제의 조건을 살펴보면,
array 배열을 i부터 j까지 자른다. 위에서 나온 배열을 오름차순으로 정렬한다 k번째 수를 리턴한다.
고려해야할 사항
우리들은 보통 2부터 5까지라고 하면 2, 3, 4, 5라는 숫자를 생각한다. 하지만 컴퓨터는 0부터 시작한다는 것 배열을 기준으로 생각한다면 인덱스 1부터 4까지 인 것이다. for문은 start 이상 last미만이다. 즉, start≤=범위<last문제풀이 1 - 복사하는 배열을 활용하여 배열을 잘라본다.
public class NumberOfKth {
public int[] solution(int[] array, int[][] commands) {
// 1번
int[] answer = new int[commands.length];
int idx = 0;
// 2번
for (int[] command : commands) {
int[] arr = Arrays.copyOfRange(array, command[0] - 1, command[1]);
Arrays.sort(arr);
// 3번
answer[idx++] = arr[command[2] - 1];
}
return answer;
}
}
Java
복사
1.
우리에게 요청이 온 답을 담은 공간인 answer의 개수는 commands의 길이만큼이다.
2.
이차원배열 commands를 for문으로 꺼내어 일차원배열 arr을 만들고, 요구한 범위만큼 자르고 오름차순으로 정렬한다.
a.
시작점은 command[0]-1 —> 컴퓨터는 0부터 시작하고 시작부터이기 때문
b.
마지막점은 commands[1] —> 미만이기 때문
3.
요청이 온 순서대로 자른 배열의 k번째 수를 answer 배열에 담는다.
시간복잡도를 생각해보자.
문제풀이 2 - 우선순위 큐 활용
public int numberOfKth(int[] array, int[] command) {
// 1번
int start = command[0]-1;
int last = command[1];
int kth = command[2];
int rst = 0;
// 2번
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = start; i < last; i++) {
pq.add(array[i]);
}
for (int i = 0; i < kth; i++) {
rst = pq.poll();
}
return rst;
}
public int[] solutionV2(int[] array, int[][] commands) {
int[] answer = new int[commands.length];
// 3번
for (int i = 0; i < commands.length; i++) {
answer[i] = numberOfKth(array, commands[i]);
}
return answer;
}
Java
복사
1.
시작점, 마지막점, k번째수, 결과값을 사용하기 위해 변수 선언 후 초기화 한다.
2.
우선순위 큐를 만들고 시작점부터 마지막점미만 까지의 숫자를 넣는다.(단, 값이 들어갈 때 낮은 숫자가 우선순위로 들어간다.)
3.
numberOfKth() 메서드를 통해 나온 값을 순서대로 answer값에 넣는다.
Priority Queue?
PriorityQueue란 우선순위 큐로써 일반적인 큐의 구조 FIFO(First In First Out)를 가지면서, 데이터가 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 데이터가 먼저 나가는 자료구조이다.제네릭를 사용한 인터페이스이기에 객체 타입을 정해두어야 한다.PriorityQueue는 Heap을 이용하여 구현하는 것이 일반적이다.Priority Queue 메서드
// 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueueLowest.poll();
// 첫번째 값 제거 비어있다면 예외 발생
priorityQueueLowest.remove();
// 첫번째 값을 반환만 하고 제거 하지는 않는다.
// 큐가 비어있다면 null을 반환
priorityQueueLowest.peek();
// 첫번째 값을 반환만 하고 제거 하지는 않는다.
// 큐가 비어있다면 예외 발생
priorityQueueLowest.element();
// 초기화
priorityQueueLowest.clear();
Java
복사
시간복잡도를 생각해보자.
가장 큰 수
제한 사항
numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다. 풀이 1 (Comparator)
package com.likelion.programmers;
import java.util.Arrays;
import java.util.Comparator;
public class Solution{
public String solution(int[] numbers) {
String[] arr = new String[numbers.length];
for (int i = 0; i < arr.length; i++) {
arr[i] = String.valueOf(numbers[i]);
}
Arrays.sort(arr, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return ((o2+o1).compareTo(o1+o2));
}
});
if(arr[0].equals("0")) {
return "0";
}
String answer = "";
for(String str:arr) {
answer += str;
}
return answer;
}
}
Java
복사
풀이 방법 실행 결과 풀이 2 (람다식을 이용한 Comparator)
import java.util.Arrays;
public class Solution {
public String solution(int[] numbers) {
String answer = "";
String[] stringList = new String[numbers.length];
for (int i = 0; i < numbers.length; i++) {
stringList[i] = String.valueOf(numbers[i]);
}
Arrays.sort(stringList, (first, next) -> {
return (first + next).compareTo(next + first);
});
for (int i = numbers.length-1; i >= 0; i--) {
answer += stringList[i];
}
if (answer.charAt(0) == '0') {
answer = "0";
}
return answer;
}
}
Java
복사
풀이 방법 실행 결과 Comparator란?
java.util 패키지에 존재하기 때문에 반드시 import를 해주어야 한다. 순서를 부과하는 비교함수로, Collection이나 배열의 정렬 메서드인 .sort() 를 사용하여 정렬 순서를 제어할 수 있다. Comparator를 사용할 때에는 compare(T o1, T o2)를 반드시 구현하여야 한다. 2개의 매개변수를 비교하여 정렬 ( 펼쳐보기) Comparable과 달리, Comparator는 동일한 타입의 자료형의 데이터를 비교하고 정렬한다.