섹션4. Sorting & Thinking - (1)

🎈섹션4. Sorting & Thinking - (1)

🟦 4-1. 이진수 정렬

문제 풀이

첫 시도 코드

• 정답은 맞았는데 ,코드가 너무 길고 비효율적이다.
• 우선 <숫자, 1 카운팅> 객체를 NumCnt로 생성했다.
• 이 클래스의 경우 Comparable를 implements해서 내부적으로 compareTo메소드를 재정의할 수 있도록 했다.
• compareTo() 메소드는 기본적으로 cnt값 기준 오름차순 하되, 만약 두 객체간 cnt 값이 일치할 경우 num의 값 기준 오름차순 정렬이 되도록 재정의했다.
• 우선 [10진수 → 이진수(String) ] : Integer.toBinaryString() 사용하여 각 nums별로 이진수값을 tmp에 담은 뒤, tmp내부를 탐색하여 ‘1’을 가진 경우에 한해서 OneCnt[i]로 카운팅했다.
• 카운팅한 뒤, ArrayList 에 add(num 값, 카운팅값) 담은 뒤, Collections.sort()를 활용하여 객체를 특정 기준으로 오름차순 재정렬하도록했다.
• 마지막으로 answer[] 에 세팅하기 위해 정렬된 list의 각 객체를 접근한 뒤 num값을 가져오되, [2진수 → 10진수] : Integer.parseInt(숫자, 2) 교체하여 담았다.

import java.util.ArrayList;
/* 섹션 4-1. 이진수 정렬 
 * */
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;

class NumCnt implements Comparable<NumCnt>{
    int num;
    int cnt;
    NumCnt(int num, int cnt){
        this.num = num;
        this.cnt = cnt;
    }
    @Override
    public int compareTo(NumCnt o) {
        // TODO Auto-generated method stub
        if(this.cnt == o.cnt) { //만약 카운팅이 같으면 
            //숫자 오름차순 (작은->큰)
            return this.num - o.num;
        }
        //기본적으로 cnt기준 오름차순 정렬
        return this.cnt - o.cnt;
    }
}

class Solution {
    //솔루션 함수 
    public int[] solution(int[] nums){
        //여기에 1의개수 오름차순 정렬해서 (10진수) 담아 반환 
        int[] answer = new int[nums.length];

        ArrayList<NumCnt> list = new ArrayList<>();

        String[] tmp = new String[nums.length];
        int[] OneCnt = new int[nums.length];

        for(int i = 0; i<nums.length; i++) {
            tmp[i] = Integer.toBinaryString(nums[i]);
            for(char x : tmp[i].toCharArray()) {
                if(x == '1') {
                    OneCnt[i]++;
                }
            }
            //list에 담기 
            list.add(new NumCnt(Integer.parseInt(tmp[i]), OneCnt[i]));
        }

        //정해둔 기준으로 정렬시킬 것 
        Collections.sort(list);
        for(int i=0; i<list.size(); i++) {
            answer[i] = Integer.parseInt(Integer.toString(list.get(i).num), 2);
        }

        return answer;
    }
    //실행 메인 
    public static void main(String[] args){
        Solution T = new Solution();
        System.out.println(Arrays.toString(T.solution(new int[]{5, 6, 7, 8, 9})));
        System.out.println(Arrays.toString(T.solution(new int[]{5, 4, 3, 2, 1})));
        System.out.println(Arrays.toString(T.solution(new int[]{12, 5, 7, 23, 45, 21, 17})));
    }

}

완성 코드

- res[][] 2차원 배열에 각 i에 대한 cnt 값을 세팅해주는 방식으로 문제를 풀 수도 있다.

//4-1. 이진수 정렬 다시 문풀 
import java.util.*;
class Solution_Re { 

    //솔루션 함수 
    public int[] solution(int[] nums){
        int[] answer = new int[nums.length];
        int[][] res = new int[nums.length][2];
        for(int i=0; i<nums.length; i++) {
            int cnt = 0;
            int tmp = nums[i];
            while(tmp > 0){
                cnt += (tmp % 2);
                tmp = tmp/2;
            }
            res[i][0] = nums[i];
            res[i][1] = cnt;
        }

        Arrays.sort(res, (a, b) -> a[1] == b[1] ? a[0] - b[0] : a[1] - b[1]);
        for(int i =0; i<res.length; i++) {
            answer[i] =res[i][0];
        }

        return answer;
    }

