[BOJ] 백준 7344번: 나무 막대

1일 1PS 11일차!

📚 문제

---

골드 2

• 정렬되지 않은 하나의 배열에서 오름차순이 가능한 수열의 개수를 구하는 문제와 같다.
• 요소 하나씩 뽑아내며 리스트에 요소보다 작은 경우가 있으면 교체하고 아니면 리스트에 요소를 추가한다.
  • 4, 1, 5, 9, 2
    • 요소 = 4, 리스트 = [] -> [4]
    • 요소 = 1, 리스트 = [4, 1]
    • 요소 = 5, 리스트 = [5, 1]
    • 요소 = 9, 리스트 = [9, 1]
    • 요소 = 2, 리스트 = [5, 2]

💡 포인트

---

1. 길이와 무게로 묶어 리스트를 만든다.
2. 해당 리스트를 길이를 통해 정렬한다. 길이가 같을 경우 무게에 따라 정렬한다.
3. 정렬된 순서대로 무게를 하나씩 뽑아낸다.
4. 리스트를 하나 만들고 뽑아낸 무게가 리스트 안에 있는 숫자보다 크면 해당 숫자를 뽑아낸 무게로 변경하고 모두 작으면 리스트에 추가한다.
5. 리스트의 길이가 총 작동 시간이다.

💻 코드

---

t = int(input())
for _ in range(t):
    n = int(input())
    numbers = list(map(int, input().split()))

    paired_and_sorted = [(numbers[i], numbers[i + 1]) for i in range(0, len(numbers), 2)]
    paired_and_sorted.sort(key=lambda pair: (pair[0], pair[1]))

    arr = []
    for pair in paired_and_sorted:
        flag = False
        for i in range(len(arr)):
            if arr[i] <= pair[1]:
                arr[i] = pair[1]
                flag = True
                break
        if not flag:
            arr.append(pair[1])

    print(len(arr))