프로그래머스 코딩테스트 고득점 Kit - 정렬(K번째수, 가장 큰 수, H-Index)

1번 문제: K번째

https://school.programmers.co.kr/learn/courses/30/lessons/42748

프로그래머스

풀이

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구해야 한다.
예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

1. array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]이다.
2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]이다.
3. 2에서 나온 배열의 3번째 숫자는 5이다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해야 한다.

접근

문제의 설명과 동일하게 접근하면 된다. i번째부터 j번째까지 자를 때는 Arrays.copyOfRange를, 정렬할 때 Arrays.sort를 사용한다.

코드

import java.util.*;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        for (int i = 0; i < commands.length; i++) {
            int[] command = commands[i];
            int start = command[0] - 1, end = command[1], k = command[2] - 1;
            int[] arr = Arrays.copyOfRange(array, start, end);
            Arrays.sort(arr);
            answer[i] = arr[k];
        }
        return answer;
    }
}

---

2번 문제: 가장 큰 수

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

프로그래머스

풀이

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내야 한다. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210이다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해야 한다.

접근

먼저 주어진 numbers 배열을 String[] 타입으로 바꾼다. 그리고 Arrays.sort에 커스텀 비교 로직을 적용하기 위한 Comparator를 사용한다. 커스텀 비교 로직의 규칙은 아래와 같다.

• 문자열 o1과 o2를 연결하여 (o1 + o2)와 (o2 + o1)을 비교한다.
  • 예를 들어 o1 = "9", o2 = "34"라면,
    • o1 + o2 = "934", o2 + o1 = "349"
    • 934 > 349이므로, o1이 o2보다 앞에 와야 한다.

이렇게 정렬된 배열을 맨 뒤부터 거꾸로 순회하면서 이어붙여 문자열을 만들고, 결과 문자열이 "000..."처럼 모든 값이 0일 때를 처리하기 위해 java.math.BigInteger를 사용한다.

코드

import java.math.BigInteger;
import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        String[] arr = new String[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            arr[i] = Integer.toString(numbers[i]);
        }
        Arrays.sort(arr, (o1, o2) -> (o1 + o2).compareTo(o2 + o1));
        StringBuilder sb = new StringBuilder();
        for (int i = arr.length - 1; i >= 0; i--) {
            sb.append(arr[i]);
        }
        return new BigInteger(sb.toString()).toString();
    }
}

---

3번 문제: H-Index

https://school.programmers.co.kr/learn/courses/30/lessons/42747

프로그래머스

풀이

위키백과에 따르면, H-Index는 다음과 같이 구한다.

• 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index이다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해야 한다.

접근

citations 배열은 발표한 논문의 인용 횟수를 담은 배열이기 때문에 이를 오름차순으로 정렬한다.

그리고 h는 citations.length부터 시작해서 점점 줄어들며 앞에서부터 값을 비교해간다.

예를 들어 n이 4이고 정렬된 citations 배열의 값이 [1, 3, 3, 4]라면 0부터 시작한 i가 1일 때 citations[i] = 3, h = n - i = 4 - 1 = 3이므로 둘을 비교했을 때 citations[i]의 값이 h 이상이므로 H-Index가 될 수 있다. 이때 H-Index는 h값 중 최댓값이므로 점점 줄어드는 h값 중 처음 만난 h값이 가장 큰 값이 되므로 이를 return하면 된다.

코드

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        Arrays.sort(citations);
        int answer = 0, n = citations.length;
        for (int i = 0; i < n; i++) {
            int citation = citations[i], h = n - i;
            if (citation >= h) {
                answer = h;
                break;
            }
        }
        return answer;
    }
}

---

결론

정렬 파트는 백준에서 푼 문제들처럼 직접 정렬 알고리즘을 짜야 성공할 수 있는.. 그런 문제인 줄 알았는데 그냥 정렬 알고리즘의 활용 그 자체를 따지는 문제들이었어서 개인적으로 마음에 들었다. 아무튼 이번에도 3문제를 한 번에 다 작성했는데 그 다음 파트부터 문제가 많이 보여서.. 다음은 진짜로 한 문제당 하나의 글이 작성되지 않을까? 물론 너무 쉬운 문제는 패스하고..