프로그래머스 고득점 Kit 하루만에 뽀개기 - 4. 정렬(Java, C++) 풀이

https://programmers.co.kr/learn/courses/30/parts/12198

프로그래머스

- 알고리즘 풀이로 C++를 주로 사용하다가 기업 코딩테스트를 위해 java 풀이를 학습하는 사람에게 도움이 될만한 포스트입니다. 알고리즘 적인 해설내용은 줄이고 C++에 익숙한 사람들이 Java 사용시 놓칠만한 내용 위주로 작성하고 있습니다.

1.  K번째 수

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

코딩테스트 연습 - K번째수

- command에 따라서 array를 자르고, 정렬해서 k번째 수를 계속해서 구해준다

// C++
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> solution(vector<int> array, vector<vector<int> > commands) {
    vector<int> ans;
    for (auto command : commands) {  // command -> i,j,k
        int i = command[0] - 1;
        int j = command[1] - 1;
        int k = command[2] - 1;
        vector<int> v(array.begin() + i, array.begin() + j + 1);
        sort(v.begin(), v.end());
        ans.push_back(v[k]);
    }
    return ans;
}

// java
import java.util.*;

class Solution {
    public List<Integer> solution(int[] array, int[][] commands) {
        List<Integer> ans = new ArrayList<>();
        for(int[] cmd: commands) { // i, j, k
            int i = cmd[0] - 1;
            int j = cmd[1] - 1;
            int k = cmd[2] - 1;
            int[] arr = Arrays.copyOfRange(array, i, j + 1);
            Arrays.sort(arr);
            ans.add(arr[k]);
        }
        return ans;
    }
}

- Arrays 클래스에는 배열의 정렬, 탐색 등 배열 조작을 위한 다양한 메서드들이 있고 또한 array -> list로 변환하는 정적 팩토리 메서드들이 있다. 그런데 Arrays.asList()를 사용할 때 주의할 점이 있는데, fixed-size list를 반환하기 때문에 초기화된 리스트에 원소를 추가,제거하거나 크기를 변경할 수 없다. 

https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/Arrays.html#copyOfRange(T%5B%5D,int,int)

- copyOfRange()를 사용해서 특정 범위에 대한 배열을 새로 선언해주고 정렬하여 K번째 값을 조회하였다.

https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/Arrays.html#copyOfRange(T%5B%5D,int,int)

 

2. 가장 큰 수

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

코딩테스트 연습 - 가장 큰 수

- 정수를 이어붙였을 때, 맨 앞에는 최대한 큰 한자리 정수값이 있어야 된다. numbers의 원소는 0~1000이하이니 char 단위로 정렬할 수 는 없고, 앞뒤 정수문자열을 이어붙였을 때 더 큰 값이 오도록 내림차순 정렬을 해준다. 예외케이스가 있는데 이렇게 정수문자열을 정렬해서 이어붙였는데, 맨 앞자리가 0이라면 나머지 숫자들도 0일 것이므로 "0000...00" 문자열을 반환하게 된다. "0"을 반환해야 한다

// C++
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string solution(vector<int> numbers) {
    vector<string> nums;
    for(int n: numbers) {
        nums.push_back(to_string(n));
    }
    sort(nums.begin(), nums.end(), [](string a, string b) {
        return a + b > b + a;
    });
    
    if(nums[0][0] == '0') return "0";
    string ans;
    for(string s: nums) {
        ans += s;
    }
    return ans;
}

// java
import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        int N = numbers.length;
        String[] nums = Arrays.stream(numbers).mapToObj(Integer::toString).toArray(String[]::new);
        Arrays.sort(nums, (String s1, String s2) -> (s2+s1).compareTo(s1+s2)); 
        
        if(nums[0].startsWith("0")) return "0";
        return String.join("", nums);
    }
}

- Arrays.stream의 맵핑으로 변환을 했는데, for문을 돌면서 Integer.toString()를 사용해도 된다. 

- s1.compareTo(String s2)는 두 문자열을 사전순서로 비교하여 -, 0, +을 반환한다

https://docs.oracle.com/javase/8/docs/api/java/lang/String.html

- String.join()은 CharSequence를 사이에 delimiter를 삽입하여 합친 String을 반환한다. delimiter가 ""이므로 그냥 합쳐서 반환한다.

https://docs.oracle.com/javase/8/docs/api/java/lang/String.html#compareTo-java.lang.String-

 

3. H-Index

https://programmers.co.kr/learn/courses/30/lessons/42747?language=java 

코딩테스트 연습 - H-Index

- citations 배열의 길이가 최대 1000이므로 전체를 순회하면서 각 인덱스마다 h-index의 조건을 만족하는지 검사한다. 

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        int N = citations.length;
        Arrays.sort(citations); // 0 1 3 5 6
        
        for(int i = 0; i < N; ++i) {
            int h = N - i;
            if(citations[i] >= h) return h;
        }
        return 0;
    }
}