[백준/BOJ] 1083. 소트 [Gold 5]

1083. 소트

문제출처 : https://www.acmicpc.net/problem/1083

code

#include <iostream>
using namespace std;

int main()
{
    int N, A[50], S;
    bool flag = true;

    for (int i = 0; i < N; i++)
        cin >> A[i];
    cin >> S;

    while (flag)
    {
        flag = false;
        for (int i = 1; i < N; i++)
        {
            if (A[i - 1] < A[i])
            {
                swap(A[i - 1], A[i]);
                S--;
                flag = true;
            }
            if (S == 0)
            {
                flag = false;
                break;
            }
        }
    }
    for (int i = 0; i < N; i++)
        cout << A[i] << " ";

    return 0;
}

아니 예제입력도 다맞고, 내가생각해봤을때 예외적인것들은 다넣어봤는데, 왜 틀리다고 하는지 모르겠다. 질문에 들어가니까 여러개의 테스트케이스를 넣어야한다고 하는데, 7년전 질문이라 맞는질문인지도 확실하지않고, 분명 문제에는 그렇게 안써있는데... 잘모르겠다

20230814 수정

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

public class baekjoon1083 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    static int N,S,temp,arr_len,result_len;
    static List<Integer> arr,result;
    static String[] inputN;

    public static void main(String args[]) throws IOException{
        result = new ArrayList<>();
        arr = new ArrayList<>();

        N = Integer.parseInt(br.readLine());
        inputN = br.readLine().split(" ");

        for(int i=0;i<N;i++){
            temp = Integer.parseInt(inputN[i]);
            arr.add(temp);
        }
        S = Integer.parseInt(br.readLine());

        while(S!=0){
            arr_len = arr.size();
            result_len = result.size();

            if(arr_len==0){
                break;
            }

            int max = Collections.max(arr);
            int max_index = arr.indexOf(max);

            if(S >= max_index){
                result.add(arr.get(max_index));
                arr.remove(max_index);
                if(max_index!=0){
                    S -= max_index;
                }
            }else{
                int big=0;
                int big_index=0;
                for(int i=0;i<=S;i++){
                    if(big<arr.get(i)){
                        big = arr.get(i);
                        big_index=i;
                    }
                }
                result.add(big);
                arr.remove(big_index);
                if(big_index!=0){
                    S -= big_index;
                }
            }
        }

        for(int i=0;i<arr.size();i++){
            result.add(arr.get(i));
        }

        for(int i=0;i<N;i++){
            if(i==N-1){
                System.out.print(result.get(i));
            }else{
                System.out.print(result.get(i)+" ");
            }
        }

    }
}

다시한번 풀어봤다.
처음에는 버블소트처럼 하나씩바꾸면 되겠지했는데,
알고보니 S가 남은만큼 큰숫자들을 맨앞으로 빼야하는 문제더라.
조건을 차근차근맞추고 테스트하다보니 덕지덕지누더기가 된 느낌이 있는데..ㅠ
좀더 잘 짤 수도 있을것 같다.