백준 / 가장 긴 증가하는 부분 수열 2 / 12015번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 가장 긴 증가하는 부분 수열 2 / 12015번 (골드 2단계)

문제 사이트: https://www.acmicpc.net/problem/12015

 

문제 설명

---

나의 풀이

A = int(input())
cases = map(int, input().split())
sequence = [0]

for case in cases:
    if sequence[-1] < case:
        sequence.append(case)
    else:
        left = 0
        right = len(sequence)

        while left < right:
            mid = (right+left) // 2
            if sequence[mid] < case:
                left = mid + 1
            else:
                right = mid
        sequence[right] = case

print(len(sequence)-1)

---

※ 알아야 할 것

A = int(input())
sequence = map(int, input().split())

s = set(sequence)

print(len(s))

처음에는 이렇게 풀면 되지 않나라고 생각했다.

이런 풀이의 주요 문제는 다음과 같다.

 

• 순서 정보 손실:
  • set은 요소를 정렬하지 않으며, 요소의 순서를 기억하지 않는다. 따라서, LIS는 순서대로 증가하는 부분 수열을 찾아야 하지만 set을 사용하면 원래 순서가 무시되어 정확한 LIS를 찾을 수 없다
• 부분 수열의 정의:
  • LIS는 원래 수열의 일부 원소들을 원래 순서대로 포함하면서 증가하는 부분 수열의 길이를 찾는 문제다 중복된 값을 제거하고 고유한 원소 수를 세는 것은 문제의 요구사항을 충족하지 않는다.