[백준] 1083번 : 소트 - C++ / JAVA

백준 1083 : 소트

등급 : Gold IV

1083번: 소트 (acmicpc.net)

1083번: 소트

사용 알고리즘 : Greedy

사용 자료구조 : Vector

 

버블 소트(Bubble Sort)의 원리와, 이를 그리디적으로 활용하는 문제였다.

 

위와 같은 배열에 17번까지 SWAP이 가능하다고 해 보자.

 

이때, 17번 안에 10을 버블 소트로 가장 앞까지 가져올 수 있으므로 이를 진행해준다.

진행 하면서 버블 소트는 총 9번이 일어났으며, 1이 있던 위치에 10이 들어간다.

( 그냥 1의 위치와 10의 위치를 SWAP하면 안 된다. → 10 2 3 4 5 6 7 8 9 1이 됨 )

 

이후 8번 안에 9를 가장 앞까지 가져올 수 있으므로 이를 진행해준다.

이러한 방식으로 구현해주면 내림차순 정렬이 된 버블 소트 배열을 만들기가 가능하다.

---

  1. 배열의 크기와 배열 값, 그리고 가능 횟수를 입력받는다.

  2. 첫 번째 인덱스부터, 현재 인덱스 ~ 마지막 인덱스를 조사하며 바꿀 수 있는 최댓값을 조사한다.

      1) 최댓값을 저장할 변수(maxi)와 그 최댓값의 인덱스를 저장할 변수(maxi_idx)를 선언. (maxi_idx 초기값 -1)

      2) 현재 인덱스(v[i])보다 현재 조사하는 인덱스(v[j])가 더 크면서 남은 횟수(m)로 바꾸기가 가능한지 확인.

      3) 바꿀 수 있다면 저장된 최댓값(maxi)보다 더 큰지 확인하고, 더 크다면 최댓값(maxi)과 인덱스(maxi_idx)를 갱신.

      4) 최댓값의 인덱스가 -1이 아니라면 남은 횟수에서 두 인덱스 사이의 거리를 빼준다.

      5) 최댓값 인덱스에 위치하던 값을 지우고, 본래 인덱스의 앞에 삽입해준다.

  3. 위 과정을 반복하고 결과값을 출력시킨다.

---

<hide/>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n;
    vector <int> v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    cin >> m;
    for (int i = 0; i < n; i++)
    {
        int maxi = 0;
        int maxi_idx = -1;
        for (int j = i + 1; j < n; j++)
        {
            if (v[j] > v[i] && m >= j - i)
            {
                if (v[j] > maxi)
                {
                    maxi = v[j];
                    maxi_idx = j;
                }
            }   
        }
        if (maxi_idx != -1)
        {
            v.erase(v.begin() + maxi_idx);
            v.insert(v.begin() + i, maxi);
            m -= maxi_idx - i;
        }
    }
    for (int i = 0; i < n; i++)
    {
        cout << v[i] << " ";
    }
}

<hide/>
import java.io.*;
import java.util.*;

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

        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        List <Integer> v = new ArrayList<>();
        for(int i=0; i<n; i++)
        {
            v.add(Integer.parseInt(st.nextToken()));
        }
        int m = Integer.parseInt(br.readLine());
        for(int i=0; i<n; i++)
        {
            int maxi = 0;
            int maxi_idx = -1;
            for(int j=i+1; j<n; j++)
            {
                if(v.get(i) < v.get(j) && m >= j - i)
                {
                    if(v.get(j) > maxi)
                    {
                        maxi = v.get(j);
                        maxi_idx = j;
                    }
                }
            }
            if(maxi_idx != -1)
            {
                v.remove(maxi_idx);
                v.add(i, maxi);
                m -= maxi_idx - i;
            }
        }
        System.out.println(v.toString().replaceAll("\\[", "").replaceAll("\\]", "").replace(",", ""));
    }
}