본문 바로가기
Algorithm/문제풀이_프로그래머스

[Swift][문자열][LV2][프로그래머스] 스킬트리

by Joahnee 2021. 11. 18.

요구능력 : 문자열에 대한 이해

 

코드설명 : 

이 문제의 해답을 보기전에 꿀팁.

이런문제는 사람들마다 문제푸는 스타일이 천차만별일것이라,, 코드해석이 어려울 수 있다.

그럴때는 그냥 혼자서 생각하고 디버깅하면서 푸는게 최고다.

 

이 문제에서의 핵심을 짚어보자.

1. 문자열을 Character로 분해

2. 배열에서 문자열의 인덱스 활용

3. 선행스킬의 존재여부

 

변수가 너무 많아서 변수부터..

skillSplit : skill입력을 캐릭터자료형으로 분해해놓은 캐릭터배열

before : 이전에 나온 스킬의 인덱스를 저장한다.

isSkill : 스킬트리가 스킬트리로서의 조건들을 만족하는지 안하는지

count : 조건들을 만족하는 스킬트리의 개수

beforeSkill : 이전에 선행으로 배워야하는 스킬

skillTree : skill_trees에 있는 스킬트리배열들 중 순서대로 하나씩 분해해서 저장

 

1. 문자열을 Character로 분해

문자열을 캐릭터자료형으로 분해하는건 for문을 이용하여 쉽게 가능하다.

요런식으로..

for i in skill{
        skillSplit.append(i)
    }

 

2, 3. 

이게 이 문제의 전부나 마찬가지이다.

스킬을 분해해놓은 skillSplit에서 하나씩 빼서 현재 skillTree에 존재하는지 확인해주고 존재한다면 이전 인덱스보다 크거나 같은지 확인해준다. 이유는 skillSplit은 ["C","B", "D"]가 들어있다고 가정해보자. 그리고 SkillTree에는 ["B", "A", "C", "D", "E"]가 존재한다.

그럼 처음으로 나오는 C가 당연히 B보다 앞에 있어야한다.

그래서 SkillTree에서 C를 먼저찾고 인덱스를 저장해둔다음, 다음번에 B가있으면 C가 선행스킬이기 때문에 before(C의 인덱스)가 index(B의 인덱스) 보다 작아야한다.

 

그리고 예제에서 ["B", "D", "A"]의 경우에는 B의 선행스킬인 C가없다.

나는 이걸 beforeSkill로 선행스킬을 저장해두고 문제를 풀었다.

beforeSkill에는 우선 맨 처음 선행스킬인 skillSplit[0]을 넣어두고 문제를 푼다.(안넣어두면 치환이안됨)

그리고 skillTree에 B가 있는지 확인한다.

어차피 맨 처음 선행스킬이 없다면 스킬트리가 조건을 만족하지 못하므로 isSkill을 false로 준다.

그리고 beforeSkill에 현재 스킬을 넣어준다. (다음 스킬이 선행스킬을 충족하는지 확인하기위해서임)

skillTree가 skillSplit스킬을 갖고있지 않더라도 선행스킬을 j로 초기화해준다.

이유는 선행스킬을 계속해서 초기화해줘야지만 다음번 스킬에서 isSkill을 false로 줄 수있다.

만약 인덱스가없을때 beforeSkill을 초기화해주지않으면 다음번 스킬에서 isSkill이 true로 되어있어서 카운트하게된다. 

for j in skillSplit{
            if let index = skillTree.firstIndex(of: j){
                if before <= index{
                    before = index
                    if !skillTree.contains(beforeSkill){
                        isSkill = false
                    }
                    beforeSkill = j
                }else if before > index{
                    isSkill = false
                    break
                }
            }else {
                beforeSkill = j
            }
        }

 

후기 : 문자열 문제라서 범위자체가 작게 설정되서 다행이다.

코드개판..시간복잡도개판...😂

func solution(_ skill:String, _ skill_trees:[String]) -> Int {
    var skillSplit:[Character] = []
    for i in skill{
        skillSplit.append(i)
    }
//    print(skillSplit)
    var before = 0
    var isSkill = true
    var count = 0
    var beforeSkill: Character = skillSplit[0]
    for i in skill_trees {
        var skillTree: [Character] = []
        for k in i{
            skillTree.append(k)
        }
//        print(skillTree)
        for j in skillSplit{
            if let index = skillTree.firstIndex(of: j){
                if before <= index{
                    before = index
                    if !skillTree.contains(beforeSkill){
                        isSkill = false
                    }
                    beforeSkill = j
                }else if before > index{
                    isSkill = false
                    break
                }
            }else {
                beforeSkill = j
            }
        }
        if isSkill{
            count += 1
        }
        
        isSkill = true
        before = 0
        beforeSkill = skillSplit[0]
    }
    
    return count
}

댓글