[백준 2631] 줄 세우기

문제 출처 : https://www.acmicpc.net/problem/2631

 

이 문제는 2001년 정보 올림피아드 중등부 2번 문제 입니다.

 

처음에는 정렬 문제라 생각했습니다. 제목도 정렬과 관련 있는 줄 세우기고, 아이들을 원하는 위치에 넣어 정렬의 횟수를 구하면 되는 문제인가 생각했습니다. 하지만 막상 이렇게 풀려고 하니 최소 횟수를 구해야 한다는 부분에서 막혔습니다.

문제 이해하기

최소 횟수를 구하는 것이 포인트이기 때문에 이것을 반대로 생각했습니다. 이동해야 하는 아이들을 생각하지 않고 이동하지 않는 아이들을 생각해 보았습니다. 이런 문제를 풀 때 반대로 생각하는 것이 더 쉬운 방향일 수 있기 때문에 한번쯤은 고려해 봐야 합니다. 가만히 있는 아이들을 생각해보니 이미 정렬되어 있는 아이들이 움직이지 않을 것이고, 그 외 아이들은 모두 이동을 해야만 합니다. 결국 이 문제는 LIS를 구해야 하는 문제가 됩니다.

LIS에 대해 잘 모른다면 아래 링크를 통해 확인해 보시기 바랍니다.

https://davincicoding.tistory.com/29

LIS 란?

 

https://wikidocs.net/263301

07. LIS(최장 증가 수열)

 

LIS를 해결할 때에는 이분 탐색을 사용하는 것이 가장 좋습니다. 알고리즘 역시 가장 간단하기 때문에 이분 탐색으로 문제를 해결하도록 하겠습니다. 기억할 것은 다음과 같습니다.

1. 탐색할 첫 번째 원소가 들어있는 lis 리스트 만들기
2. 탐색할 원소가 lis 마지막 원소보다 크면 원소 추가
3. 탐색할 원소가 lis 마지막 원소보다 작다면 해당 원소로 lis 업데이트

코드작성

그럼 코드를 작성해 보겠습니다.

입력 받기

N = int(input())

arr = []
for _ in range(N):
    tmp = int(input())
    arr.append(tmp)

아이들의 수 N을 입력 받습니다. 그리고 아이들을 arr 라는 리스트에 넣습니다.

LIS 구하기

lis = [arr[0]]
for a in arr[1:]:
    if lis[-1] < a:
        lis.append(a)
        continue

    idx = bisect_left(lis, a)
    lis[idx] = a

위에 언급한 방법대로 구현해 주었습니다. 먼저 arr의 첫 번째 원소만 넣고 lis라는 리스트를 만들었습니다.

두 번째 원소부터 탐색하면서 lis의 마지막 원소와 크기를 비교합니다. 만약 원소 a가 더 크다면 lis에 추가합니다. 그렇지 않다면 이분 탐색으로 위치를 구해 lis에 업데이트 합니다.

출력하기

print(N - len(lis)) 

마지막으로 N에서 lis의 길이를 뺀 값을 출력합니다. 우리가 출력 해야하는 값은 정렬 되어 있는 아이들의 수가 아니라 정렬된 아이들을 제외한 나머지 아이들의 이동 횟수입니다. 따라서 전체 아이들의 수에서 lis의 길이를 빼 준 값을 출력합니다.

전체 코드

전체 코드를 확인해 보겠습니다.

from bisect import bisect_left

N = int(input())

arr = []
for _ in range(N):
    tmp = int(input())
    arr.append(tmp)

lis = [arr[0]]
for a in arr[1:]:
    if lis[-1] < a:
        lis.append(a)
        continue

    idx = bisect_left(lis, a)
    lis[idx] = a

print(N - len(lis))