1365

풀이1

전선이 꼬여있다는 것은 왼쪽 전깃줄이 오른쪽 전깃줄의 번호보다 크다는 것이다. (1->2, 2->3, 3->4, 4->1 일때 4->1의 전깃줄이 나머지 전깃줄을 지나가므로) 리스트로 입력을 받고 이렇게 되는 경우가 몇개인지 찾으면 될 것같다. 반복자 i는 왼쪽 전깃줄 번호이므로 i를 돌면서 i 인덱스의 값이 i 보다 작으면 res+=1

import sys
n = int(input())
arr = list(map(int, sys.stdin.readline().split()))
res = 0
for i in range(len(arr)):
    if arr[i] < i:
        res += 1
  

print(res) 

오류 : 왼쪽번호가 그 다음 인덱스 전깃줄 보다 큰 번호에 연결되는 경우도 선이 꼬인다

풀이2

제대로 연결되있는 선을 찾자
오른쪽으로 연결되는 번호를 받으면서 인덱스가 증가할수록 값이 증가해야 꼬이지 않는 것이므로 번호가 커지지 않을 때를 세면 된다

import sys
input = sys.stdin.readline

def binary_search(left, right, target):

    while left < right:
        mid = (left + right) // 2
        if lis[mid] < target:
            left = mid + 1
        else:
            right = mid
    return right
    
N = int(input())
numbers = list(map(int, input().split()))
lis = []
lis.append(numbers[0])

for i in range(1, N):
    if lis[-1] < numbers[i]:
        lis.append(numbers[i])
    else:
        j = binary_search(0, len(lis)-1, numbers[i])
        lis[j] = numbers[i]

print(N - len(lis))