[Java] 정렬, 그리디 | 백준 1083 소트

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

 

접근 방법 :

 

그리디하게 각 위치에서 현재 범위 내 가장 큰 값을 앞으로 이동시킨다.

- S의 제한 때문에, 가능한 교환 횟수(j - i <= S)를 고려해주어야 한다.

 

두 원소 교환 과정 :

• 현재 위치 i 에서 i+1부터 i+S범위 내에서 가장 큰 값을 찾는다.
• 해당 값을 i로 이동시키기 위해 인접 원소 간 교환을 반복한다. (버블 소트와 유사)
• 값을 이동 시키는 데 사용한 교환 횟수만큼 S를 감소시킨다.

종료 조건 : S가 0이 되거나, 배열을 끝까지 탐색했을 경우 종료

 

핵심 코드 

S 제한 내에서 가장 왼쪽 자리부터 최대 값으로 채워주는 것에 집중한다.

매 반복 마다 S-=(maxIndex - i); 로 교환한 횟수만큼 S를 감소시켜준다.

private static void solve(){
    for(int i=0; i<N; i++){
        int maxIndex = i;
        for(int j=i+1; j<N && j-i<=S; j++){
            if(list.get(maxIndex) < list.get(j)){
                maxIndex = j;
            }
        }

        for(int j=maxIndex; j>i; j--){
            Collections.swap(list, j, j-1);
        }

        S -= (maxIndex - i);
    }
    printList();
}

 

전체 코드 

public class BOJ1083 {
    static List<Integer> list;
    static int N,S;
    public static void main(String[] args) throws Exception {
        init();
        solve();
    }

    private static void solve(){
        for(int i=0; i<N; i++){
            int maxIndex = i;
            for(int j=i+1; j<N && j-i<=S; j++){
                if(list.get(maxIndex) < list.get(j)){
                    maxIndex = j;
                }
            }

            for(int j=maxIndex; j>i; j--){
                Collections.swap(list, j, j-1);
            }

            S -= (maxIndex - i);
        }
        printList();
    }

    private static void printList(){
        for(int e : list){
            System.out.print(e+" ");
        }
    }

    private static void init() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        list = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            list.add(Integer.parseInt(st.nextToken()));
        }

        S = Integer.parseInt(br.readLine());
    }
}