[백준]2550: 전구 - JAVA
[백준]2550: 전구
2550번: 전구
첫 번째 줄에는 스위치의 수(전구의 수)를 나타내는 정수 N (1 ≤ N ≤ 10,000)이 주어진다. 두 번째 줄에는 N개의 스위치 번호들이 위에서부터 순서대로 빈칸을 사이에 두고 주어진다. 세 번째 줄에
www.acmicpc.net
풀이
🪑 LIS에 대한 개념이 없었더라면 LIS에 대해 이해부터 해야 하므로 어려웠을 문제이다. LIS를 알았다면 어렵지 않게 풀 수 있었을 문제였다.
🙋♀️ 우선 나는 LIS문제를 풀어본 적이 있었지만 오래전이라 기억이 나지 않았다. 그래서 LIS부터 다시 공부하였다!
🔹 LIS(Lowes Increasing Subsequence)
- 최장 증가 수열이라는 뜻이다.
- 예를 들면 [5, 6, 1, 2, 3] 이라는 배열이 있을때 [1, 2, 3]과 같이 해당 배열 내에서 제일 긴 증가하는 수열의 배열을 의미한다.
🔹 LIS는 어떻게 구할 수 있을까?
- 완전탐색: O(2^N)
- DP: O(N^2)
- 이분탐색: O(NlogN)
🔎 이전에는 DP로 풀어보았었다. 이번에는 이분탐색을 활용하여 푸는 방법을 알아보자.
🔹 LIS를 담은 리스트의 마지막 값과 수열의 현재 요소와 비교한다.
- 리스트의 마지막 요소가 현재 요소보다 작으면, 리스트의 마지막에 현재 요소를 추가한다.
- 리스트의 마지막 요소가 현재 요소보다 크면, 이분탐색을 진행하여 현재 요소가 들어갈 위치를 찾는다. 그리고 해당 위치의 값을 현재요소로 대체한다.
🔧 이제 문제를 풀어보자.
- 스위치에서 전구로 뻗은 선이 서로 겹치지 않으려면 가리키는 전구의 순서가 증가하면된다. 그러므로 LIS를 활용한다.
- 스위치의 번호를 입력받고, 이를 인덱스와 연결해 준다. (2번 스위치 - 0번 인덱스)
- 전구를 입력받고, 이를 스위치의 인덱스와 연결해 준다. (4번 전구 - 4번 스위치 - 1번 인덱스)
- LIS를 찾아준다.
- 전구에 대한 스위치 정보를 찾아 출력한다. 출력할때는 오름차순으로 출력한다.
🔹 왜 LIS일까?
- 스위치에서 전구로 뻗은 선이 겹치지 않도록 누를 수 있는 최대의 숫자를 눌러야 하는 것과 같은 문제라고 볼 수 있다.
- 겹치지 않도록 누르기 위해 어떻게 해야할지 생각해보면 스위치가 가리키는 전구의 순서가 증가하면 된다.
- 즉, 0번 인덱스의 스위치가 2번 전구를 가리켰다면 그 다음 인덱스의 스위치는 2번보다 큰 전구를 가리키면 겹치지 않는다.
- 그러므로 LIS를 구해주어야 한다.
🔹 스위치의 번호를 입력받고, 인덱스와 연결해 준다.
- 문제에서 원하는 답은 스위치에 대한 정보이다. 하지만 LIS를 진행해야 하는 정보는 전구에 대해서이다.
- 이때 스위치의 번호는 순서와 상관없는 수로 되어있으므로 LIS를 수행하기 위해 인덱스와 연결해 준다.
- 이 정보를 사용하여 전구에서 LIS를 수행한다.
🔹 전구를 입력받고, 스위치와 연결해준다.
- 전구 번호와 스위치를 연결해 준다.
- 만약 4번 전구를 입력받았다면 4번 전구에 해당하는 스위치의 인덱스인 1이 저장되어야 한다.
🔹 LIS를 찾아준다.
- 앞서 언급한 이분 탐색을 사용하였다.
- 이때 LIS에 저장되는 전구와 인덱스 정보를 저장한다. (다시 거꾸로 원래의 스위치 정보를 찾기 위함.)
🔹 전구에 대한 스위치 정보를 찾는다.
- 마지막으로 LIS를 수행한 전구의 인덱스와 LIS를 담은 list의 인덱스를 비교하며 거꾸로 원래의 스위치에 대한 정보를 찾아간다.
- 해당 인덱스를 가진 전구를 찾는 과정이다.
- 만약 현재 전구가 1번 전구라면 원래 1번 전구에 해당하는 스위치는 4번 스위치 이므로 4로 변경해 준다.
- 변경된 list를 오름차순하여 출력한다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
import java.util.*;
public class Main {
static int n;
static List<Integer> list = new ArrayList<>(); //LIS를 담을 리스트
static Node[] node;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
Map<Integer, Integer> map = new HashMap<>();
int[] origin_sw = new int[n];
for(int i = 0; i < n; i++) {
int sw = scan.nextInt();
origin_sw[i] = sw;
map.put(sw, i);
}
int[] bulb = new int[n];
for(int i = 0; i < n; i++) {
bulb[i] = map.get(scan.nextInt());
}
node = new Node[n];
for(int i = 0; i < n; i++) {
if(list.size() == 0 || list.get(list.size() - 1) < bulb[i]) {
list.add(bulb[i]);
node[i] = new Node(bulb[i], list.size() - 1); // sw와 연결된 전구의 LIS위치
} else {
int idx = binarySearch(bulb[i]);
list.set(idx, bulb[i]);
node[i] = new Node(bulb[i], idx);
}
}
int idx = list.size() - 1;
for(int i = n - 1; i >= 0; i--) {
if(node[i].idx == idx) {
list.set(idx--, origin_sw[node[i].num]);
}
}
System.out.println(list.size());
Collections.sort(list);
StringBuilder sb = new StringBuilder();
for(int i = 0; i < list.size(); i++) {
sb.append(list.get(i) + " ");
}
System.out.println(sb.toString());
}
public static int binarySearch(int num) {
int l = 0;
int r = list.size() - 1;
while(l <= r) {
int m = (l + r) / 2;
if(list.get(m) < num) {
l = m + 1;
} else{
r = m - 1;
}
}
return l;
}
public static class Node {
int num;
int idx;
public Node(int num, int idx) {
this.num = num;
this.idx = idx;
}
}
}
|
cs |
REFERENCE
https://lotuslee.tistory.com/17?category=962720