[2568] 전깃줄-2

2568번: 전깃줄 - 2

처음 이걸 볼 때 가장 긴 증가하는 부분 수열, 전깃줄 문제와 비슷해서 “아.. Easy~” 라고 말했던 나는… 첫 틀렸습니다가 나왔을 때 직감했다. 뭔가 잘못되었다고…

우선 문제에서 요구하는 것은 2가지이다. 최소로 제거해야하는 전깃줄의 수와 제거할 전기줄의 번호이다. 제거할 전깃줄의 수는 이분 탐색을 돌려서, 이전 길이(cnt-1)의 값이 현재 탐색하는 수보다 큰 경우 cnt를 업데이트 하여서 최종 cnt 값을 모든 전깃줄 수에서 빼면 완료이다.

여기까지 코드는 다음과 같다.

import sys

def bs(left, right, value):
    while(left <= right):
        mid = (left+right)//2
        if lis[mid] < value:
            left = mid + 1
        else:
            right = mid-1
    return left

if __name__ == "__main__":
    N = int(sys.stdin.readline())
    elec = dict()
    keys = list()
    for i in range(N):
        a,b = map(int, sys.stdin.readline().split())
        keys.append(a)
        elec[a] = b

    cnt = 1
        
    keys.sort() // 이분탐색을 위해 정렬한다.
    lis = list(0 for _ in range(N))
    lis[0] = elec[keys[0]]

    for key in keys:
        value = elec[key]
        if lis[cnt-1] < value:
            lis[cnt] = value
            cnt += 1
        else:
            left = 0
            right = cnt
            ind = bs(left, right, value)
            lis[ind] = value

        print(N-cnt)

하지만, 내가 버벅였던 곳은 제거할 전깃줄을 구하는 문제였다.

처음에는 cnt 업데이트 시 길이, 즉 수열이 증가하는 것이니까. 증가할 때마다 이전 수열과 값을 저장하고 나중에 출력하면 되겠다 싶었는데, else 문을 체크하지 않은 문제가 있었다. 아래가 그 코드이다. else 에서 group[ind] = [key] 로만 처리하고 있어서…

        for key in keys:
        value = elec[key]
        if lis[cnt-1] < value:
            lis[cnt] = value
            group[cnt] = group[cnt-1][:]
            group[cnt].append(key)
            cnt += 1
        else:
            left = 0
            right = cnt
            ind = bs(left, right, value)
            lis[ind] = value
            group[ind] = [key]

새로운 수열이 등록될 때 값이 저장안되는 문제가 있다. 내 경우에 다음 예제에서 이슈가 있었다.

8
1 8
3 9
2 2
4 1
6 4
10 10
9 7
7 6

이것과 같이 4가 수열에 포함되지 않아서 전깃줄을 4개를 자르게 된다.

if ind > 0:
    group[ind] = group[ind-1][:]
    group[ind].append(key)
else:
    group[ind] = [key]

따라서 값이 작을 때 이렇게 수정해서 이전 길이의 수열을 현재 값에 붙이도록 수정했다. 그 다음은 간단하다. group[cnt-1] 이 전깃줄이 겹치지 않는 최적의 수열이기때문에 해당 수열을 제외한 모든 값을 출력하면 된다.

풀이

import sys

def bs(left, right, value):
    while(left <= right):
        mid = (left+right)//2
        if lis[mid] < value:
            left = mid + 1
        else:
            right = mid-1
    return left

if __name__ == "__main__":
    N = int(sys.stdin.readline())
    elec = dict()
    keys = list()
    for i in range(N):
        a,b = map(int, sys.stdin.readline().split())
        keys.append(a)
        elec[a] = b

    cnt = 1
        
    keys.sort()
    lis = list(0 for _ in range(N))
    group = dict()
    lis[0] = elec[keys[0]]

    for key in keys:
        value = elec[key]
        if lis[cnt-1] < value:
            lis[cnt] = value
            group[cnt] = group[cnt-1][:]
            group[cnt].append(key)
            cnt += 1
        else:
            left = 0
            right = cnt
            ind = bs(left, right, value)
            lis[ind] = value
            if ind > 0:
                group[ind] = group[ind-1][:]
                group[ind].append(key)
            else:
                group[ind] = [key]
            
            

    print(N-cnt)

    for k in keys:
        if k not in group[cnt-1][:]:
            print(k)