백준 13711 자바 - LCS 4 (BOJ 13711 JAVA)

문제 : https://www.acmicpc.net/problem/13711

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/13700/BOJ_13711.java

 

[ 스포 주의 ]

  직접 풀어보려면 풀이를 보면 안됩니다. 딱 한마디로 바로 풀이가 끝나는 문제라..

 

 

 

 

 

 

 

 

 

 

 

 

---

 

LCS 시리즈인척 하는 LIS 문제입니다.

 

LCS ; Longest Common Subsequence

LIS ; Longest Increasing Subsequence

 

[오답]

1. 문제제목이 LCS라서 처음엔 LCS 알고리즘으로 풀었습니다. -> 답이야 나오겠지만 당연히 메모리초과 (10만x10만xsizeof(int))

2. 어차피 N x N 배열이 필요없으므로 배열크기를 2줄로 줄여서 풀었습니다. -> 답이야 나오겠지만 당연히 시간초과 (O(N^2)만 해도 10만x10만이면 10억이므로 다른 연산 다 쳐내도 그냥 NxN을 서로 확인만 해도 대략 10초니 될리가없음) ​

 

[특이점]

  양쪽 다 길이가 동일하고 1~N까지가 모두 포함되어 있다는점.

 

[풀이]

1. N=5에 대해 A수열이 1,2,3,4,5이라면, B수열과의 LCS는 단순히 B수열의 LIS와 동일함.

 

2. '특이점'에 따라 A와 B는 각각의 수열에 중복값이 없고, A에 있는건 B에도 단 1개 있고, B에 있는것도 역시 A에 단 1개 있으며 없는경우도 없음.

 

3. 그럼 어차피 LCS이므로 임의로 A수열과 B수열을 변경해도 문제가 없음!!

 

4. '풀이1'처럼 A수열이 오름차순으로 되도록 B수열의 값을 변경하면, 이제 B에 대한 LIS 연산만 진행하면 되는것. (16~22줄)

-> 즉, A가 [ㄱㄹㄷㄴ]이고, B가 [ㄷㄴㄹㄱ] 이렇게 양쪽다 단 1개씩 값이 존재하고 양쪽다 서로에게 값이 있다면, ㄱ을 0, ㄹ을 1, ㄷ을 2, ㄴ을 3로 생각하고 A를 [0123], B를 [2310]이라고 봐도 LCS 구하는데는 아무 문제가 없는것임. 그리고 '풀이1'에 따라 A를 오름차순으로 했으므로 이제 B의 LIS만 구하면 답임. (LIS가 2,3 이므로 답은 LIS의 길이인 2)

-> B수열에서 A수열과 동일한 값에 대한 인덱스를 기록하면 그렇게 됨. (O(N))

 

5. 이제 LIS를 진행하며, LIS는 대표적으로 트리셋을 사용하거나, binarySearch를 사용하면 되며, 두가지 경우 모두 O(NlogN)으로 가능. 링크 걸어둔 제 코드에선 binarySearch를 사용. c++에서 lower_bound 사용한 LIS와 동일한 역할을 하는 자바코드입니다.

 

6. 그럼 최종적으로 O(NlogN)으로 가능! (LCS로 할 경우 O(N^2))