7476번 - 최대 공통 증가 수열
하루종일 이것만 붙잡았는데 왜 틀렸는지 깨닫지 못하고 있습니다.
전략은 이중포문으로 두 수열의 값이 같은 경우들을 모두 뽑아 하나의 수열로 나열합니다.
이 수열의 LIS가 정답이 되도록 했습니다.
이때 이진탐색을 활용하였습니다.
하나의 수열을 만드는 과정은 수열이 나열되어있을 때 insertion 소트 방식을 사용했습니다.
이전에 들어온 값보다 arr1, arr2의 인덱스가 크면 그자리에 위치하며 둘중 하나라도 이전의 인덱스 값보다 작으면
그때는 value 값을 비교하여 (node의 value -> arr1와 arr2의 같은 값 중 하나) 기존의 값보다 크면 앞으로 (증가 수열이 될 수 없도록),
작거나 같으면 뒤에 위치하도록 했습니다. (이 역시 증가 수열이 될 수 없도록...)
생각이 완전히 틀린걸까요??
도와주세요 ㅠㅜ
댓글을 작성하려면 로그인해야 합니다.
nano6384 6년 전
하루종일 이것만 붙잡았는데 왜 틀렸는지 깨닫지 못하고 있습니다.
전략은 이중포문으로 두 수열의 값이 같은 경우들을 모두 뽑아 하나의 수열로 나열합니다.
이 수열의 LIS가 정답이 되도록 했습니다.
이때 이진탐색을 활용하였습니다.
하나의 수열을 만드는 과정은 수열이 나열되어있을 때 insertion 소트 방식을 사용했습니다.
이전에 들어온 값보다 arr1, arr2의 인덱스가 크면 그자리에 위치하며 둘중 하나라도 이전의 인덱스 값보다 작으면
그때는 value 값을 비교하여 (node의 value -> arr1와 arr2의 같은 값 중 하나) 기존의 값보다 크면 앞으로 (증가 수열이 될 수 없도록),
작거나 같으면 뒤에 위치하도록 했습니다. (이 역시 증가 수열이 될 수 없도록...)
생각이 완전히 틀린걸까요??
도와주세요 ㅠㅜ