[구름톤 챌린지] 알고리즘 챌린지 1주차 마지막 학습일기

[ 목차 ]

1. ☁️ 구름톤 챌린지 문제 (이진수 정렬)

2. 📝 이진수 정렬 풀이

3. 🧐 느낀점

 

☁️ 구름톤 챌린지 문제 (이진수 정렬)

N개의 10진수 정수가 주어진다. 플레이어가 정수를 그냥 정렬하는 것은 너무 쉽기 때문에, 아래 기준에 따라 정수를 정렬하기로 한다.

1.. 10진수 정수를 2진수로 나타냈을 때, 2진수에 포함된 1의 개수를 기준으로 내림차순 정렬한다.

2. 1의 개수가 같다면, 원래 10진수를 기준으로 내림차순 정렬한다.

 

📝 이진수 정렬 풀이

우선, 주어진 기준으로 정렬할 수 있도록 순위를 결정 짓는 공식을 작성해야합니다.

이때 저는 우선순위 큐를 사용해 값을 넣을때마다 정렬 할 수 있도록 했습니다. List를 사용해도 되지만 List에 넣고, Sort하는 메소드를 호출해야되서 PriorityQueue를 선택했습니다.

 

우선순위 큐

우선순위 큐에서 어떤 방식을 기준으로 정렬할 것인지 명시해줬습니다.

우선 a와b를 기준으로 이진수로 변경했을때 나오는 1의 개수를 모두 세어준 뒤 1의 개수가 큰 순서대로 내림차순 정렬해줬습니다.

만약 binaryA와 binaryB 이진수로 변경했을때 나오는 1의 개수가 같으면 10진수 기준으로 내림차순 해줬습니다.

Queue<Integer> priorityQueue = new PriorityQueue<>((a, b) -> {
    int binaryA = 0;
    int binaryB = 0;

    int compareA = a;
    while (compareA != 0) {
        if (compareA % 2 == 1) {
            binaryA++;
        }
        compareA /= 2;
    }

    int compareB = b;
    while (compareB != 0) {
        if (compareB % 2 == 1) {
            binaryB++;
        }
        compareB /= 2;
    }

    if (binaryA == binaryB) return b - a;
    return binaryB - binaryA;
});

 

입력받은 순서의 값 찾기

우선순위 큐에 값을 하나씩 꺼내서 target 값이 원했던 순서와 같으면 그 값을 return 해주는 것으로 정답을 호출했습니다.

int target = 1;
while (!priorityQueue.isEmpty()) {
    int cur = priorityQueue.poll();
    if (target == input[1]) {
        return cur;
    }
    target++;
}

 

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 이진수 정렬 (195687)
 * 14'27"
 */
public class Solution {

    public static void main(String[] args) throws Exception {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            System.out.print(solution(reader));
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    static int solution(BufferedReader br) throws IOException {
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] nums = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        
        return sortedBinary(input, nums);
    }

    private static Integer sortedBinary(int[] input, int[] nums) {
        Queue<Integer> priorityQueue = new PriorityQueue<>((a, b) -> {
            int binaryA = 0;
            int binaryB = 0;

            int compareA = a;
            while (compareA != 0) {
                if (compareA % 2 == 1) {
                    binaryA++;
                }
                compareA /= 2;
            }

            int compareB = b;
            while (compareB != 0) {
                if (compareB % 2 == 1) {
                    binaryB++;
                }
                compareB /= 2;
            }

            if (binaryA == binaryB) return b - a;
            return binaryB - binaryA;
        });

        for (int num : nums) {
            priorityQueue.offer(num);
        }

        int target = 1;
        while (!priorityQueue.isEmpty()) {
            int cur = priorityQueue.poll();
            if (target == input[1]) {
                return cur;
            }
            target++;
        }
        return 0;
    }
}

 

🧐 느낀점

위에 작성한 코드는 리팩토링을 거치기 전의 코드로 IDE의 도움없이 진행하다보니 숏코딩을 하기 힘들었습니다.

후에 Integer에서 제공하는 기능 중 하나인 toBinaryString()을 활용해 이진수로 변경해서 1의 갯수만큼 count()를 시켜 비교하는 방식으로 변경했지만 구름에서 채점하니 계속 중간부터 Timeout이 나서 결국 포기,,,

IDE도움을 받지 않고 계속 숏코딩할 방법, 변수 사용을 줄일 방법을 고민해봐야겠습니다.