[Epper] 사다리(집으로 가는 길)

문제

겨울이와 친구들은 자신의 집으로 돌아가야 합니다. 겨울이 포함 4명의 사람이 있다고 했을 때, 현재 각 사람이 갈 수 있는 길은 그림1과 같습니다. 편의를 위해 사람에게 번호를 부여하였으며, 각 집에는 살고 있는 사람의 번호로 표시됩니다. 이런 도로상황에서, 우리는 강을 가로지르는 다리를 추가할 수도 하지 않을 수도 있습니다. 다리 추가 작업을 마친 후, 각 사람은 도로를 따라 목표지점인 본인 번호의 집까지 가야합니다. 1번사람을 예시로 들면, 아무런 다리가 설치되어 있 지 않을 경우, 3번집으로 가게 됩니다. 하지만 그림2 와 같은 다리가 놓여있을 경우라면, 모든 사람은 그림3처럼 빨간 경로를 따라 자신의 집에 도착하게 됩니다. 1번 사람은 1번 집, 2번사람은 2번 집, 3번 사람은 3번집, 4번사람은 4번집에 도착할 수 있습니다. 문제에서는 초기의 사람 배치 순서를 입력으로 줍니다. 그림1의 경우 입력은 [3, 2, 1, 4] 입니다. 각 사람이 자신의 집으로 돌아갈 수 있게 하는 최소 개의 다리의 수를 return 하도록 solution함수를 작성해주세요.

 

풀이

사다리 하나가 설치 되면 인접한 두 수가 서로 위치를 스왑하게 된다.

예를 들어 입력값이 3 1 2 4로 주어졌을 때 

3과 1, 1과 2 사이에 사다리가 추가가 된다면

3, 1, 2, 4 -> 1, 3, 2, 4 -> 1, 2, 3, 4 가 되게 된다.

따라서 이렇게 스왑을 이용하여 정렬하는 버블 정렬 기법을 사용하여 문제를 해결할 수 있다.

 

코드

package Level3;

import java.util.Scanner;

public class E16No8_사다리 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[] finalArray=new int[n];
		
		for(int i=0;i<n;i++) {
			finalArray[i]=sc.nextInt();
		}
		
		System.out.println(solution(n, finalArray));
	}
	
	static long solution(int n, int[] finalArray) {
		long bridge=0;
		
		//버블정렬 이용(다리 하나가 추가될 때마다 인접한 두 수 간의 스왑이 일어남) 
		//swap 필요하면 bridge 개수 증가
		for(int i=0;i<n;i++) {
			for(int j=i-1;j>=0;j--) {
				if(finalArray[j]>finalArray[i]) {
					bridge++;
				}
			}
		}
		
		return bridge;
	}
}