[코드트리] ABC 줄 세우기

난이도는 낮지만 나중에 꼭 다시 사용할 알고리즘일것 같아 기록한다. 이것 외에도 최소값의 최댓값, 최댓값의 최솟값에 대한 알고리즘은 반드시 다시 숙지할것.

 

---

처음에 n명의 사람이 서있는 순서가 A부터 순서대로 알파벳으로 주어지면 알파벳 순으로 줄을 세우려고 합니다. 단, 순서대로 줄을 세우기 위해서는 인접한 두 사람의 위치를 계속 바꾸는 행위만 가능하다고 할 때, 가능한 최소 횟수를 구하는 프로그램을 작성해보세요. 예를 들어 4명의 사람이 서있는 순서가 A D C B와 같이 주어지면, A, B, C, D 순으로 줄을 세워야 합니다.

 

입력 형식

첫 번째 줄에 정수 n이 주어집니다.

두 번째 줄에 n명의 사람이 서있는 순서가 알파벳으로 공백을 사이에 두고 주어집니다.

• 1 ≤ n ≤ 26

출력 형식

첫 번째 줄에 최소 횟수를 구하여 출력합니다.

 

입출력 예제

예제1

입력:

4
A D B C

출력:

2

 

예제 설명

첫 번째 에제에서 4명의 사람이 서있는 순서가 A D B C와 같이 주어지면, 우선 D와 B의 순서를 바꿔줍니다. 그러면 A B D C와 같이 되고, 후에 D와 C의 순서를 바꿔주면 A B C D와 같이 됩니다. 순서대로 줄을 세우기 위한 최소 횟수는 2회 입니다.

---

내 코드

 

import java.util.*;

public class Main {
    //주어진 알파벳을 정렬하기 위해, index값으로 표현한다. 그것을 위한 알파벳 문자열
    static final String alpahbet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        //알파벳을 index로 표현한다. 그렇다면 i값과 index값을 동일시해 비교로직이 단순해진다.
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = alpahbet.indexOf(sc.next());
        }

        int count = 0;
        while(true){
            boolean isEnd = true;
            //모든 index값이 i값과 같다면 정렬된것이다.
            for(int i = 0; i < n; i++){
                if(arr[i] != i){
                    isEnd = false;
                    break;
                }
            }
            if(isEnd){
                break;
            }else{
                //모든 알파벳을 상대로 큰 알파벳을 뒤로 이동시킨다
                for(int i = 0; i < n-1; i++){
                    if(arr[i] == i)continue;
                    if(arr[i] > arr[i+1]){
                        int temp = arr[i];
                        arr[i] = arr[i+1];
                        arr[i+1] = temp;
                        count++;
                    }
                }
            }
        }
        System.out.print(count);
    }
}