#백준_3006 터보소트 - Java 자바

#유형 : 시뮬레이션, 펜윅 트리

#난이도 : 플래티넘 4

# 맨 처음에는 트리문제로 접근안하고 그냥 구현해서 풀었는데, 풀고나서 보니 다른 사람들은 펜윅 트리 알고리즘으로 풀어서 도전해보았다. 

펜윅 트리는 https://www.crocus.co.kr/666에  정말 설명이 잘 되어있다. 필자가 설명하기 보다는 저 블로그에 정리가 잘되어있으니 참고하면 좋을 것 같다. 코드는 1) 시뮬레이션 2)펜윅 트리로 첨부한다.

 

# 펜윅 트리로 접근한 방식

5

5 4 3 2 1 로 생각해보자. 모든 인덱스에는 1이라는 값을 넣는다. 그렇다면 

1 1 1 1 1 이라는 값이 들어있을 것이다.

1) 처음에는 숫자 1을 찾아야 한다. 1은 5 번째에 있기에 앞으로 4칸을 땡겨야 한다.

그렇다면 1 1 1 1 1 에서 처음부터 5번째 인덱스까지 더한 후에 -1을 한다면 4를 얻을 수 있다.

그 후에 1 1 1 1 0 으로 배열을 변경해준다.

 

2) 그다음은 5를 옮겨야하는데 1번째에 있다.

이 값은 1 1 1 1 0 에서 첫 번째 인덱스에서 오른쪽으로 모든 합을 더한 후 -1을 하게 되면 3이라는 값을 얻을 수 있다.

그 후 0 1 1 1 0 으로 배열을 변경해준다.

 

이러한 방법을 반복하여 접근한다면 자바 Point 객체(값, 인덱스)와 펜윅트리의 update, sum 함수를 이용하여 풀 수 있다

 

package bj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class p3006 {
    static int N, low, high;
    static int arr[];
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        for(int n=0; n<N; n++) {
            arr[n] = Integer.parseInt(br.readLine());
        }
        StringBuilder sb = new StringBuilder();
        low = 0;
        high = N-1;
        int max = N;
        int min = 1;
        int time = 1;
        while(low < high) {
            int rs = 0;
            int index =0 ;
            
            if(time % 2 == 1) {
                for(int i=low; i<=high; i++) {
                    if(min == arr[i]) {
                        index = i;
                        break;
                    }
                }
                for(int i=index; i>low; i--) {
                    int tmp = arr[i];
                    arr[i] = arr[i-1];
                    arr[i-1] = tmp;
                }
                rs += (index - low);
                low++;
                min++;
            }
            else {
                for(int i=low; i<=high; i++) {
                    if(max == arr[i]) {
                        index = i;
                        break;
                    }
                }
                for(int i=index; i<high; i++) {
                    int tmp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = tmp;
                }
                rs += (high - index);
                high--;
                max--;
            }
            sb.append(rs+"\n");
            time++;
        }
        sb.append("0\n");
        System.out.println(sb.toString());
        
    }
}
 

package bj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
 
public class p3006_tree {
    static int N, low, high;
    static int tree[];
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        tree = new int[N+1];
        ArrayList<Po> arrList = new ArrayList<>();
        arrList.add(new Po(0,0));
        for(int n=1; n<=N; n++) {
            int x = Integer.parseInt(br.readLine());
            arrList.add(n, new Po(x, n));
            update(n, 1);
        }
        Collections.sort(arrList);
        int low = 1;
        int high = N;
        for(int i=1; i<=N; i++) {
            if(i%2 == 1) {
                System.out.println(sum(arrList.get(low).y)-1);
                update(arrList.get(low).y, -1);
                low++;
            }else {
                System.out.println(sum(N)- sum(arrList.get(high).y-1)-1);
                update(arrList.get(high).y, -1);
                high--;
            }
        }
    }
    
    public static int sum(int index) {
        int rs = 0;
        while(index > 0) {
            rs += tree[index];
            index -= (index & -index);
        }
        return rs;
    }
    public static void update(int index, int diff) {
        while(index<=N) {
            tree[index] += diff;
            index += (index & -index);
        }
    }
    
    public static class Po implements Comparable<Po>{
        int x;
        int y;
        
        public Po(int x, int y) {
            this.x=x;
            this.y=y;
        }
        @Override
        public int compareTo(Po o) {
            if(this.x - o.x > 0)
                return 1;
            
            return -1;
        }
        
    }
}