[백준] 반도체 설계

최동혁·2022년 12월 6일

백준

목록 보기

52/68

반도체 설계

문제

반도체를 설계할 때 n개의 포트를 다른 n개의 포트와 연결해야 할 때가 있다.

예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다. 하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다. n개의 포트가 다른 n개의 포트와 어떻게 연결되어야 하는지가 주어졌을 때, 연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 최대 몇 개까지 연결할 수 있는지를 알아내는 프로그램을 작성하시오

입력

첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자.

출력

첫째 줄에 최대 연결 개수를 출력한다.

예제 입력 1

6
4 2 6 3 1 5

예제 출력 1

문제 해석

이진 탐색을 이용하여 LIS(가장 긴 증가하는 부분 수열)을 구하는 문제이다.
선이 얽히면 안되기 때문에 무조건 증가하는 식으로 선이 구성이 되어 있어야 하며 얽히면 그 선은 뒷 줄로 밀어버린다. 그러면 첫째 줄에서 가장 많이 연결되어야 하는 선을 뽑아야 한다.
이렇게 되면 LIS 문제랑 똑같다.
처음에는 BFS를 생각하여 풀이를 하였지만, BFS의 시간 복잡도는 O(n^2)이다. 하지만 LIS의 시간 복잡도는 O(nlogn)이다.

문제에서 제시한 데이터 수는 4 * 10^4 이였다. 그래서 시간 복잡도가 O(n^2)으로 풀어도 되는 줄 알았지만 앞에 4가 붙어있어서 그런지 시간초과가 떳다. 그래서 O(nlogn)의 시간 복잡도를 가진 LIS 알고리즘을 이용하여 풀어야 된다는 것을 깨닫고 구글링을 해보았다.

풀이

파이썬에서 제공해주는 bisect_left라는 함수가 있다. 이진 탐색을 이용하여 해당 값이 리스트의 값들과 비교하여 그 값이 삽입이 되어야 할 왼쪽 index 값을 리턴해준다. 이게 무슨 말이냐면
q = [1, 3, 5, 7, 9] 라는 리스트가 있다.
만약 index = bisect_left(q, 4)를 호출해주면 5 왼쪽에 삽입이 되어야 하기 때문에 현재 5의 index인 2를 리턴해준다.
이진 탐색을 써서 완전 탐색보다 훨씬 빠르게 동작을 한다.
이것을 이용하여 우리는 LIS를 풀 것이다.
예를 들어 우리가 2 11 4 55 7 9 13 3 이라는 수를 입력 받아서 LIS 식으로 가장 긴 증가하는 수열을 출력해야 한다.
그렇다면 우리는 2 4 7 9 13 이라는 수열이 가장 긴 증가하는 수열이라는 것을 알 것이다.
이걸 LIS 알고리즘을 이용하여 풀이해보자.

1. 2
2. 2 11
3. 2 4
4. 2 4 55
5. 2 4 7
6. 2 4 7 9
7. 2 4 7 9 13
8. 2 3 7 9 13

이런 식으로 업데이트를 한다면 가장 긴 수열을 뽑아낼 수 있다.
q라는 리스트에 초기 값인 2를 넣어준다.
그리고 루프를 돌면서 모든 수를 확인한다.
만약 2 다음의 숫자인 11이 2보다 크다면 증가하는 수열이기 때문에 q에 append를 해준다.
그런데 11 다음 숫자인 4는 11보다 작다.
그렇다면 bisect_left를 이용하여 q에서 4가 들어가야 할 index를 리턴 받는다.
그러면 11의 index 값인 1을 리턴 받을 것이다.
그렇게 11을 4로 바꾸어 준다.
55는 4보다 큰 수이기 때문에 q에 그대로 append를 해준다.
7은 55보다 작은 수 이기 때문에 bisect_left를 이용하여 index 값 2를 리턴 받고 55자리를 7로 바꾸어준다.
이렇게 진행을 하게 되면 2 3 7 9 13 이라는 수열이 나오게 된다.
하지만 이건 우리가 이전에 앞서 예상했던 2 4 7 9 13과 다르다.
이 풀이는 이 문제에서 가장 긴 증가하는 수열의 길이만 출력을 하라고 했기 때문에 가능한 풀이이다.
우리가 가장 중요시 하는 값은 q 리스트의 가장 끝 값인 13이다.
이 13만 유지가 된다면 그 앞에 13보다 작은 수들이 계속 업데이트가 된다고 하더라도 가장 긴 증가하는 수열의 크기는 변하지 않는다.
하지만 만약 가장 긴 증가하는 수열의 크기와 순서를 출력하라고 한다면??
우리는 증가하는 수열이면 그대로 append를 해주었고, 만약 증가하지 않으면 가장 긴 수열을 찾기 위해 q 리스트의 끝 값을 포함하여 리스트들을 가장 촘촘하게 체크했다.
위에 리스트들이 나열된 순서를 보자면 7 9 13 이렇게 3번 연속하여 증가하는 수열이 나왔다. 그럴때는 그냥 append를 시켰다.

