백준 - 14467

문제 링크

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

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

 

풀기 전에 아이디어

소의 위치는 0, 1 두 개뿐이라서.. 소 번호만큼 배열 생성한 후 소 번호에 맞는 인덱스에 0 , 1 바뀌는 거 체크해보기. 그리고 문제 보니까 소들 중에 제일 적게 건넌 횟수 구하는 것도 아니고, 그냥 소 건넌 횟수 다 합쳐서 구하는 거라서 별로 어렵진 않겠다는 생각이 들었다..

 

과정

처음엔 2차원 배열을 생성할까 했는데 구현이 산으로 가는 것 같았다. 그래서 그냥 배열 하나 생성했음

 

배열 크기는 소 번호가 1부터 10까지 있기 때문에 크기를 11로 정했다.

 

위치를 아직 모르는 상태에서 체크하려면 -1로 초기화하는 게 좋을 것 같았다. 근데 일일이 다 어떻게 -1로 채우지 하다가 Arrays.fill이라는 메서드에 대해 알게 되었다.

 

쨋든 이제 for문 돌리면서 값 입력받을 때마다 소 번호가 뭔지 보고 내가 만든 배열 중 소 번호에 해당하는 인덱스에 위치를 저장해 줬다. 위치는 0 or 1이니까.. 그리고 다음에 또 같은 소 번호를 입력받았을 때 저장해 둔 위치랑 다르면 그때 새로 입력받은 소의 위치로 바꿔주면서 소가 건넌 횟수를 담는 변수인 answer을 1씩 증가시켰다. 그러면 이제 소들이 얼마나 건넜는지 알 수가 있다.

 

시간 복잡도

3학년 때 알고리즘 시간에 배운 것 같긴 한데.. 일단 인터넷 다시 뒤적거리니까 약간 기억나는 것 같기도..

일단 for문 한번 돌렸으니까 O(n)이 아닌가 싶다 ㅎㅎ!

import java.util.*;

public class 14467 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int answer = 0;
		int[] arr = new int[11];
		Arrays.fill(arr, -1);
		for (int i = 0; i < n; i++) {
			int num = sc.nextInt();
			int loc = sc.nextInt();
			if (arr[num] == -1) {
				arr[num] = loc;
			}
			else if (arr[num] != loc) {
				arr[num] = loc;
				answer++;
			}
		}
		System.out.println(answer);
	}
}