[홀로 하는 코딩 공부] 병사 배치하기 (Python)

백준

사용 언어: Python

문제 링크: https://www.acmicpc.net/problem/18353

18353번: 병사 배치하기

 

*** 본 문제를 푸는 과정을 공유하려 한다.

---

▶ LIS 알고리즘 공부를 많이 했더니  "내림차순 배치와 동시에 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다." 라는 문구를 보자마자 LIS 알고리즘이 떠올랐다. 하지만 다른점은 LIS알고리즘은 오름차순으로 정렬했다면 해당 문제는 내림차순정렬이다.

▶ 그래서 binary_search 함수 부분의 부등호와 MIN_VALUE 사용이 아닌 MAX_VALUE 사용, 그리고 lis_arr 배열의 마지막 값이 for문에서 나오는 값보다 큰 경우에만 삽입하고 그 외에는 binary_search함수를 이용하여 배열에 들어갈 인덱스 구하는 정도만 변경하면된다.

 

import sys
input = sys.stdin.readline

n = int(input())
n_list = list(map(int, input().split()))


def binary_search(arr, tgt):
    left, right = 0, len(arr)-1
    while left < right:
        mid = (left+right) // 2
        if arr[mid] > tgt:
            left = mid+1
        else:
            right = mid
    return right


MAX_VALUE = 10000001
lis_arr = [MAX_VALUE]

for num in n_list:
    if lis_arr[-1] > num:
        lis_arr.append(num)
    else:
        idx = binary_search(lis_arr, num)
        lis_arr[idx] = num

print(n-len(lis_arr)+1)

 

 

▶ LIS의 오름차순을 내림차순으로만 변경하면 되는 문제였기에 해당 부분만 꼬이지않게 바꿔준다면 쉽게 풀리는 문제이다. 본 문제를 혼자 풀고나서야 LIS에 익숙해진 것 같은 느낌이 든다.

---

>> 위 내용은 필자가 코딩테스트 문제를 푼 코드입니다.

>> 부족한 점이 많을 수 있기에 잘못된 내용이나 궁금한 사항이 있으면 댓글 달아주시기 바랍니다.

>> 긴 글 읽어주셔서 감사합니다.