[BOJ][JAVA] 10431: 줄세우기

 

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

10431번: 줄세우기

 

import java.util.Scanner;

class Main{
    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int n = 20;
        for(int tc = 0; tc<T; tc++){
            int tcNum = sc.nextInt();
            int[] input = new int[n]; 
            int fallBack = 0;
            input[0] = sc.nextInt(); // 첫 값은 그대로 들어감
            for(int i=1; i<n;i++){
                input[i] = sc.nextInt();
                for(int j=0; j<i; j++){
                    if(input[j] > input[i]){
                        for(int k=i; k>j; k--){
                            input[k] = input[k-1];
                            fallBack++;
                        }
                        input[j] = input[i];
                    }
                }
            }
            System.out.println(tcNum+" "+ fallBack);
        }

        sc.close();
    }
}

---

오답노트(푸는 동안 사고과정 및 개선점)

삽입정렬을 생각하면서 풀었다. 삽입시, 이전 배열을 처음부터 한바퀴 돌면서 작은 걸 발견했을때, 그 지점부터 하나씩 밀고 그 자리에 넣는 방식이다. 이렇게 하면 25%에서 틀렸습니다가 나온다. 시간초과가 아니라서 복잡도에 걸리는 건 아닌 것 같은데 뭐가 문제인지 살펴보자.

---

정답코드

import java.io.FileInputStream;
import java.util.Scanner;

class Main{
    public static void main(String[] args) throws Exception{
        System.setIn(new FileInputStream("res/input.txt"));

        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int n = 20;
        for(int tc = 0; tc<T; tc++){
            int tcNum = sc.nextInt();
            int[] input = new int[n]; 
            int fallBack = 0;
            input[0] = sc.nextInt();
            for(int i=1; i<n;i++){
                input[i] = sc.nextInt();
                for(int j=i; j>0; j--){
                    if(input[j-1]>input[j]){
                        int tmpJ = input[j-1];
                        input[j-1] = input[j];
                        input[j] = tmpJ;
                        fallBack++;
                    }
                }
            }
            System.out.println(tcNum+" "+ fallBack);
        }
        sc.close();
    }
}

훑는 방식을 바꿔봤다.

이전 방식이

1. 앞에서 부터 현재 삽입 값보다 큰 것 찾기
2. 찾았으면 그 위치부터 뒤로 쭉 한 칸 씩 밀기
3. 해당 위치에 값 삽입

이라서 3중 포문이 됐는데, 아예 삽입을 맨 뒤에서 부터 고려하면 swap될때를 fallback 하나로 치면 됐다.

시간 복잡도도 줄고, 왜 났는 지 모를 오답도 걸러낼 수 있었다.

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^