[TIL/04.10] Algorithm: 정렬 (Java)

1. 문제

문자열로 구성된 리스트 strings와 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다.

예를 들어 strings가 ["sun", "bed", "car"]이고 n이 1이면 각 단어의 인덱스 1의 문자 "u", "e", "a"로 strings를 정렬합니다.

 

제한 조건

1. strings는 길이 1이상, 50이하인 배열입니다.

2. strings의 원소는 소문자 알파벳으로 이루어져 있습니다.

3. strings의 원소는 길이 1이상, 100이하인 문자열입니다.

4. 모든 strings의 원소의 길이는 n보다 큽니다.

5. 인덱스 1의 문자가 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치합니다.

 

입출력 예

strings	n	return
"sun", "bed", "car"]	1	["car", "bed", "sun"]
["abce", "abcd", "cdx"]	2	["abcd", "abce", "cdx"]

 

 

2. 코드

import java.util.*;

class Solution {
    public String[] solution(String[] strings, int n) {
        // n번째 문자가 같다면: 사전순 오름차순
        // 다르다면: n번째 문자 기준 오름차순 
        Arrays.sort(strings, 
                    (o1, o2) -> o1.charAt(n) == o2.charAt(n) ?
                   o1.compareTo(o2): Character.compare(o1.charAt(n), o2.charAt(n)));
        return strings; 
    }
}

 

3. 체크 포인트

✅ Arrays.sort(배열, (s1, s2) -> {...}) : 람다식을 활용하여 정렬의 기준을 재정의

 

---

1. 문제

함수 solution은 정수 n을 매개변수로 입력받습니다. n의 각 자릿수를 큰것부터 작은 순으로 정렬한 새로운 정수를 리턴해주세요. 예를들어 n이 118372면 873211을 리턴하면 됩니다.

---

✅ 제한 조건

• n은 1이상 8000000000 이하인 자연수입니다.

---

📖 입출력 예

118372

873211

 

2. 코드

import java.util.*;

class Solution {
    public long solution(long n) {
        // 정수 -> 문자열 변환 
        String[] digits = Long.toString(n).split("");
        
        // 내림차순 정렬
        Arrays.sort(digits, Collections.reverseOrder());
        
        // 정렬된 숫자 -> 하나의 문자열 변환
        StringBuilder sb = new StringBuilder();
        for(String digit : digits){
            sb.append(digit);
        }
        
        return Long.parseLong(sb.toString());
        
    }
}

3. 체크 포인트

✅ 정수 -> 문자열 변환

✅ 정렬된 숫자 -> 문자열 변환

✅ 마지막에 StringBuilder 타입 String으로 변환 후 Long으로 변환 

 

---

1. 문제

배열 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 함수를 작성해 주세요.

 

제한사항

• array의 길이는 1 이상 100 이하입니다.
• array의 각 원소는 1 이상 100 이하입니다.
• commands의 길이는 1 이상 50 이하입니다.
• commands의 각 원소는 길이가 3입니다.

입출력 예

array	commands	return
[1, 5, 2, 6, 3, 7, 4]	[[2, 5, 3], [4, 4, 1], [1, 7, 3]]	[5, 6, 3]

 

 

2. 코드

import java.util.*;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        ArrayList<Integer> answerlist = new ArrayList<>(); // 리스트 

        int[] answer = {}; // 배열 
        
        // i부터 j까지 자르기
        for(int i = 0; i < commands.length; i ++){
            ArrayList<Integer> list = new ArrayList<>(); // 리스트 

            for(int j = commands[i][0] -1; j < commands[i][1]; j++){
                if(j >= 0 && j < array.length) {
                    list.add(array[j]);} 
            }
            
            Integer[] arr = list.toArray(new Integer[0]); // Integer 배열로 변환
            Arrays.sort(arr);
            
            if(commands[i][2] - 1 < list.size() && commands[i][2] - 1 >= 0) { // 배열의 범위 내에 있는지 확인
                answerlist.add(arr[commands[i][2] - 1]);
            } else {
                answerlist.add(-1); // 범위를 벗어나면 -1 추가
            }
        }
        // 리스트 -> 배열 변환 (주의: Integer -> Int 변환 필요 )
        answer = answerlist.stream().mapToInt(Integer::intValue).toArray();
        
        return answer;
    }
}

 

➤ 슬라이싱을 이용할 경우 ver

import java.util.*;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length]; 
        
        for (int c = 0; c < commands.length; c++){
            int i = commands[c][0];
            int j = commands[c][1];
            int k = commands[c][2];
            
            // i~j 슬라이싱
            int[] arr = Arrays.copyOfRange(array, i-1, j);
            
            // 배열 정렬
            Arrays.sort(arr);
            
            // k번째 원소 구하기
            answer[c] = arr[k-1];
        }
        return answer; 
        
        
    }
}