[2164/Swift] 카드2

*** 언어는 Swift! ***

 

벌써 알고리즘 스터디를 시작한 지 4회차이다. 점점 더 어려워지는 문제들을 풀면서 그래도 내가 처음보다는 문제를 풀 수 있다는 것에 놀라웠다. 문제를 풀고 나서 물론 어려웠지만 그래도 다 풀 수 있어서 정말 좋았던 스터디인 것 같다.

 

자 그럼 오늘도 알고리즘을 시작해보자😇

오늘의 문제는 2164번의 카드2 라는 문제였다. 자세한 문제는 아래와 같다.

 

솔직히 문제만 보면 어렵지 않은 문제였지만 시간초과에 걸려서 몇 번을 실패했던 문제였다.

스터디 때 보니까 C++로 하셨던 분이 사용했던 방식을 똑같이 썼는데 Swift는 시간복잡도가 높아서 시간초과가 떴었다. 너무 슬프다...

나중에 시간 복잡도도 한번 정리해보고 싶다!🤒

 

자 그럼 이번에도 문제를 쪼개보자

1. N을 입력받는다.

2. 제일 위에 있는 카드를 바닥에 버린다.

3. 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

 

쪼개기는 이게 끝이다! 정말 쉬울줄 알았던 내 자신 반성해 ( ᴗ_ᴗ̩̩ )

 

1. N을 입력받는다.

항상 했던 N을 입력받는다.

let n = Int(readLine()!)!
var numbers: [String] = []
for i in 1...n {
    numbers.append("\(i)")
}

N을 입력받고 입력받은 N을 numbers라는 배열에 String으로 넣어준다. Int로 받은 이유는 for 문에 사용하려고 했던 건데.. 딱히 이유가 없었던 것 같다.

 

2. 제일 위에 있는 카드를 바닥에 버린다.

이번 문제는 큐 알고리즘에 관련된 문제였다. 솔직히 처음 문제를 봤을 때 이게 큐인지 몰랐던 나는 해보다가 시간초과가 계속 나서 다른 방법을 바꿨는데도 잘 안풀려서 다른 사람들은 어떻게 했나 블로그를 찾아보았다.

그러다가 내가 하고 있는 방법과 비슷하게 풀었던 사람이 있길래 그 분의 코드를 참고해보기로 했다.

(나중에 스터디할 때 들었는데 혁신적인 방법이라구 한다, 궁금하다면 요기로)

[Swift Algorithm] 카드2 BOJ #2164

 

자 그럼 참고 삼아서 다시 코드를 짜보자

우리는 N번까지 이 행동을 반복할 것이기 때문에 while문을 이용해 마지막 하나가 남을 때 까지 반복한다.

 while numbers.count - indexFirst >= 2 {

 

그 다음에 제일 위에 있는 카드를 바닥에 버린다.

원래라면 removeFirst() 를 이용해 버려야하지만 removeFirst는 시간복잡도가 O(n) 이다. 그렇기 때문에 여기서는 사용했을 경우 시간초과가 뜰 것이다. 그러니 지우지 않고 해당 부분을 "" -> 빈 값으로 바꿔준다.

 numbers[indexFirst] = ""

다음으로 할 일은 첫번째 카드를 맨 밑으로 옮기는 일이다.

 

3. 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

먼저 옮길 카드를 미리 저장해둔다. 그리고 그 위치도 "" -> 빈 값으로 바꿔준다.

firstNumber = numbers[indexFirst + 1]
numbers[indexFirst + 1] = ""

이렇게 하고 저장해둔 카드를 배열의 맨 뒤에 붙여넣는다.

numbers.append(firstNumber)

마지막으로 우리는 index를 두번 사용했으니 (첫번째 카드를 버릴 때, 다음 카드를 옮길 때) index를 2 더해준다.

indexFirst += 2

이렇게 하면 갯수만큼 돈 후 배열에 마지막에 남은 값을 출력하면 정답을 얻어낼 수 있다.

전체 코드는 아래와 같다.

 while numbers.count - indexFirst >= 2 {
        
    /// 제일 위에 있는 카드를 바닥에 버린다.
    numbers[indexFirst] = ""

    /// 첫번째 카드를 저장해두고 해당 위치도 비워준다.
    firstNumber = numbers[indexFirst + 1]
    numbers[indexFirst + 1] = ""

    /// 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
    numbers.append(firstNumber)

    indexFirst += 2

    print(numbers)
}

만약 6까지의 카드가 있다면

["1", "2", "3", "4", "5", "6"] 의 배열이 만들어지고

제일 위에 있는 카드를 버린 후 그 다음 카드를 맨 뒤로 옮기면

["", "", "3", "4", "5", "6", "2"] 와 같이 나올 것이고

그 다음 똑같은 행동을 반복하면

["", "", "", "", "5", "6", "2", "4"]

["", "", "", "", "", "", "2", "4", "6"]

["", "", "", "", "", "", "", "", "6", "4"]

["", "", "", "", "", "", "", "", "", "", "4"]

가 되면서 마지막 남은 숫자는 4가 되게 된다!

 

자 이렇게 시간초과의 늪에 빠졌다가 블로그 구원을 받아 완성한 알고리즘! 

이번에도 한 건 해결!