프로그래머스 구현문제, Lv2 스킬트리 swift 풀이

 

 

 

 

---

프로그래머스 Lv2 구현문제, 스킬트리

스킬트리문제는 스킬과 스킬트리 리스트가 주어졌을때 유효한 스킬트리가 몇개인지를 구하는 문제입니다.

 

여기서 핵심은 스킬은 규칙 순서대로 사용을 해야합니다. 만약 사용순서대로 사용을 하지 않으면 해당 스킬트리는 유효하지 않습니다.

위의 스킬트리를 보면, "CBD"의 순서로 사용을 하는 스킬트리는 각각 "CBADF", "AECB"가 됩니다. 마지막 "BDA"는 'C' 스킬을 선행으로 사용하지 않았기 때문에 유효하지 않죠. 

 

바로 이어서 swift언어를 사용해서 구현문제, 스킬트리문제 풀어보도록 하겠습니다.

 

 

 

---

프로그래머스 Lv2 구현문제, 스킬트리 swift 풀이
extension Character

먼저 extension 구현을 몇개 하겠습니다. Character타입의 인덱스를 반환하는 메서드, asciiIndex입니다. 대문자 영문의 인덱스(0 ~ 25)를 반환합니다. 

 

 

 

extension Array

extension Array 구현부 입니다. 

9행) prev는 이전에 사용한 스킬의 영문 인덱스를 갖습니다. 순서대로 스킬을 사용중인지 체크하는데에 사용합니다.

10행) skillTree를 순회하면서 순서대로 스킬을 사용하는지 체크해보겠습니다. 

11 ~ 15행) dicList는 순서대로 사용할 스킬의 사용 순서를 기록해두고 있습니다. 현재 순회중인 skill의 asciiIndex를 접근했을때 now값이 0보다 크면 사용규칙에 있는 스킬입니다. (자세한 내용은 아래 solution 구현부 설명을 참고하세요.) 만약 규칙에 있는 스킬인데, 사용규칙이 위배되는 경우 false를 반환합니다. 

prev + 1 == now여야 올바른 순서로 스킬을 사용함을 의미합니다. 그러므로 반대인 prev + 1 != now의 경우 false를 반환할 수 있습니다.

16행) 만약 now의 값이 0 이상(규칙에 있는 스킬)이면 prev에 저장을 해서 다음 스킬을 체크합니다. 

이렇게 모든 skillTree의 순회과정을 거치고도 문제가 없다면, 문제가 없는 스킬트리이므로, true를 반환합니다.

 

이어서 마지막으로 solution 메서드를 구현해보겠습니다.

 

 

25행) 먼저 skill을 [Character] 타입의 배열로 만들어줍니다. 시간복잡도 O(1)로 첨자접근을 통한 값 추출이 용이하기 때문에 변환했습니다.

26행) dicList는 앞서 extension Character 에서 사용했죠? 규칙에 있는 스킬의 사용순서를 기록할 배열입니다. 

27 ~ 31행) 규칙이 있는 스킬의 사용순서를 dicList에 기록하고 있습니다. 이때 Character 익스텐션에서 구현한 assciiIndex를 사용하고 있죠?

33 ~ 35행) 유효한 스킬트리의 갯수를 reduce 함수를 통해 반환하는 코드입니다. 각 skillTree가 유효한지 앞서 Array extension 에서 구현한 isValid 메서드를 통해 체크하고, 유효하면 1을 누적시킵니다. 최종적으로 유효한 스킬트리의 갯수를 반환하고 함수는 종료합니다.

 

최종적으로 해당 문제는 O(N)의 시간복잡도(time complexity)로 풀 수 있었습니다. 
아래는 최종 제출결과 및 swift 전체코드 입니다. 좋아요(?) 부탁드리고, 의견 및 질문 환영합니다. 😁

 

 

 

extension Character {
    var asciiIndex: Int {
        return Int(self.asciiValue!) - 65
    }
}

extension Array where Element == Character {
    func isValid(skillTree: String, dicList: inout [Int]) -> Bool {
        var prev = 0
        for skill in skillTree {
            if dicList[skill.asciiIndex] > 0 {
                let now = dicList[skill.asciiIndex]
                if now != 0 && prev + 1 != now {
                    return false
                }
                prev = now > 0 ? now : prev
            }
        }

        return true
    }    
}

func solution(_ skill:String, _ skill_trees:[String]) -> Int {
    let arr = Array(skill)
    var dicList = [Int](repeating: 0, count: 26)
    var cnt = 1
    skill.forEach { char in
        dicList[char.asciiIndex] = cnt
        cnt += 1
    }
    
    return skill_trees.reduce(into: 0) { (answer, skillTree) in
        answer += arr.isValid(skillTree: skillTree, dicList: &dicList) ? 1 : 0
    }
}