[백준/Java] 1083번 - 소트

문제 & 난이도

 

• 정렬 알고리즘
• 난이도 : 골드 4

 

풀이

 

📄 (잘못된 코드) 정렬 유형 생각 안하고 푼 첫 코드

package sorting;

import java.util.*;

//사용한 알고리즘 - 사전순으로 가장 뒷서는 것을 출력하려면 맨 앞에서부터 비교하면서 정렬해야 함

public class Beakjoon1083 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //첫째줄 : 크기 N
        int N = sc.nextInt();

        //크기 N인 배열 생성
        int[] arr = new int[N];

        //배열 안에 원소 넣기
        for(int i = 0; i < N; i++){
            arr[i] = sc.nextInt();
        }

        //마지막 줄 : 교환 횟수 S
        int S = sc.nextInt();

        //count : 교환 횟수, place : 현재 인덱스 위치
        int count=0, place = 0;

        //정렬
        while(count<S){
            if(arr[place]<arr[place+1]){
                change(arr, place, place+1);
                count++;
            }
            else{
                continue;
            }
            place++;
        }

        //결과 출력
        for(int i = 0; i < N; i++){
            System.out.print(arr[i]+" ");
        }
    }

    //자리 바꿔주는 change 메서드 생성
    public static void change(int[] arr, int a, int y){
        int temp = arr[a];
        arr[a] = arr[y];
        arr[y] = temp;
    }
}

 

📄시간 초과 나서 버퍼 사용했지만 여전히 문제점 수정 x → 코드 알고리즘 수이 필요함

 

▶ 위 코드의 반례를 찾아달라고 지피티한테 보냈더니, 5 / 3 5 2 4 1 / 3의 경우 3-5와 2-4, 3-4 순으로 교환이 이루어져 5 4 3 2 1이 나와야하는데 내 코드는 순차적으로 우위를 비교해 실행하다보니 5 3 4 2 1의 결과가 나왔다. 교환 횟수 제한이 있는 문제에서 제대로된 최댓값을 찾은 것이 아닌 인접한 원소만 비교하여 최적의 교환 결과를 얻지 못한 것.

▶교환 횟수를 최적으로 사용하기 위해서는 배열의 현재 위치에서부터 최대 교환 가능 범위 내에서 가장 큰 값을 찾아서 교환하는 방식으로 변경해야 한다는 지피티의 수정 제안 방법

 

📄최종 코드

import java.util.*;

public class Beakjoon1083 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //첫째줄 : 크기 N
        int N = sc.nextInt();

        //크기 N인 배열 생성
        int[] arr = new int[N];

        //배열 안에 원소 넣기
        for(int i = 0; i < N; i++){
            arr[i] = sc.nextInt();
        }

        //마지막 줄 : 교환 횟수 S
        int S = sc.nextInt();

        //정렬
        for (int i = 0; i < N && S > 0; i++) {
            // 최대 교환 가능 범위 내에서 가장 큰 값을 찾아야 함
            int maxIdx = i;
            for (int j = i + 1; j < N && j <= i + S; j++) {
                if (arr[j] > arr[maxIdx]) {
                    maxIdx = j;
                }
            }

            // 교환 횟수 줄이기
            S -= (maxIdx - i);

            // 가장 큰 값이 현재 위치에 오도록 교환
            for (int k = maxIdx; k > i; k--) {
                change(arr, k, k - 1);
            }
        }

        //결과 출력
        for(int i = 0; i < N; i++){
            System.out.print(arr[i] + " ");
        }
    }

    //자리 바꿔주는 change 메서드 생성
    public static void change(int[] arr, int a, int y) {
        int temp = arr[a];
        arr[a] = arr[y];
        arr[y] = temp;
    }
}

 

: 해당 알고리즘의 목적 - 교환 가능 범위 내에서 가장 큰 값을 찾아서 해당 값을 첫 번째 인덱스로 옮기는 것.

(배열의 길이가 n이고 교환 횟수가 s일때 교환 가능 범위 : 해당 인덱스+s)

이때 가장 큰 값을 해당 인덱스로 옮기면 그 다음은 다음으로 큰 값을 다음 인덱스의 위치까지 이동시키자.

 

알게된 것 & 느낀 점

 

입력 - 출력 값으로 문제를 유추하지 말고 주어진 문제 지문을 빠짐없이 잘 읽자 !

이해를 잘못해서 몇 번이나 고친 문제..

근데 여전히 백준에서 틀렸다고 나와서 스터디 끝나고 다시 코드 고치러 와야겠다 ㅜㅁㅜ

→  위 알고리즘/설명 참조