[Algorithm Champions] Week 4, No.6

문제

풀이

• order 의 문자 순서대로 array를 재정렬하는 문제이다.
  
  

해시맵 사용

• 공간복잡도가 O(1)이기 때문에 해시맵을 사용했다.
  -> array는 order 안의 숫자로만 구성되어있기 때문에 order의 각 문자별로 몇개가 들어있는지 세서 해시맵에 넣으면, array가 길어지더라도 해시맵에는 3쌍만 존재하기 때문에 O(1)이 된다.

• 우선 order의 각 원소가 array에 몇 개 들었는지 세서 해시맵에 넣는다.

• 다 넣으면 order의 원소가 해시맵에 들어있는지 확인한다.
  -> 들어있다면 그 개수만큼 array 배열에 값을 넣는다.
  -> 들어있지 않다면 order의 다음 요소로 넘어가서 이를 수행한다.

• 마지막에는 재정렬된 array를 반환한다.
  
  

포인터 사용

• 새로운 추가 공간을 사용하지 않고 푸는 방법이다.

• 왼쪽, 중간, 오른쪽 포인터를 만든다.

• 중간 포인터가 오른쪽 포인터보다 작거나 같을 때

  • 현재 값(curVal)을 중간 포인터가 가리키는 값으로 설정한다.
  • 현재 값이 첫 번째로 나올 숫자(order[0])인 경우, 왼쪽 포인터가 가리키는 숫자와 현재 값을 교체한다. 그리고 왼쪽 포인터와 중간 포인터를 하나씩 증가시킨다.
  • 현재 값이 두 번째로 나올 숫자(order[1])인 경우, 중간 포인터만 하나 증가시킨다.
  • 현재 값이 세 번째로 나올 숫자(order[2])인 경우, 현재 값과 오른쪽 포인터가 가리키는 값을 바꾸고 오른쪽 포인터를 하나 줄인다.

• 마지막으로 새롭게 정렬된 array를 반환한다.

코드

해시맵 사용

package com.company.w4;

import java.util.Arrays;
import java.util.HashMap;

/*
date: 21.07.08

input: 정수 배열, 세 숫자가 들어간 배열
output: 정수 배열
constraints:
    첫 번재 배열은
        두 번째 배열에 있는 정수만 포함한다.
        두 번째 배열에 있는 정수 세개가 모두 포함될 수도 있고 안될 수도 있다.
    두 번째 배열은 서로 다른 세 숫자만 들어간다.
    있는 배열에서 순서를 정렬해야한다. 새로운 공간 사용 불가.
    원하는 순서는 오름차순이나 내림차순일 필요가 없다.
edge cases:
    {2}, {1,3,2} => {2}
    {2,1}, {1,3,2} => {1,2}
    {2,1,3}, {1,3,2} => {1,3,2}

 */
public class No6_2 {
    public static void main(String[] args) {
        int[] array = {1, 0, 0, -1, -1, 0, 1, 1};
        int[] order = {0, 1, -1};
        System.out.println(Arrays.toString(desiredOrder(array, order)));
    }

    public static int[] desiredOrder(int[] array, int[] order) {
        // base case
        if (array.length == 1) return array;

        HashMap<Integer, Integer> map = new HashMap<>();
        for (Integer n : array) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }

        int idx = 0;

        for (int i = 0; i < order.length; i++) {
            if (map.containsKey(order[i])) {
                for (int j = 0; j < map.get(order[i]); j++) {
                    array[idx++] = order[i];
                }
            } else
                continue;
        }

        return array;
    }
}

포인터 사용

package com.company.w4;

import java.util.Arrays;

/*
date: 21.07.08

input: 정수 배열, 세 숫자가 들어간 배열
output: 정수 배열
constraints:
    첫 번재 배열은
        두 번째 배열에 있는 정수만 포함한다.
        두 번째 배열에 있는 정수 세개가 모두 포함될 수도 있고 안될 수도 있다.
    두 번째 배열은 서로 다른 세 숫자만 들어간다.
    있는 배열에서 순서를 정렬해야한다. 새로운 공간 사용 불가.
    원하는 순서는 오름차순이나 내림차순일 필요가 없다.
edge cases:
    {2}, {1,3,2} => {2}
    {2,1}, {1,3,2} => {1,2}
    {2,1,3}, {1,3,2} => {1,3,2}

포인터 세 개 사용하기


 */
public class No6_3 {
    public static void main(String[] args) {
        int[] array = {1, 0, 0, -1, -1, 0, 1, 1};
        int[] order = {0, 1, -1};
        System.out.println(Arrays.toString(desiredOrder(array, order)));
    }

    public static int[] desiredOrder(int[] array, int[] order) {
        System.out.println(Arrays.toString(array));
        int leftP = 0, midP = 0, rightP = array.length - 1;

        while (midP <= rightP) {
            int curVal = array[midP];

            if (curVal == order[0]) {
                array[midP] = array[leftP];
                array[leftP] = order[0];
                leftP++;
                midP++;
            } else if (curVal == order[1]) {
                midP++;
            } else if (curVal == order[2]) {
                array[midP] = array[rightP];
                array[rightP] = order[2];
                rightP--;
            }
        }

        return array;
    }
}