백준 1547번: 공

문제 설명

• 야바위와 유사하지만 공의 위치가 변하지 않습니다.
• 공은 움직이지 않기 때문에 항상 가장 왼쪽에 있습니다.
• 그렇기 때문에 해당 문제는 가장 왼쪽에 있는 컵의 번호를 찾는 문제입니다.

접근법

• 컵이 3개로 고정되어 있기 때문에 [1,2,3]의 배열을 사용했습니다.
• 배열의 두 원소를 서로 바꾸는 코드는 다음과 같습니다.

lst[a],lst[b] = lst[b],lst[a] #배열의 a번째 원소와 b번째 원소의 값이 서로 바뀝니다

• 반복문을 통해 컵을 섞는 행위를 M번 실행합니다.

정답

lst = [1,2,3] #컵의 개수는 항상 일정합니다
M = int(input()) #컵의 위치를 바꾼 횟수입니다 
for _ in range(M): #컵의 위치를 바꾼만큼 반복합니다
    a,b = list(map(int,input().split(' '))) #어떤 컵의 위치를 바꿨는지를 변수로 받습니다
    idx_a,idx_b = lst.index(a), lst.index(b) #해당 컵이 현재 몇 번째 위치에 존재하는지 index함수를 통해 파악합니다
    lst[idx_a],lst[idx_b] = lst[idx_b],lst[idx_a] #두 컵의 위치를 바꿉니다
    
    
print(lst[0])

기타

• .index() 함수의 시간복잡도는 O(n)입니다.
  • 이분탐색을 사용하면 시간복잡도를 O(log(n))으로 줄일 수 있습니다.