Algorithm

[PCCP] 스택 · 큐 · 정렬 · 그리디 알고리즘 [3]

Uykm 2023. 8. 10. 17:59

▼ Why ?

이번엔 최근까지 공부했던 정렬(sort)과 람다식을 활용해보고자 정렬과 관련된 문제를 풀어보려고 한다.

▼ 이진수 정렬

 

문제 정보

매개변수 nums에 숫자가 주어지면 nums의 원소들을 이진수로 변환했을 때 1의 개수가 적은 것부터 많은 것 순으로 정렬하여 반환하는 프로그램을 작성하세요.

만약 nums = [5, 6, 7, 8, 9]이고 이 원소들을 이진수로 변환하면

  • 5 --> 101 : 1이 2개
  • 6 --> 110 : 1이 2개
  • 7 --> 111 : 1이 3개
  • 8 --> 1000 : 1이 1개 9 --> 1001 : 1이 2개

이고, 이 수들을 이진수에서 1의 개수에 의해 오름차순 정렬하면 [8, 5, 6, 9, 7]이다.

위에 5, 6, 9는 이진수로 변환했을 때 1의 개수가 2개로 동일하면 십진수가 작은순(오름차순) 으로 정렬합니다.

 

제한사항

  • nums의 길이는 1,000을 넘지 않습니다.
  • 1 <= nums[i] <= 100,000

 

입출력 예

 

어떻게 해결해야 할까 ?

  1. 먼저 십진수를 이진수로 변환했을 때의 1의 개수를 각 행(row; 매개변수로 주어진 숫자들)의 첫 번째 index 요소로, 원래의 십진수를 두 번째 index 요소로 저장하는 2차원 배열을 생성해준다
  2. 단, 이진수로 변환할 때 마지막에 몫이 1이 되는 경우도 빼먹지 말고 이진수로 변환했을 때의 1의 개수에 포함해서 생각하자
    ( while(num > 1) ➜ while(num > 0) )
  3. 그리고  ' Arrays.sort() '메서드를 사용해서 첫 번째 index 요소를 x값, 두 번째 index 요소를 y값이라 했을 때 x값을 기준으로 정렬을 해주고 x값이 같을 시에 y값을 기준으로 정렬하게 코드를 작성해주면 될 것 같다

 

해결 코드 0

import java.util.*;

class Solution {
    public int[] solution(int[] nums) {
        int[][] binaryDecimal = new int[nums.length][2];
        
        for(int i = 0; i < nums.length; i++) {
            int num = nums[i];
            binaryDecimal[i][1] = num;
            
            int oneCnt = 0; // 이진수로 변환했을 때 1의 개수
            
            while(num > 0) {
                oneCnt += num % 2; 
                num /= 2;
            }
            
            binaryDecimal[i][0] = oneCnt;
        }
        
        Arrays.sort(binaryDecimal, (num1, num2) -> num1[0] == num2[0] ? num1[1] - num2[1] : num1[0] - num2[0]);
        
        int[] answer = new int[nums.length];
        
        for(int i = 0; i < answer.length; i++)
            answer[i] = binaryDecimal[i][1];
        
        return answer;
    }
}

 

해결 코드 1

  • 굳이 이렇게까지 할 필요는 없지만, 며칠 전에 공부한 stream을 활용해보기도 할 겸 향상된 for문을 사용해 배열 ' binaryDecimal ' 에 값을 저장하는 방식으로도 코드를 수정해봤다
    ( ' indexOf() ' 메서드를 사용하기 위해 Collections class 타입으로 변환하였다 )
import java.util.*;
import java.stream.Stream;

public int[] solution(int[] nums) {
    ArrayList<Integer> numsList = (ArrayList<Integer>) Arrays.stream(nums)
            .boxed()
            .collect(Collectors.toList());

    int[][] binaryDecimal = new int[nums.length][2];

    for(int num : nums) {
        int tmp = num;
        binaryDecimal[numsList.indexOf(num)][1] = tmp;

        int oneCnt = 0; // 이진수로 변환했을 때 1의 개수

        while(tmp > 0) {
            oneCnt += tmp % 2;
            tmp /= 2;
        }
            
        binaryDecimal[numsList.indexOf(num)][0] = oneCnt;
    }

    Arrays.sort(binaryDecimal, (num1, num2) -> num1[0] == num2[0] ? num1[1] - num2[1] : num1[0] - num2[0]);

    int[] answer = new int[nums.length];

    for(int i = 0; i < answer.length; i++)
        answer[i] = binaryDecimal[i][1];

    return answer;
}

 

▼ 정리

 

  • Comparator class를 직접 구현(' compare() ')하는 대신에 람다식을 이용해서 ' Arrays.sort ' 에 비교기준을 제공하는 방식으로 배열을 정렬시켜봤다 ( x값에 의한 오름차순 정을 하되 x값이 같은 경우엔 y값에 따라 오름차순으로 정렬 )

  • 원래 기본 정렬(오름차순)이 아닌 특별한 정렬 기준으로 정렬해야 할 때엔, 기본형 배열에 ' Arrays.sort() ' 를 사용할 수 없어 Wrapper class 타입으로 변환시키고 정렬해야 하지만, 위와 같이 2차원 배열은 기본형이더라도 ' Arrays.sort() ' 이 매개변수에 정렬 방법(Comparator or 람다식)을 제공해준다면 가능하다는 것을 기억하자 !

  • 배열을 stream을 이용해 Collections class 타입으로 변환시킨 방법을 기억해두면 좋을 것 같다