닭이 길을 건너간 이유는 과학적으로 깊게 연구가 되어 있지만, 의외로 소가 길을 건너간 이유는 거의 연구된 적이 없다. 이 주제에 관심을 가지고 있었던 농부 존은 한 대학으로부터 소가 길을 건너는 이유에 대한 연구 제의를 받게 되었다.
존이 할 일은 소가 길을 건너는 것을 관찰하는 것이다. 존은 소의 위치를 N번 관찰하는데, 각 관찰은 소의 번호와 소의 위치 하나씩으로 이루어져 있다. 존은 소를 10마리 가지고 있으므로 소의 번호는 1 이상 10 이하의 정수고, 소의 위치는 길의 왼쪽과 오른쪽을 의미하는 0과 1 중 하나다.
이 관찰 기록을 가지고 소가 최소 몇 번 길을 건넜는지 알아보자. 즉 같은 번호의 소가 위치를 바꾼 것이 몇 번인지 세면 된다.
소의 번호와 위치가 주어질 때 소가 길을 건너간 최소 횟소를 출력하자.
파이썬의 dictionary를 이용해서 문제를 해결할 수 있다. 만약 dict에 해당 키가 없다면 초기 값을 기록한다. 만약 해당 값이 있다면 지금 들어온 위치와 원래 있던 위치를 비교한 뒤 다르다면 move count를 1올려주고 위치를 갱신한다. 위 과정을 반복하면 최소 이동 횟수를 구할 수 있다.
import sys
if __name__ == '__main__':
N = int(sys.stdin.readline().strip())
cow_dict = dict()
move = 0
for _ in range(N):
cow, location = map(int, sys.stdin.readline().split())
if cow in cow_dict.keys():
if location != cow_dict[cow]:
move += 1
cow_dict[cow] = location
else:
cow_dict[cow] = location
print(move)
문제의 내용을 그대로 구현했지만 비트 마스킹을 이용하면 더 빠른 시간에 문제를 해결할 수 있을 것 같다.