소트

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

문제

크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전순으로 가장 뒷서는 것을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 원소가 차례대로 주어진다. 이 값은 1000000보다 작거나 같은 자연수이다. 마지막 줄에는 S가 주어진다. S는 1000000보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(read.readLine());

        String[] arr = new String[N];
        StringTokenizer stoi = new StringTokenizer(read.readLine());
        for(int i = 0; i < N; i++){
            arr[i] = stoi.nextToken();
        }

        int S = Integer.parseInt(read.readLine());
        S = Math.min(S, N-1);

        for (int i = 0; i < S; i++) {
            boolean isSwap = false;
            for (int j = 0; j < N-1; j++) {
                if (!arr[j + 1].isEmpty() && !arr[j].isEmpty()) {
                    if (Long.parseLong(arr[j + 1] + arr[j]) > Long.parseLong(arr[j] + arr[j + 1])) {
                        String temp = arr[j + 1];
                        arr[j + 1] = arr[j];
                        arr[j] = temp;
                        isSwap = true;
                    }
                    if (isSwap) {
                        break;
                    }
                }
            }
        }
        String answer = String.join(" ", arr);
        System.out.println(answer);
    }
}

런타임 에러

원인 배열의 숫자를 문자로 변환하여 문자 합친 후 다시 숫자로 변환 하는 과정에서 Int 이상의 값이 만들어져서 변환하지 못하는 에러가 발생함

틀렸습니다

원인 - 추측 소팅하는 로직이 문제의 방식대로 진행되지 않는듯 해 보임
배열에 가장 큰값을 먼저 찾아서 최대한 앞으로 끄집어 내는게 먼저?

 // 최대 S번의 이동을 허용
        for (int i = 0; i < N - 1 && S > 0; i++) {
            // 최대 S번 안에 가장 큰 값을 찾아서 교환
            int maxIndex = i;
            for (int j = i + 1; j < N && j <= i + S; j++) {
                // arr[j] + arr[maxIndex] 비교를 통해 더 큰 값 찾기
                if ((arr[j] + arr[maxIndex]).compareTo(arr[maxIndex] + arr[j]) > 0) {
                    maxIndex = j;
                }
            }
            // maxIndex가 i와 다르다면 교환을 실행하고 S를 갱신
            if (maxIndex != i) {
                String temp = arr[maxIndex];
                for (int k = maxIndex; k > i; k--) {
                    arr[k] = arr[k - 1];
                }
                arr[i] = temp;
                S -= (maxIndex - i);  // 교환에 사용한 이동 수만큼 S 감소
            }
        }

틀렸습니다2

gpt 답을 이해해보자..

• arr을 애초에 int로 먼저 받고 최대값을 구함
• 최댓값을 찾고 앞의 요소와 교환
  -> 문자로 바꾸고 합쳐서 더 큰 숫자 비교 이부분이 필요가 없었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(read.readLine());
        int[] arr = new int[N];

        StringTokenizer stoi = new StringTokenizer(read.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(stoi.nextToken());
        }

        int S = Integer.parseInt(read.readLine());

        // S번의 교환을 허용하여 배열을 최대화
        for (int i = 0; i < N - 1 && S > 0; i++) {
            int maxIndex = i;

            // 현재 위치 i부터 S 범위 내에서 최대값 찾기
            for (int j = i + 1; j < N && j <= i + S; j++) {
                if (arr[j] > arr[maxIndex]) {
                    maxIndex = j;
                }
            }

            // maxIndex가 i와 다르다면 교환을 실행
            if (maxIndex != i) {
                // maxIndex까지의 요소를 앞으로 한 칸씩 이동
                int temp = arr[maxIndex];
                for (int k = maxIndex; k > i; k--) {
                    arr[k] = arr[k - 1];
                }
                arr[i] = temp;

                // 사용한 이동 수만큼 S를 감소
                S -= (maxIndex - i);
            }
        }

        // 결과 출력
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}