가장 길게 이어지는 오름차순 로그 체인
자바스크립트 코딩테스트 문제로 lis 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
증가하는 값만 골라 가장 길게 이어 붙일 수 있는 부분 수열의 길이를 구하는 문제입니다.
문제 설명
서버 로그 중요도를 나타내는 정수 배열 levels가 주어집니다. 이 배열에서 순서는 유지하되 일부 원소를 건너뛰어 엄격하게 오름차순이 되도록 만들 수 있습니다.
이때 만들 수 있는 오름차순 부분 수열의 최대 길이를 반환하는 longestRisingLogChain 함수를 작성하세요.
예를 들어 levels = [5, 1, 6, 2, 3, 4]라면 1 → 2 → 3 → 4를 고를 수 있으므로 정답은 4입니다.
제한사항
0 <= levels.length <= 100,000-1,000,000,000 <= levels[i] <= 1,000,000,000- 부분 수열은 원래 순서를 유지해야 합니다.
- 같은 값은 오름차순에 포함되지 않으므로
strictly increasing이어야 합니다. - 반환값은 만들 수 있는 가장 긴 오름차순 부분 수열의 길이입니다.
예시
- 입력:
levels = [5, 1, 6, 2, 3, 4]→ 출력:4 - 입력:
levels = [9, 8, 7, 6]→ 출력:1 - 입력:
levels = [2, 2, 2, 2]→ 출력:1 - 입력:
levels = []→ 출력:0
힌트
- 길이가 같은 증가 부분 수열이 여러 개 있다면, 마지막 값이 더 작은 쪽이 다음 값을 붙이기 유리합니다.
- 어떤 배열
tails[len]을 “길이가len + 1인 증가 부분 수열이 가질 수 있는 최소 끝값”으로 생각해 보세요. - 새 숫자를 만날 때마다 이 값을 어디에 놓아야 하는지 선형 탐색 대신 이분 탐색으로 찾을 수 있습니다.
해설
이 문제는 대표적인 최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 문제입니다.
가장 먼저 떠오르는 방법은 dp[i] = i에서 끝나는 LIS 길이를 구하는 O(n^2) 풀이입니다. 하지만 levels.length가 최대 100,000이므로 더 빠른 방법이 필요합니다.
여기서는 tails 배열을 사용합니다.
tails[0]= 길이 1인 증가 부분 수열이 가질 수 있는 최소 끝값tails[1]= 길이 2인 증가 부분 수열이 가질 수 있는 최소 끝값- …
핵심은 실제 부분 수열 전체를 저장할 필요 없이, 각 길이에서 가장 유리한 끝값만 저장해도 길이는 정확히 구할 수 있다는 점입니다.
예를 들어 levels = [5, 1, 6, 2, 3, 4]를 보겠습니다.
5를 보면tails = [5]1을 보면 길이 1 수열의 끝값을 더 작은 값으로 바꿀 수 있으므로tails = [1]6을 보면 뒤에 붙일 수 있으므로tails = [1, 6]2를 보면 길이 2 수열의 끝값을 더 작게 만들 수 있으므로tails = [1, 2]3을 보면tails = [1, 2, 3]4를 보면tails = [1, 2, 3, 4]
최종 길이는 tails.length = 4입니다.
왜 교체가 괜찮을까요?
길이가 같은 증가 부분 수열이라면 끝값이 작을수록 이후 더 큰 숫자를 붙일 가능성이 커집니다. 그래서 어떤 숫자 x가 들어왔을 때는 tails에서 처음으로 x 이상인 위치를 찾아 그 값을 x로 바꾸면 됩니다.
- 그런 위치가 없다면
x는 가장 긴 수열 뒤에 새로 붙습니다. - 위치가 있다면 그 자리를 더 작은 끝값
x로 교체합니다. - 같은 값은 증가가 아니므로
>가 아니라>=기준 첫 위치를 찾아야 합니다.
이 위치를 매번 이분 탐색으로 찾으면 전체 시간 복잡도는 O(n log n), 추가 공간 복잡도는 O(n)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.