hongjunland

Welcome

2 분 소요

백준 1083

제한

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 2730 637 509 29.490%

문제

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

입력

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

출력

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

예제 입력1

7
10 20 30 40 50 60 70
1

예제 출력1

20 10 30 40 50 60 70

예제 입력2

5
3 5 1 2 4
2

예제 출력2

5 3 2 1 4

예제 입력3

10
19 20 17 18 15 16 13 14 11 12
5

예제 출력3

20 19 18 17 16 15 14 13 12 11

풀이

처음에 완전탐색을 생각했다. S의 최댓값인 10^6, N의 최대값인 50으로 가정한다.

예제 2를 가정해 보면

5
3 5 1 2 4
2

에서 각 원소를 노드라고 가정하고 간선간의 순열에 대한 경우의 수를 생각한다면

(n-1)P(s)

50P10^6 > 2*10^8(2초)
=> 시간초과

이므로 시간초과가 예상이 되어, 최적화된 방법을 생각해 보았다.

사전순으로 가장 뒷자리에 해당하는 경우는 가장 왼쪽에 있는 숫자의 크기를 가능하면 최대화 시키는 것이다. 

7
10 20 30 40 50 60 70
1

예제 1을 참고하면, 가장 큰 값은 70이지만 횟수가 1개로 한정되어 가장 왼쪽에 있는 20과 교환할수 밖에없다.

그래서 현재 가지고 있는 횟수 S에 맞춰서 범위를 지정해 맨왼쪽부터 S를 다쓰거나 맨 오른쪽까지 갈때 까지 최댓값을 가져오는 방식으로 채택해 보았다.

이 아이디어는 bubble sort에 영감을 얻었고, 시간복잡도는 O(n2) 즉 2500 이라서 10^8 에는 한참 못미치기 때문에 시간문제도 해결할 수 있다.

while 문에서 한 루프를 돌때 마다 교체를 사용한 횟수를 차감하고, 인덱스를 1씩 증가시킨다.

그리고 종료조건을 S를 소진한 경우(S=0) 또는 인덱스가 오른쪽 끝(idx = N-1)까지 갔을 경우이다.

소스코드


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

public class Main {
    static int N;
    static int[] nums;
    static int S;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        nums = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < N ; i++){
            nums[i] = Integer.parseInt(st.nextToken());
        }
        S = Integer.parseInt(br.readLine());
        int current = 0;
        while (S>0 && current<N-1){
            int maxIdx = current;
            for(int i = current ; i <= current+S ; i++){
                if(i>=N) break;
                if(nums[i]>nums[maxIdx]) maxIdx = i;
            }
            int distance  = maxIdx-current;
            for (int i = maxIdx; i > current ; i--) {
                swap(i,i-1);
            }
            S-=distance;
            current++;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < nums.length ; i++){
            sb.append(nums[i]+" ");
        }
        System.out.println(sb);
    }
    static void swap(int idx1, int idx2){
        int temp = nums[idx1];
        nums[idx1] = nums[idx2];
        nums[idx2] = temp;
    }
}

참고