[백준_14467번] 소가 길을 건너간 이유 1

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

14467번: 소가 길을 건너간 이유 1

[문제]

 닭이 길을 건너간 이유는 과학적으로 깊게 연구가 되어 있지만, 의외로 소가 길을 건너간 이유는 거의 연구된 적이 없다. 이 주제에 관심을 가지고 있었던 농부 존은 한 대학으로부터 소가 길을 건너는 이유에 대한 연구 제의를 받게 되었다.

 존이 할 일은 소가 길을 건너는 것을 관찰하는 것이다. 존은 소의 위치를 N번 관찰하는데, 각 관찰은 소의 번호와 소의 위치 하나씩으로 이루어져 있다. 존은 소를 10마리 가지고 있으므로 소의 번호는 1 이상 10 이하의 정수고, 소의 위치는 길의 왼쪽과 오른쪽을 의미하는 0과 1 중 하나다. 이 관찰 기록을 가지고 소가 최소 몇 번 길을 건넜는지 알아보자. 즉 같은 번호의 소가 위치를 바꾼 것이 몇 번인지 세면 된다.

 

[입력 조건]

 첫 줄에 관찰 횟수 N이 주어진다. N은 100 이하의 양의 정수이다. 다음 N줄에는 한 줄에 하나씩 관찰 결과가 주어진다. 관찰 결과는 소의 번호와 위치(0 또는 1)로 이루어져 있다.

 

[코드]

package BEAKJOON;

import java.util.*;

public class BaekJoon_14467 {
	static int[][] cow;
	static int n,count=0;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		cow=new int[n][2];
		
		for(int i=0;i<n;i++) {
			cow[i][0]=sc.nextInt();
			cow[i][1]=sc.nextInt();
		}
		
		// 소의 번호를 기준으로 오름차순으로 정렬한다.
		Arrays.sort(cow, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				return o1[0]-o2[0];
			}
		});
		
		int prev=cow[0][0]; // 이전 소의 번호
		int status=cow[0][1]; // 이전 소의 위치
		for(int i=1;i<n;i++) {
			int now=cow[i][0]; // 현재 소의 번호
			
			/*
			 * 현재 소의 번호가 이전 소의 번호와 같으면
			 * 상태가 변했다면 count를 증가시킨다. 
			 */
			if(prev==now) 
				if(status!=cow[i][1]) 
					count++;
			
			status=cow[i][1]; // 소 위치 갱신
			prev=now; // 소 번호 갱신
				
		}
		
		System.out.println(count);
	}

}

 

[고찰]

 이번 문제는 구현 문제로 특정 알고리즘 사용 없이 주어진 조건들을 정확하게 구현하면 정답 처리를 받을 수 있는 문제였다. 2차원 배열에 소의 번호와 상태를 입력 받고 현재 소의 번호가 이전 소의 번호와 같으면서 상태가 변한 경우에 count를 증가시키는 방식으로 해결했다.