[Python] 7570. 줄세우기(골3) / 그리디

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

https://www.acmicpc.net/problem/7570

7570번: 줄 세우기

---

2. 핵심 아이디어

처음에는 가장 긴 증가하는 수열만큼 아이들을 남기고

규칙에서 어긋나는 아이들만 재배치를 해주면 된다고 생각했다.

 

그래서 O(nlogn)으로 LIS 알고리즘을 구현해주었는데

틀렸다는 것을 보고 멘붕이 왔다.

 

 

>>틀렸던 코드

import sys
from bisect import bisect_left
input = lambda: sys.stdin.readline().strip('\n')

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

x=[kids[0]]
dp=[1]

for i in range(1,n):
  last_kid= x[-1]
  #더 클 때
  if kids[i]> last_kid:
    dp.append(dp[-1]+1)
    x.append(kids[i])
  else:
    idx= bisect_left(x,  kids[i])
    x[idx]=kids[i]


print(n-dp[-1])

 

 

그럼 어디에서 예외가 발생한 것일까?

 

문제는 재배치 규칙에 있었다.

 

아이들을 재배치하는 것은 두가지 이다.

1. 맨 앞에 둔다.

2. 맨 뒤에 둔다.

 

즉, 내가 원하는 위치에 아이들을 껴넣을 수 있는 것이 아니라

맨 앞이나 뒤라는 추가조건이 있었다.

 

그렇기에 최대 증가수열을 만들고 아이들을 원하는 곳에 껴넣는 행위가 불가했던 것이다.

 

예를 들어 다음 아이들을 보자

1 3 2 4

 

최대 증가 수열은 1 4이다.

여기서 우린 가운데 2,3만 자리를 바꾸어주면 된다고 생각했으나

2와 3이 이동할 수 있는 자리는 맨 앞이나 맨 뒤이다.

 

그렇기에 최초에 생각한 2회보다 더 많은 횟수를 옮겨야 하는 상황이 발생한다.

---

따라서 이번 문제에는 가장 긴 연속된 증가수열을 찾아야 했다.

 

즉, 1씩 차이가 나는 가장 긴 연속 수열을 찾고,

잘못 서있는 아이들을 앞이나 뒤에 순서에 맡게 붙여주기만 하면 되었다.

 

예를 들어 다음 아이들을 보자

 

5 2 3 4 1 6

 

여기서 가장 긴 연속 수열은 2 3 4이다.

 

이제 1,5,6은 차례대로 앞 뒤에 붙여주기만 하면 된다.

 

1 + [2,3,4] + 5,6

 

---

그럼 가장 긴 연속된 증가수열을 어떻게 찾을까?

 

index를 활용하면 된다.

다음 숫자의 위치가 내 뒤에 있는지 확인하면서 가장 긴 연속수열을 찾으면 된다.

 

예를 들어 5 2 3 4 1 6 으로 서있는 아이들에 대해 각 위치를 기록하면

아이들 번호	1	2	3	4	5	6
위치	5번째	2번째	3번째	4번째	1번째	6번째

 

초기값 cnt=1로 설정해놓고

 

이제 1번부터 차례로 다음숫자와 비교해보자

1은 5번째이고 2는 2번째 => 2가 먼저 나오므로 해당x                      => cnt=1

2는 2번째이고 3은 3번째 => 2-3 순서대로 배치되어 있으므로 ok     => cnt=2

3은 3번째이고 4는 4번째 => 3-4가 순서대로 배치되어 있으므로 ok => cnt =3

4는 4번째이고 5는 1번째 => 5가 먼저나오므로 해당x                       => cnt를 1로 다시 초기화

5는 1번째 이고 6은 6번째 => 5-6이 순서대로 배치되어 있으므로 ok => cnt=2

 

여기서 가장 긴 연속수열은 cnt의 최대값이었던 3이다.

 

따라서 2-3-4의 연속수열은 그대로 놔두고 나머지 예외 아이들만 순서대로 배치해주면 되므로

최소 이동횟수는 6-3=3회가 된다.

 

이를 코드로 옮겨보자

 

 

---

3. 코드

#1씩 증가하는 가장 긴 수열

n= int(input())
kids= list(map(int, input().split()))
idx= [0]*(n+1)

for idx2, i in enumerate(kids):
  idx[i]=idx2

cnt=1
result=1
#print(idx)

for i in range(1, n):
  if idx[i]<idx[i+1]:
    cnt+=1
    result= max(result, cnt)
  else:
    cnt=1

print(n-result)

---

4.배운 점

문제를 푸는 과정에서 틀리기는 했지만 LIS 시간복잡도를 줄이려 했던 과정이 기억에 남아 아카이빙해두고자 한다.

이분탐색을 이용하면 LIS 기록은 물론 시간도 줄일 수 있다!!

 

velog

 

그리디는 항상 아이디어 발상과 정당성 탐색이 주가 되는 만큼

아이디어에서 그치지 않고, 그 아이디어가 최적 해를 가져다주는지도 더 생각해보자!!