[프로그래머스/Swift] level2 - 스킬트리 | PS일지

 

문제

프로그래머스

간단한 문제 요약

스킬을 배우려면 사전에 선행스킬을 먼저 배워야 합니다.

 

예를들어 스킬트리: 스파크 -> 라이트닝 볼트 -> 썬더. 최종적으로 썬더를 배우기 위해선 그 이전에 스파크를 배운 후에, 라이트닝 볼트를 배워놔야 합니다. 스파크를 배우지 않았다면 라이트닝 볼트를 배울 순 없습니다. 

 

위 스킬트리 중간 중간에 다른 스킬은 순서에 상관없이 많이 배울 수 있습니다.

스파크 -> 힐링1 -> 힐링2 -> 라이트닝 볼트

 

고려해야 할 사항

• 예를들어 C -> B -> D라면 "CBD"로 표기합니다.

문제 풀이 | PS일지

특정 스킬을 배울 때, visited 배열을 통해서 그 이전에, 배워야 할 skill들이 다 true(배웠는지)가 되어 있는지 조건 체크 후에 해당 스킬을 배우는 방식으로 문제를 접근해나갔습니다. 

코드

 

func solution(
  _ skill:String,
  _ skill_trees:[String]) -> Int {
    let list = skill.map{String($0)}
    var res = 0
    skill_trees.map{ input in
      var visited = Array(repeating: false, count: list.count)
      var skillTree = input.map{String($0)}
      for (i,char) in skillTree.enumerated() {
      //1.
        if list.contains(char),
           let idx = list.firstIndex(of: char)
        {
          var flag = true
          //2.
          for ind in (0..<idx) {
            if !visited[ind] { flag = false }
          }
          //3.
          if !flag { break }
          visited[idx] = true
        }
        if i == skillTree.count-1 { res += 1 }
      }
    }
  return res
}

 

저는 모든 문자열을 각각의 배열로 변환해서 일치하는지 비교해나갔습니다.

 

1. 특정 skillTree는 skill의 문자열을 포함하는가?

2. 방문체크에서 skill의 앞에 있는 스킬들을 다 배웠는가?

3. 만약 앞에있는 스킬을 배우지 않은 스킬이 한개라도 존재한다면 flag를 false로 만들고, 만약 flag가 false가 아니라면, 현재 스킬은 배워도 됨으로 visited를 true로 한 후에 다음 스킬을 판별합니다.

 

 

 

다른분들의 코드를 보며 개선점을 찾았습니다. 이 문제의 요지는 엄청 많이 배운 스킬이 있는데, 그 중에서 결론적으로 스킬트리대로 배웠는지 여부가 제일 중요한 것 같습니다. 그리고 이를 문자열로 접근하는 방법이 대단했습니다.( 빨리 문자열과 친숙해 져야할텐데..)

 

func solution(
  _ skill:String,
  _ skill_trees:[String]) -> Int {
    //1.
    return skill_trees.filter {
      //2.
      let filtered = $0.filter {
        //3.
        return skill.index(of: $0) != nil
      }
      //4.
      return skill.hasPrefix(filtered)
    }.count
    
  }

 

1. 특정 조건에 skill_trees배열을 filter해서 일치하는 조건의 값을 반환한다.

3. 배웠던 각각의 스킬배열에서 스킬트리(skill)에 일치하는 스킬들만 반환한다. ( 어차피 어느 스킬을 배웠던, 스킬트리에 해당되지 않는 스킬들이면 순서 상관없이 스킬을 배워도 되기 때문에, 지금 중요한 것은 스킬트리에 포함되는 스킬들이 스킬트리 대로 배웠는가? 입니다.)

2.  3의 조건대로 스킬트리에 존재하는 스킬들로 구성이 되어있는 문자열을 filtered로 받습니다. 

 

예를들어

skill == "ABD"

특정 skill_tree == "BCDEFGF"

 

여기서 2의 조건 이후 filtered된 문자열은 BD가 됩니다.

결국 이 두 스킬들은 스킬트리(skill)를 만족하는가? 입니다. A를 배웠는가? 이는 skill의 prefix와 일치한다면 스킬트리대로 배웠구나, 아니구나 임을 확인할 수 있습니다....

 

새로 알게된 점

filter연산자를 통해서도 map과 같은 기능으로 사용할 수 있는데 차이점은 결국 특정 조건에 따른 true, false를 반환하는 것입니다. 이 문제같은 경우 각각의 case에 대해서 맞으면 true, 틀리면 false를 통해 true의 개수를 파악하는 것이 답이므로 filter를 통해 문제를 접근해 나갈 수 도 있다는 것이 정말 신기했습니다.