2550. 전구 (Python)

2550번: 전구

 

풀이

 LIS를 사용하여 해결하는 문제다. LIS는 여기를 참고하자. 문제는 여기에서 LIS의 길이뿐만 아니라 LIS에 포함되는 원소까지 구해야 한다. 

 

 일단 LIS를 구하는 대상이 되는 배열은 n번의 스위치가 전구 리스트에서 몇 번째에 있는지를 나타내는 인덱스 리스트이다.

 문제의 예제를 보면 스위치 리스트 [2, 4, 1, 5, 3]은 각각 전구 리스트에서 [4, 0, 2, 1, 3] 인덱스에 존재한다. 따라서 [4, 0, 2, 1, 3]에 대해서 LIS를 구하고 각각에 해당하는 스위치 번호를 구하여 출력해주면 된다.

 

 예를 들어 [4, 0, 2, 1, 3]의 LIS중 하나는 길이 3을 가진 {0, 1, 3}을 구할 수 있다. 이제 이 {0, 1, 3}을 스위치 번호로 나타내면 {4, 5, 3}이 되고 이를 오름차순 정렬하면 문제에서 주어진 정답 3 4 5가 되는 것이다.

 

 LIS에 속하는 원소를 구하는 것은 탐색에 사용된 정보를 하나의 배열에 append 해주고 이를 뒤에서부터 역추적 하는 것이다. 문제의 예제를 이분 탐색을 사용하여 LIS를 구하면서 사용된 모든 정보를 배열에 담으면 아래 그림과 같다.

 여기에서 튜플은 (LIS에 삽입 될 때의 인덱스 번호, 스위치 번호)를 의미한다. 위에서 LIS의 길이가 3이라는 것을 구했다. 배열의 길이가 3이니 마지막 인덱스는 2가 될 것이다. 이제 위의 배열의 뒤에서부터 인덱스 번호에 해당하는 값이 무엇인지 찾아보면 3번 스위치가 이에 해당함을 알 수 있다. LIS는 현재 다음과 같다.

• LIS : { 3 }

 

 이제 인덱스를 2에서 하나 감소시켜 1에 해당하는 스위치를 찾는다. 다음 스위치는 5번 스위치임을 알 수 있다. 이제 LIS에 5번 스위치 정보를 앞에 넣어준다.

• LIS : { 5, 3 }

 

 이제 인덱스를 1에서 하나 감소시켜 0에 해당하는 스위치를 찾는다. 1번 스위치는 1번째에 해당하기 때문에 넘어가고 다음으로 만난 4번 스위치가 인덱스 0에 해당함을 알 수 있다. 이를 LIS의 앞에 넣어준다.

• LIS : { 4, 5, 3 }

 

 이제 길이 3에 해당되는 LIS 정보를 구했으므로 탐색을 종료한다.

 

 위와 같은 방법으로 역추적을 통해서 LIS의 길이뿐만 아니라 원소까지 구할 수 있다.

 

코드

from bisect import bisect_left
INF = float('INF')


# LIS를 구하기 위한 함수 
def findLIS():
    dp = [switchToBulb[0][0]] 
    LIS = [(0, switchToBulb[0][1])] # (LIS에 삽입 될 때의 인덱스 번호, 스위치 번호)

    for i in range(1, N):
        idx, switch = switchToBulb[i]

        if idx > dp[-1]:
            dp.append(idx)
            LIS.append((len(dp)-1, switch)) # 현재 스위치 번호는 dp 배열의 마지막에 삽입 되었다.
        else:
            dpIdx = bisect_left(dp, idx)
            dp[dpIdx] = idx
            LIS.append((dpIdx, switch)) # 현재 스위치 번호는 dp 배열의 dpIdx번째 위치에 삽입 되었다.
    
    return len(dp), LIS # LIS의 길이와 LIS를 구하기 위해 사용된 정보를 모두 담아놓은 리스트를 return


if __name__ == '__main__':
    N = int(input())  # 스위치의 수
    switches = list(map(int, input().split())) # 스위치 리스트
    bulbs = list(map(int, input().split())) # 전구 리스트 

    switchToBulb = [] # switchToBulb[n] : (전구 리스트에서 n번 전구의 인덱스 번호, n번 스위치)

    for switch in switches:
        switchToBulb.append((bulbs.index(switch), switch))

    LISLength, LIS = findLIS() # LIS의 길이, LIS를 구하기 위해 사용된 모든 정보를 담아놓은 리스트 

    print(LISLength)

    cnt = LISLength - 1 # cnt번째부터 역추적을 통해서 LIS를 구성하는 스위치 번호를 탐색한다.
    res = [0 for _ in range(LISLength)]

    # LIS의 뒤에서부터 탐색
    for (idx, data) in reversed(LIS):
        if cnt == idx: # cnt번째에 해당하는 스위치 번호를 만나면
            res[idx] = data # 결과 배열의 idx번째에 해당 스위치 번호를 넣어주고 
            cnt -= 1 # cnt는 1 감소 시켜 다음 스위치 번호를 찾는다.

        if cnt < 0: # LIS의 스위치 번호를 모두 찾았으면 탐색 종료 
            break

    res.sort()
    print(" ".join(map(str, res)))