[Swift Algorithm] 줄 세우기 BOJ #7570

문제 설명

대한 어린이집에 올해 입학한 어린이들이 놀이터에 한 줄로 서있다. 모든 어린이들에게는 입학할 때 주어진 번호가 있고 모두 옷에 번호표를 달고 있다. 그런데 어린이들은 아직 번호 순서대로 줄을 잘 서지 못하므로 선생님이 다음과 같은 방법을 사용해서 번호순서대로 줄을 세우려고 한다.

방법: 줄 서있는 어린이 중 한 명을 선택하여 제일 앞이나 제일 뒤로 보낸다.

위의 방법을 사용할 때 어린이가 이동해서 빈자리가 생기는 경우에는 빈자리의 뒤에 있는 어린이들이 한 걸음씩 앞으로 걸어와서 빈자리를 메꾼다.

예를 들어, 5명의 어린이들에게 1부터 5까지의 번호가 주어져 있고, 다음과 같은 순서로 줄 서있다고 하자. 

5 2 4 1 3

위 방법을 이용해서 다음과 같이 번호순서대로 줄을 세울 수 있다. 

1. 1번 어린이를 제일 앞으로 보낸다. (5 2 4 1 3 → 1 5 2 4 3)
2. 4번 어린이를 제일 뒤로 보낸다. (1 5 2 4 3 → 1 5 2 3 4)
3. 5번 어린이를 제일 뒤로 보낸다. (1 5 2 3 4 → 1 2 3 4 5)

위의 예에서는 세 명의 어린이를 제일 앞이나 제일 뒤로 보내 번호순서대로 줄을 세웠다. 그리고 두 명 이하의 어린이를 제일 앞이나 제일 뒤로 보내는 방법으로는 번호순서대로 줄을 세울 수 없다. 그러므로 이 경우에는 최소한 세 명의 어린이를 이동하여야 번호순서대로 줄을 세울 수 있다.

이 문제는 처음에 줄서있는 상태에서 위 방법을 이용해서 번호순서대로 줄을 세울 때 앞이나 뒤로 보내는 어린이 수의 최솟값을 찾는 것이다.

 

입력

입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하나씩 들어있다. 단, 어린이 수는 1이상 1,000,000이하의 정수로 제한되고, 어린이 수가 N이면 어린이들의 번호는 1부터 N까지의 정수이다.

 

출력

입력에서 주어진 어린이들의 줄에 대해 번호순서대로 줄을 세우기 위해 제일 앞이나 제일 뒤로 보내는 어린이 수의 최솟값을 출력해야 한다.

 

입출력 예제

입력

5
5 2 4 1 3

출력

3

 

내 문제 풀이

import Foundation

var n = Int(readLine()!)!
var input = readLine()!.split(separator: " ").map({Int(String($0))!})
var position = Array(repeating: 0, count: n)
var count = 1
var max = 0

// position 업데이트
for i in 0..<n {
    position[input[i]-1] = i
}

for i in 0..<n-1 {
    if position[i] < position[i+1] {
        count += 1
        if count > max { max = count }
    }
    else { count = 1 }
}

print(n - max)

LIS문제인줄 알았는데, 아니었다고 한다..

최장 증가 부분 수열을 구하고, 나머지 요소들은 아무렇게나 옮길 수 있으면 LIS가 맞는데

이건 맨 앞이나 맨 뒤로만 옮겨야 한다는 제한조건이 있기 때문에 그렇게만 하면 예외가 생긴다.ㅜ

따라서 각 요소들의 인덱스를 확인하고 알맞게 서있는 어린이의 수를 구하여 풀어주었다.

• 입력된 수열들의 인덱스를 저장하기 위한 position 배열을 생성했다.
  position에는 input 배열에 나열된 수들의 인덱스를 원래 있어야 할 위치에 저장한다.
  (예를 들어, input이 [2, 1, 3]라면 position은 [1, 0, 2]가 된다. input은 원래 [1, 2, 3] 순으로
  배치되어야 하는데, 1은 [1]에 존재하고 2는 [0]에, 3은 [2]에 존재하기 때문이다.)
  -> 문제에서 주어진 예제의 경우, position에 [3, 1, 4, 2, 0]이 저장된다.
• 두 번째 for문에서 position 배열을 순서대로 검색하는데,
  if) position 배열의 앞 요소가 뒤 요소보다 작을 경우 count에 1을 더하고,
  count가 max보다 클 경우에는 max를 업데이트했다.
  else) position 배열의 앞 요소가 뒤 요소보다 클 경우에는 count를 1로 초기화했다.

 

💡 피드백

• 돌아돌아 역대급 오래걸린 문제여따.ㅜㅜ 근데 생각보다 쉽게 풀렸다.
• 그리디 문제가 정말 한 번 풀이를 생각해내지 못하면 정말 어려운 것 같다,,
• 그래도 내 안일한 구글링 덕에 LIS인줄 알고,, DP부터 이분탐색에 LIS까지 공부할 수 있었당,,

 

---

 

문제

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