    //실행 메인 
    public static void main(String[] args){
        Solution_Re T = new Solution_Re();
        System.out.println(Arrays.toString(T.solution(new int[]{5, 6, 7, 8, 9})));
        System.out.println(Arrays.toString(T.solution(new int[]{5, 4, 3, 2, 1})));
        System.out.println(Arrays.toString(T.solution(new int[]{12, 5, 7, 23, 45, 21, 17})));
    }
}

🟦 4-2. 원래의 수열 찾기

문제 풀이

첫 시도 코드 | 오류

• HashMap을 사용하여 각 nums 값에 대한 cnt 값을 중복없이 담을 예정이다.
• nums는 정렬
• [가장 작은 값은 map에서 삭제, 그 값의 2배 값도 삭제
• 빈도수 1 이상인 값에 한하여 answer[i]에 값을 세팅해줄 것이다.

/*4-2. 수열 찾기 */
import java.util.*;
class Solution {
    //솔루션 함수 
    public int[] solution(int[] nums){
        int[] answer = new int[nums.length / 2];

        //1)일단 nums 정렬
        Arrays.sort(nums);

        HashMap<Integer, Integer> map= new HashMap<>();
        for(int i=0; i<nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0)+1); //빈도수별 카운팅 
        }

        int i = 0; 
        for(int key : map.keySet()) {
            if(map.get(key) >= 1) {
                //1) 최솟값 담아주고 
                answer[i] = Collections.min(map.keySet());
                //카운팅-1
                map.put(answer[i], map.getOrDefault(answer[i], 0)-1);

                //2) 두배값 존재하면 삭제해줌 
                map.put(answer[i] * 2, map.getOrDefault(answer[i] * 2, 0) -1);

                i++;
            }
        }
        return answer;
    }
    //실행 메인 
    public static void main(String[] args){
        Solution T = new Solution();
        System.out.println(Arrays.toString(T.solution(new int[]{1, 10, 2, 3, 5, 6})));
        System.out.println(Arrays.toString(T.solution(new int[]{1, 1, 6, 2, 2, 7, 3, 14})));
        System.out.println(Arrays.toString(T.solution(new int[]{14, 4, 2, 6, 3, 10, 10, 5, 5, 7, 7, 14})));
    }
}

완성 코드

- HashMap 사용하여 중복값없이 카운팅한다

- nums 는 오름차순 정렬하여 , 각 nums의 x값은 (항상 최솟값이 됨) 카운팅이 0이 아닐 경우에 한해서만

최솟값 x를 answer에 담고, (x 카운팅 -1) , (x*2 카운팅 -1) 처리 한다.

package to_0524_3;
//4-2. 수열 찾기 
import java.util.*;
class Solution {
	public int[] solution(int[] nums){
		int[] answer = new int[nums.length / 2];
		
		HashMap<Integer, Integer> map = new HashMap<>();
		for(int x : nums) {
			map.put(x, map.getOrDefault(x, 0)+1);
		}
		//오름차순 정렬시켜놓고 
		Arrays.sort(nums);
		int idx = 0;
		for(int x : nums) {
			//카운팅 0 이면 그냥 지나가고 
			if(map.get(x) == 0) continue;
			//정답 세팅 
			answer[idx] = x;
			idx++;
			//최소값 카운팅-1, 
			map.put(x,  map.get(x)-1);
			//최솟값*2 카운팅 -1
			map.put(x*2, map.get(x*2) - 1);
		}
		
		return answer;
	}

	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(Arrays.toString(T.solution(new int[]{1, 10, 2, 3, 5, 6})));
		System.out.println(Arrays.toString(T.solution(new int[]{1, 1, 6, 2, 2, 7, 3, 14})));
		System.out.println(Arrays.toString(T.solution(new int[]{14, 4, 2, 6, 3, 10, 10, 5, 5, 7, 7, 14})));
	}
}