[배열] 타노스 배열

타노스 배열 

 

- 문제 (난이도 하)

드디어 타노스는 인피니티 건틀렛을 손에 넣었고, 타노스 정렬을 시행하려고 한다. 타노스 정렬은 세상에서 두번째로 빠른 정렬 알고리즘이다. 길이가 N인 수열 A[1], A[2], ... , A[N]이 주어졌을 때 이 수열을 타노스 정렬하는 과정은 다음과 같다.

A[i] > A[i + 1] (1 ≤ i ≤ N - 1)를 만족하는 원소 A[i]를 인피니티 건틀렛을 이용해 절반으로 줄인다. 즉, A[i] = floor(A[i] / 2) 를 적용한다. 이를 만족하는 원소가 여러 개 있다면 가장 앞서는 것을 처리한다.
더 이상 처리할 수 있는 원소가 없을 때까지 1번 과정을 반복한다.
주어진 수열 A를 타노스 정렬해보자.

- 입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스의 첫째 줄에 수열의 길이 N (1 ≤ N ≤ 50)이 주어진다.

둘째 줄에 수열의 원소 A[1], A[2], ..., A[N]이 주어진다. 수열의 i번째 원소는 정수 A[i] (1 ≤ A[i] ≤ 1 000) 이다.

 

- 출력

각 테스트 케이스마다 주어진 수열을 타노스 정렬한 결과를 출력한다.

 

- 풀이

자바로 해결

while문으로 반복해서 앞부터 탐색.

만약 모두 오름차순으로 정렬되었을 때는 flag가 변경되고, break됨.

 

import java.util.Scanner;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testcase = Integer.parseInt(br.readLine());
        for(int i =0;i<testcase;i++) {
            int size = Integer.parseInt(br.readLine());
            String [] arr = br.readLine().split(" ");
            int [] arrint = new int[size];
            for (int j = 0;j<size;j++){
                arrint[j] = Integer.parseInt(arr[j]);

            }

            int temp = 0;
            int flag = 0;
            while(true){
                for (int k = 0;k<size-1;k++){
                    if(arrint[k]>arrint[k+1]){
                        flag = 0;
                        break;
                    }else{
                        flag = 1;
                    }
                }
                if(flag == 1 || size==1){
                    break;
                }
                if(temp == size-1){
                    temp = 0;

                }
                if(arrint[temp]> arrint[temp+1]) {
                    arrint[temp] = (int)((arrint[temp])/2);
                }
                if(arrint[temp] <= arrint[temp+1]){
                    temp += 1;
                }
            }

            for (int j = 0;j<size;j++){
                System.out.print(arrint[j]+" ");
            }
            System.out.println();
        }
    }
}