[백준/1015/수열 정렬]

https://www.acmicpc.net/problem/1015

1015번: 수열 정렬

 

<<풀이>>

 

DP

 

풀이 1

 

-> 일단 이 풀이는 틀린 답이다 ㅋㅋ

논리적으로는 맞다고는 생각했지만 hashmap을 특성을 간과하고 풀었다 ㅠ

map은 중복 인덱스를 허용하지 않다보니 이미 있는 인덱스가 있다면 기존의 인덱스를 지우고 새롭게 넣어준다. 

그렇기 때문에 밑의 풀이는 틀리게 되는 것이다 ㅋㅋ

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

class Main {
    private int[] solution(HashMap<Integer, Integer> map, int[] brr, int n) {
        int[] answer = new int[n];
        for (int i=0; i<n; i++) {
            answer[i] = map.get(brr[i]);
            map.put(brr[i], map.get(brr[i])+1);
        }
        return answer;

    }



    public static void main(String[] args){
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        HashMap<Integer, Integer> map = new HashMap<>();
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        int[] brr = new int[n];
        System.arraycopy(arr, 0, brr, 0, arr.length);
        Arrays.sort(arr);


        for (int i = 0; i < n; i++) {
            map.put(arr[i], i);
        }

        for(int x : T.solution(map, brr, n)) System.out.print(x + " ");

    }
}

 

 

풀이2

 

일반적으로 구현을 한 풀이이다. 이 풀이의 핵심은  3가지이다. 우선 정렬이다. 정렬을 하게 되면 순서관련한 문제에서 원하고자 하는 값을 구하기가 쉬워진다. 그다음 인덱스 값을 넣어주기 위한 P 배열, 넣어준 배열은 또 다시 사용되면 안 되기 때문에 (누락 발생) 1를 줌으로써 누락계산 피하기인 sortedIndex 배열을 줌으로써 문제를 수월하게 해결할 수 있다.

 

문제 자체는 그렇게 어려운 것이 아닌데 약간 해맨거를 보니 아직 난 한참 멀었다 ㅋㅋ ㅎㅎ

 

더 열심히 하자 !!

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); // 배열 A의 크기 N 입력
        int[] a = new int[n]; // 배열 A
        Integer[] p = new Integer[n]; // 비내림차순으로 만드는 수열 P
        int[] sortedIndex = new int[n]; // 정렬된 배열의 인덱스를 추적

        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt(); // 배열 A의 원소 입력
            p[i] = i; // 초기에 P[i]를 i로 설정
        }

        // 배열 A를 복사하여 정렬
        int[] sortedA = a.clone();
        Arrays.sort(sortedA);

        // 정렬된 배열의 각 원소에 대해 원본 배열에서의 인덱스를 찾아 P 배열에 할당
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (sortedA[i] == a[j] && sortedIndex[j] == 0) {
                    sortedIndex[j] = 1; // 인덱스 사용 표시
                    p[j] = i; // P 배열에 정렬된 인덱스 할당
                    break;
                }
            }
        }

        // 비내림차순으로 만드는 수열 P 출력
        for (int i = 0; i < n; i++) {
            System.out.print(p[i] + " ");
        }
    }
}

 

import java.util.Arrays;
import java.util.Scanner;

class Main {
    static int n;
    static int[] P;
    static int[] ch;

    private int[] solution(int[] arr, int[] brr) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (brr[i] == arr[j] && ch[j] == 0) {
                    ch[j] = 1;
                    P[j] = i;
                    break;
                }
            }
        }
        return P;
    }



    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        int[] arr = new int[n];

        P = new int[n];
        ch = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        int[] brr = arr.clone();
        Arrays.sort(brr);


        for(int x : T.solution(arr, brr)) System.out.print(x + " ");

    }
}

 

 

<<추가 공부>>

 

 System.arraycopy(arr, 0, brr, 0, arr.length);

-> 배열을 복사하거나 다른 배열을 추가할 때 이용하는 방식이다.

 

해설 : arr 배열 인덱스 0부터 (arr[0]) 해서 brr 배열의 인덱스 0부터 (brr[0]) arr.length - 1까지  arr을 복사하겠다. 

주로 합칠때 많이 이용할 것으로 생각된다.

 

clone

-> 이는 메서드이다. brr = arr.clone(); 을 하게 되면 arr배열을 그대로 brr에 가져오게 된다. 주로 배열을 변형하기 전에 기존 값을 빼두기 위해서 사용한다.