백준 3006. 터보소트 :: 돼지개발자

출저 : https://www.acmicpc.net/problem/3006

"세그먼트 트리...?"

문제를 풀고나서 시간이 오래 걸려 찾아 보았더니 이 문제는 세그먼트 트리를 이용해서 풀어야 한다고한다. 하지만, 허접인 안는 세그먼트 트리가 뭔지 몰랐고, 생짜 구현했다. 

세그 먼트 트리에 대해서 공부한 후에 다시 풀어봐야 겠다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
class Main {
    
    static int N;
    static int[] arr;
    static int low,high;
    static int min, max;
    static StringBuffer sb = new StringBuffer();
    public static void main (String[] args) throws IOException{
    
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        low = 0;
        high = N-1;
        min = 1;
        max = N;
        int time  = 1;
        
        while(low < high) {
            int cnt = 0;
            int idx = 0;
            
            if(time % 2 == 0) {
                for (int i = low; i <= high; i++) {
                    if(max == arr[i]) {
                        idx = i;
                        break;
                    }
                }
                
                for (int i = idx; i < high; i++) {
                    swap(i,i+1);
                }
                
                cnt += (high - idx);
                high--;
                max--;
            }
            else {
                for (int i = low; i <= high; i++) {
                    if(min == arr[i]) {
                        idx = i;
                        break;
                    }
                }
                
                for (int i = idx; i > low; i--) {
                    swap(i,i-1);
                }
                cnt += (idx - low);
                low++;
                min++;
            }
            sb.append(cnt+"\n");
            time ++;
        }
        sb.append("0\n");
        System.out.print(sb.toString());
    }
    
    static void swap(int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}