Baekjoon 12015 가장 긴 증가하는 부분 수열 2 JAVA

https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2012015

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

 

가장 긴 증가하는 부분 수열을 구하는 문제다.

https://blog.naver.com/soonil0119/222510558911

Baekjoon 11053 가장 긴 증가하는 부분 수열 JAVA

​이전에 풀었던 문제도 이진 탐색으로 풀었기 때문에 소스코드는 동일하다.

​

이진 탐색을 이용했고 이진 탐색에서 주의할 점은 만약 해당 수가 없으면 음수를 출력해 주는데

이 음수를 어떤 식으로 출력하는지 알아야 한다

​

음수 값은 현재 값이 있어야 할 위치 -1 해준 값이다. 이게 무슨 소리냐면

만약 2 4 6이라는 수열이 있을 때 5라는 데이터는 2번째 위치에 들어가면 된다. (시작은 0)

그러면 음수 값으로 -2가 주어지면 좋은데 확인해 보면 -3이 주어진다.

그 이유는 1234.. 숫자들은 양수 음수가 존재하지만 0은 양수 음수 개념이 없다

즉 이진 탐색을 했을 때 결과가 0이 나오면 이게 0번째에 있다는 건지 없지만 0번째에 들어가야 한다는 건지

알 수가 없다 그래서 만약 0번째에 있으면 0을 출력해 주고 그렇지 않다면 -1을 출력해 주어

0번째에 들어가야 한다는 것을 알려주는 방식이다.