정렬 연습문제

문제1

// Practice1
// nums 배열에 3가지 색으로 구분되는 데이터들이 들어 있다.
// 0은 흰색, 1은 파랑, 2는 빨강이라고 할때
// 주어진 nums 배열에서 흰색 부터 빨강 순으로 인접하게 정렬시킨 후 출력하는 프로그램을 작성하세요.

// 입출력 예시
// 입력: 2, 0, 2, 1, 1, 0
// 출력: 0, 0, 1, 1, 2, 2

import java.util.Arrays;

public class Practice1 {
    // 계수 정렬
    public static void solution(int[] arr) {
        if(arr == null || arr.length == 0){
            return;
        }

        int[] cntArr = new int[3];
        for(int i = 0; i < arr.length; i++){
            cntArr[arr[i]]++;
        }

        int index = 0;
        for(int i = 0; i < cntArr.length; i++){
            while(cntArr[i] > 0){
                arr[index++] = i;
                cntArr[i] -= 1;
            }
        }
    }

    public static void main(String[] args) {
        // Test code
        int[] arr = {2, 0, 2, 1, 1, 0};
        solution(arr);
        System.out.println(Arrays.toString(arr));
        System.out.println();

        arr = new int[]{2, 0, 1};
        solution(arr);
        System.out.println(Arrays.toString(arr));
    }
}

문제 2

// Practice2
// 문자열 배열 strs 가 주어졌을 때 anagram 으로 묶어서 출력하는 프로그램을 작성하세요.
// anagram 은 철자 순서를 바꾸면 같아지는 문자를 의미한다.
// 예) elvis <-> lives
// anagram 그룹 내에서 출력 순서는 상관 없다.

// 입출력 예시
// 입력: "eat", "tea", "tan", "ate", "nat", "bat"
// 출력: [[eat, tea, ate], [bat], [tan, nat]]


import java.util.ArrayList;
import java.util.HashMap;

public class Practice2 {
    public static ArrayList<ArrayList<String>> solution(String[] strs) {
        if(strs == null || strs.length == 0){
            return new ArrayList<>();
        }
        HashMap<String, ArrayList<String>> map = new HashMap<>();

        for(String s : strs){
            char[] cArr = s.toCharArray();
            sort(cArr);
            // sort
            String key = String.valueOf(cArr);
            if(!map.containsKey(key)){
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(s);
        }
        return new ArrayList<>(map.values());
    }

    public static void sort(char[] arr) {
        for(int i = 1; i < arr.length; i++){
            for(int j = i; j > 0; j--){
                if(arr[j-1] > arr[j]){
                    char temp = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = temp;
                }else{
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        // Test code
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        System.out.println(solution(strs));

        strs = new String[]{"abc", "bac", "bca", "xyz", "zyx", "aaa"};
        System.out.println(solution(strs));
    }
}

문제 3

// Practice3
// intervals 라는 구간으로 이루어진 배열이 주어졌을 때,
// 오버랩 되는 구간을 합치는 프로그램을 작성하세요.
// 합친 구간은 오름차순으로 정렬해서 반환

// 입출력 예시
// 입력: [2, 6], [1, 3], [15, 18], [8, 10]
// 출력: [1, 6] [8, 10] [15, 18]

import java.util.ArrayList;
import java.util.Arrays;

public class Practice3 {

    public static ArrayList<int[]> solution(int[][] intervals) {
        if(intervals == null || intervals.length < 2){
            return new ArrayList<>();
        }
        sort(intervals);

        ArrayList<int[]> result = new ArrayList<>();
        int[] curInterval = intervals[0];
        result.add(curInterval);

        for(int i = 1; i < intervals.length; i++){
            if(curInterval[1] >= intervals[i][0]){
                curInterval[1] = intervals[i][1];
            }else{
                curInterval = intervals[i];
                result.add(curInterval);
            }
        }
        return result;
    }

    public static void sort(int[][] intervals) {
        quickSort(intervals,0, intervals.length - 1);
    }

    public static void quickSort(int[][] arr, int left, int right){
        if(left >= right){
            return;
        }
        int pivot = partition(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot+1, right);
    }

    public static int partition(int[][] arr, int left, int right){
        int pivot = arr[left][0];
        int i = left;
        int j = right;

        while(i < j){
            while(arr[j][0] > pivot && i < j){
                j--;
            }

            while(arr[i][0] <= pivot && i < j){
                i++;
            }

            swap(arr,i,j);
        }
        swap(arr,left,i);
        return i;
    }

    public static void swap(int[][] arr, int i, int j){
        int[] tmp = arr[i];
        arr[i] = arr[j];
        arr[i] = tmp;
    }

    public static void main(String[] args) {
        // Test code
        int[][] intervals = {{2, 6}, {1, 3}, {15, 18}, {8, 10}};

        for (int[] item: solution(intervals)) {
            System.out.print(Arrays.toString(item) + " ");
        }
        System.out.println();

    }
}

문제 4

// Practice4
// 정수 배열 nums 가 주어졌을 때
// 오름차순으로 정렬하기 위해 배열 내에서 정렬이 필요한 구간의 길이를 출력하는 프로그램을 작성하세요.

// 입출력 예시
// 입력: 2, 6, 4, 8, 5, 3, 9, 10
// 출력: 5

// 입력: 1, 3, 1
// 출력: 2

public class Practice4 {
    public static int solution(int[] nums) {
        if(nums == null || nums.length < 2){
            return 0;
        }
        int min = Integer.MAX_VALUE;
        int firstIdx = 0; // 가장 좌측
        for(int i = nums.length -1; i>= 0; i--){
            min =  Math.min(min,nums[i]);
            if(nums[i] > min){
                firstIdx = i;
            }
        }

        int max = Integer.MIN_VALUE;
        int lastIdx = -1;
        for(int i = 0; i < nums.length; i++){
            max = Math.max(max,nums[i]);
            if(nums[i] < max){
                lastIdx = i;
            }
        }
        return lastIdx - firstIdx + 1;
    }

    public static void main(String[] args) {
        // Test code
        int[] nums = {2, 6, 4, 8, 5, 3, 9, 10};
        System.out.println(solution(nums));

        nums = new int[]{1, 3, 1};
        System.out.println(solution(nums));

        nums = new int[]{1, 9, 3, 4, 5};
        System.out.println(solution(nums));

        nums = new int[]{1, 2, 3, 4, 5};
        System.out.println(solution(nums));
    }
}