1. 2 index = 0, value = 2
2. 2 11 index = 1, value = 11
3. 2 4 index = 1, value = 4
4. 2 4 55 index = 2, value = 55
5. 2 4 7 index = 2, value = 7
6. 2 4 7 9 index = 3, value = 9
7. 2 4 7 9 13 index = 4, value = 13
8. 2 3 7 9 13 index = 1, value = 3

이런 식으로 정리할 수 있다.

(0, 2)
(1, 11), (1, 4)
(2, 55), (2, 7)
(3, 9)
(4, 13)
(1, 3)

같은 index가 여러개 나올 때 가장 나중에 업데이트 된 value가 가장 긴 증가하는 수열의 일원이다.
q의 리스트의 길이는 총 5이다. 0, 1, 2, 3, 4 이렇게 5개 인데,
가장 끝에 업데이트 된 값을 보면 index가 1이면서 value가 3이다.
index가 4에서 갑자기 1로 변하면서 업데이트가 된 값은 가장 긴 증가하는 수열의 일원이 되지 못한다.
그래서 생각해 낸 것이, c라는 리스트를 따로 만들어서 q가 업데이트를 할 때마다 c에도 append를 해주는 것이다. c에는 q리스트의 특정 index의 값이 바뀌거나 특정 값이 추가될 때마다 업데이트 되는 위치의 index와 값을 튜플로 넣어준다.
c.append((index, value))
그렇다면 c 리스트에는 [(0, 2), (1, 11), (1, 4), (2, 55), (2, 7), (3, 9), (4, 13), (1, 3)] 이렇게 쌓일 것이다.
c 리스트의 길이는 우리가 입력 받은 리스트의 길이와 같다.
루프를 거꾸로 돌면서 체크를 해준다.
현재 q의 최종 길이는 5이다.
그래서 last_index = len(q) - 1로 잡아준다.
루프의 시작을 len(c) - 1부터 0까지 루프를 돈다.
만약 c[i][0] == last_index 라면 연속되는 index에서 가장 나중에 업데이트 된 값이 c[i][1]이기 때문에 ans라는 리스트에 넣어준다.
그리고 last_index를 1 감소시켜준다.
이렇게 하면 처음 루프를 돌면서 last_index는 4부터 체크를 할 것이다.
index가 4를 가지는 값이면서 가장 나중에 업데이트 된 수인 13이 ans 리스트에 삽입이 될 것이며 last_index = 3 으로 줄어든다.
그리고 index 3 자리에서 가장 나중에 업데이트 된 수는 9이다.
index 2 자리에서 가장 나중에 업데이트 된 수는 7, index 1 자리에서 가장 나중에 업데이트 된 수는 4, index 0 자리에서 가장 나중에 업데이트 된 수는 2이다.
그렇게 ans 리스트에는 [13, 9, 7, 4, 2] 이런 식으로 업데이트가 될 것이다.
이걸 reversed 함수를 이용해 뒤집어 주면 가장 긴 증가하는 수열의 리스트들이 나오게 된다.

정답 코드

import sys
from bisect import bisect_left

N = int(sys.stdin.readline())

list_num = list(map(int, sys.stdin.readline().split()))

q = [list_num[0]]

t = []

for i in list_num:
    if q[-1] < i:
        q.append(i)
    else:
        idx = bisect_left(q, i)
        q[idx] = i
        
print(len(q))

길이뿐만이 아닌 수열의 리스트까지 뽑아내는 코드

import sys
from bisect import bisect_left

N = int(sys.stdin.readline())

list_num = list(map(int, sys.stdin.readline().split()))

q = [list_num[0]]

c = []

for i in list_num:
    if q[-1] < i:
        q.append(i)
        c.append((len(q) - 1, i))
        
    else:
        idx = bisect_left(q, i)
        q[idx] = i
        c.append((idx, i))

last_idx = len(q) - 1
ans = []
        
for i in range(N - 1, -1, -1):
    if last_idx == c[i][0]:
        ans.append(c[i][1])
        last_idx -= 1
    if last_idx < 0:
        break
        
print(len(q))
print(*reversed(ans))