백준 10431 줄세우기 c++

 

 

 

처음 작성한 코드는 다음과 같다.

하지만 시간초과 오류가 떴다.

#include <iostream>
using namespace std;

int main(){
    int p;
    cin >> p;
    
    for(int i=0; i<p; i++){
        int t;
        int arr[20];
        
        cin >> t;
        for(int j=0; j<20; j++)
            cin >> arr[j];
        
        int answer = 0;
        for(int j=1; j<20; j++){
            int temp = arr[j];
            if(arr[j-1] > temp){
                for(int k=j-1; k>=0; k++){
                    if(arr[k] > temp){
                        answer++;
                        arr[k+1] = arr[k];
                    }
                    else{
                        arr[k] = temp;
                        break;
                    }
                }                
            }
        }        
        cout << t << " " << answer;
    }
    
    return 0;
}

 

 

 

앞선 코드에서는 직접 정렬까지 하며 옮겨야하는 횟수를 세는 방식으로 했는데, 

그냥 앞에 있는 수 중 현재 인덱스의 수보다 큰 경우를 count하는 방식으로 간단하게 구현했다.