[코딜리티] Stone Wall - Stack과 Queue

 
▼ 문제 링크

StoneWall coding task - Learn to Code - Codility

영어로 된 문제가 너무 난해해서 이해하기 너무 어려웠던 문제.(사실 아직도 문제는 무슨 소린지 모르겠음;;) 벽돌을 쌓네 마네 하는 것들은 일단 뒤로 재쳐두고, 주어진 배열만 보고 유추해서 풀었다. 

 

# 풀이 1
FIFO Queue를 이용한 풀이

import Foundation
import Glibc

public func solution(_ H : inout [Int]) -> Int {
    var count = 0

    // use queue
    while !H.isEmpty {
        count += 1
        var index = 0
        let value = H.removeFirst()
        
        while index < H.count && value <= H[index] {
            H[index] -= value
            index += 1
        }
        
        // 0인 요소를 제외하되, 가장 첫번째 요소부터 연속된 0만 제외
        while !H.isEmpty {
            if H.first == 0 {
                H.removeFirst()
            } else {
                break
            }
        }
    }

    return count
}
swift

First-In First-Out, 선입선출의 특징을 가진 Queue를 이용한 풀이.

1. 배열의 첫 요소를 추출해서 value에 담는다.
2. value보다 크거나 같은 연속된 요소들을 찾아 value값 만큼 빼준다.
3. 배열 H의 첫 요소가 0으로 시작하면 해당 요소를 아예 제거해준다.
4. 배열 H가 빌때까지 1~3번 과정을 반복한다.

반복한 횟수가 count, 즉 문제에서 말하는 가장 최소로 필요한 벽돌의 개수가 된다.

테스트 케이스를 통과해서 맞겠거니 했는데... 퍼포먼스 테스트에서 죄다 탈락했다. 🥲

퍼포먼스를 조금이라도 향상시켜보고자 첫번째 요소가 아니라 마지막 요소를 사용해보기로 했다. (배열에서 맨 뒤가 아닌 중간 요소를 제거하면 해당 요소 뒤에 위치한 모든 요소들의 위치를 재정렬해줘야하기 때문에)

 

 

# 풀이 2
removeFirst() 대신 removeLast()

import Foundation
import Glibc

public func solution(_ H : inout [Int]) -> Int {
    var count = 0

    // use queue
    while !H.isEmpty {
        count += 1
        let value = H.removeLast()
        var index = H.count-1
        
        while index >= 0 && value <= H[index] {
            H[index] -= value
            index -= 1
        }
        
        // 0인 요소를 제외하되, 가장 첫번째 요소부터 연속된 0만 제외
        while !H.isEmpty {
            if H.last == 0 {
                H.removeLast()
            } else {
                break
            }
        }
    }

    return count
}
swift

배열 H의 첫번째 요소가 아니라 마지막 요소를 사용하는 걸 제외한 전체적 로직은 풀이 1과 동일하다. 

솔직히 퍼포먼스가 많이 개선됐을 거라고는 기대 안했는데, 그래서 그런지 결과도 딱 그만큼 나왔다.

(심지어 Wrong Answer의 값도 풀이 1과 2가 다르다 🙃)

아무리 생각해도 답이 안나와 결국 집단지성의 힘을 빌렸다.

 

 

# 풀이 3
LIFO Stack을 이용한 풀이

import Foundation
import Glibc

public func solution(_ H : inout [Int]) -> Int {
    var count = 0
    var stack = [Int]()

    // use stack
    for value in H {
        while stack.count > 0 && stack.last! > value {
            stack.removeLast()
        }

        if stack.count == 0 || stack.last! < value {
            stack.append(value)
            count += 1
        }
    }

    return count
}swift

 

나는 풀이 1과 풀이 2를 Queue를 사용해서 풀었는데, 사실 정답은 Stack이었다. 😭 위 방법으로 풀면 굳이 요소끼리의 차를 구할 필요도 없고 그저 큰지 작은지 비교만 하면 된다.

1. 쌓을 벽돌(H[i])이 이전 벽돌(stack의 마지막 요소)보다 작으면 이전 벽돌(Stack의 마지막 요소)을 없앤다.
2. 쌓을 벽돌(H[i])보다 작은 벽돌이 나올 때까지 1번을 반복한다.

O(N)의 시간 복잡도로 간단하게 퍼포먼스 테스트도 통과했다.

사실 아직도 풀이 3을 완벽하게 이해하지 못했다. 분명 어려운 문제는 아닌데 문제에 대한 이해가 부족한 것 같다. 좀 더 살펴봐야지.