프로그래머스 LV.1 달리기 경주 스위프트

 

코드 실행을 통과한다고 답은 아니다... 

문제에 1,000,000의 조건이 있으면 시간 복잡도를 생각해보자 

 

자 그럼 시작해보겠습니다. 

 

지문을 보면 

 

어렵지만은 않은 지문입니다.

이름이 불리면 한칸씩 앞으로 간다 ,  앞 칸에 있던 것은 뒤로 한칸 밀린다. 

즉, index -1 , 앞에 있던 문자 index +1

이게 포인트 인거 같습니다. 

 

자 그러면 한번 적어보겠습니다. 

for i in 0..<callings.count {
	 if let number = result.firstIndex(of: callings[i]) {
	 result[number] = result[number-1]
	 result[number-1] = callings[i]
 	}
 }
 
 print(result)

 

처음에는 요런 느낌으로 적어봤는데요

이렇게 쉽게 해치웠나...?

 

네 어림 반푼어치도 없었습니다 ㅋㅋㅋㅋㅋㅋ

 

시간초과가 날때 푸는 많은 방법이 있는데요

저는 딕셔너리를 사용해서 풀었습니다. 

 

왜 딕셔너리를 사용해서 풀었나요? 

이유는 !!

배열은 순서가 있기 때문에  하나씩 다 체크합니다. 

하지만 딕셔너리는 순서가 없고 해시 테이블로써

 

입력값(key)를 해시함수를 통해 해시하고,

출력값(value)는 해시 주소 값에 해당하는 해시 테이블 슬롯을 저장

 

흠... 무슨말인지 모르겠네요 

쉽게 설명해서 딕셔너리는  (key, value) 값으로 이뤄지잖아요?

 

key값이 주어지면 value값을 출력한다고 생각하면 됩니다. 

근데 이게 배열보다 속도가 빠르다!!

당연하죠 배열은 하나씩 다 비교 해가면서 확인 하는데,

딕셔너리는 키값에 해당하는 것만 확인하니까요 

var example: [String: Int] = ["예시1" : 1, "예시2" : 2, "예시3" : 3]
 print(example["예시1"])
 
 // Optional(1)

자 이렇게 말이죠

 

일단 배열과 딕셔너리에 대한 자세한 포스팅은 나중에 다루도록 하겠습니다.

 

 

문제로 돌아오면 

 

일단 담아줄 변수를 만들어 줍니다.

// 등수가 바뀌기 때문에 변수로 할당
var result: [String] = players
// 딕셔너리 형태로 문자 : Int 담아주기 
var callingDic: [String:Int] = [:]

 

매개변수로 주어진 players는 let이기 때문에

변수로 담아줍니다.

하나씩 담기는 빈 딕셔너리를 만들어줍니다. 

 

 

그렇다면 딕셔너리에는 어떤걸 넣어야 할까요?

 

바로 .. !!

players에 대한 인덱스와 문자를 딕셔너리에 넣어주면 됩니다. 

    for (index, player) in players.enumerated() {
        callingDic[player] = index
    }
    print("callingDic:",callingDic)
    
    // callingDic: ["poe": 2, "mine": 4, "soe": 1, "mumu": 0, "kai": 3]

 

callingDic의 value 부분은 players의 문자들의 인덱스 입니다. 

["mumu", "soe", "poe", "kai", "mine"] 
mumu: 0
soe: 1
poe: 2
kai: 3
mine: 4

여기까지는 참 쉽죠? 

 

 

자 그렇다면 

이름이 불리면 한칸씩 앞으로 간다 ,  앞 칸에 있던 것은 뒤로 한칸 밀린다. 

즉, index -1 , 앞에 있던 문자 index +1

이 부분을 적용해봅시다.

 

딕셔너리에 있는 callingDic을 하나씩 가져올때 result에 있는 인덱스를 -1 하고 , 인덱스의 앞에 있는 것에 +1을 해서 바꿔준다.

쉽게 이해하자면 

혹시 swap라는 함수 하시나요??

result.swapAt(index, index-1)
index를 index-1로 바꿔준다.

var example = [1, 2, 3, 4, 5]
// 배열의 인덱스를 적어줍니다.
example.swapAt(1, 2)

print(example)

// [1, 3, 2, 4, 5]

 

네 그렇습니다. 그럼 코드를 작성해보겠습니다.

 

그러면 이렇게 시작하면 될까요??

for (index,value) in callingDic {
	~ 블라 블라
    ~ 블라 블라
}

 

자 이렇게 생각하신 분들... 푸쳐핸섭!

callingDic을 print해보세요

print("callingDic:",callingDic)

// callingDic: ["poe": 2, "mine": 4, "soe": 1, "mumu": 0, "kai": 3]
// callingDic: ["mine": 4, "soe": 1, "mumu": 0, "poe": 2, "kai": 3]
// callingDic: ["kai": 3, "mine": 4, "mumu": 0, "poe": 2, "soe": 1]
// callingDic: ["soe": 1, "kai": 3, "mumu": 0, "mine": 4, "poe": 2]
// callingDic: ["mumu": 0, "poe": 2, "kai": 3, "soe": 1, "mine": 4]

네! 눈치 채신분들도 있겠지만

순서가 없이 랜덤으로 프린트가 됩니다. 

그러면 당연히 for문을 돌릴때도 값이 계속 바뀌면서 나오겠죠?

 

네! 매개변수로 주어진 callings를 기준으로 for문을 돌리고,

딕셔너리의 value 값만 뽑아서 쓰면 됩니다. 

이렇게 생각하신 분들 Good!

// ["kai", "kai", "mine", "mine"]
for i in callings {
	// 딕셔너리로 되어 있는 것에서 키값을 기준으로 value를 뽑아냅니다. 
    // ex) callingDic["kai"] = 3
    // 이렇게 하면 callings안에 있는 요소의 순서대로 뽑아 callingDic의 순서를 만들 수 있습니다.
    let index = callingDic[i]
    // 해당 index 앞의 문자가 무엇인지 알기 위해서 index - 1을 사용하여 변수 만들기
    let forent = result[index-1]
}

 

저희는 players를 활용해서 딕셔너리를 만들었습니다.

그래서 딕셔너리에는 players의 인덱스 순서가 들어가 있죠 

players = ["mumu", "soe", "poe", "kai", "mine"]
callingDic: ["mumu": 0, "poe": 2, "kai": 3, "soe": 1, "mine": 4]

이렇게 말이죠 

"soe"의 index -1 은 "mumu"가 되겠죠?

"kai"의 index-1은 "poe"가 되겠죠?

 

이런식으로 구하면 됩니다. 

// ["kai", "kai", "mine", "mine"]
for i in callings {
	// 딕셔너리로 되어 있는 것에서 키값을 기준으로 Int를 뽑아냅니다.
    let index = callingDic[i]
    // 해당 index 앞의 문자가 무엇인지 알기 위해서 index - 1을 사용하여 변수 만들기
    let forent = result[index-1]
    
    // 해당 index와 forent의 자리를 바꿔줍니다.
    result.swapAt(index, index-1)
    print("result:",result)
}

/*
callingDic: ["soe": 1, "mine": 4, "mumu": 0, "kai": 3, "poe": 2]
result: ["mumu", "soe", "kai", "poe", "mine"]
result: ["mumu", "soe", "poe", "kai", "mine"]
result: ["mumu", "soe", "poe", "mine", "kai"]
result: ["mumu", "soe", "poe", "kai", "mine"]
*/

 

프린트를 해서 확인을 해보니...

뭔가 이상하네요 원하는 값이 아닌데... 

 

확인을 해보니 

기준이 callingDic의 value값에 따라 swap가 되는것을 확인할 수있습니다. 

아! 그렇다면 한번씩 돌때마다 value 값을 +1,  -1 해주면 되겠다.

// ["kai", "kai", "mine", "mine"]
for i in callings {
	// 딕셔너리로 되어 있는 것에서 키값을 기준으로 Int를 뽑아냅니다.
    let index = callingDic[i]
    // 해당 index 앞의 문자가 무엇인지 알기 위해서 index - 1을 사용하여 변수 만들기
    let forent = result[index-1]
    
    // 해당 index와 forent의 자리를 바꿔줍니다.
    result.swapAt(index, index-1)
    
    // 해당 key에 해당하는 value값 -1 해주기 왜냐하면 swap를 통해 위치가 바꼈기 때문에
    callingDic[i] = callingDic[i]! - 1
    // swap를 통해 앞의 인덱스도 바뀌기 때문에
    callingDic[forent] = callingDic[forent]! + 1
    print("callingDic:",callingDic)
}

/*
callingDic: ["poe": 3, "kai": 2, "mine": 4, "soe": 1, "mumu": 0]
callingDic: ["poe": 3, "kai": 1, "mine": 4, "soe": 2, "mumu": 0]
callingDic: ["poe": 4, "kai": 1, "mine": 3, "soe": 2, "mumu": 0]
callingDic: ["poe": 4, "kai": 1, "mine": 2, "soe": 3, "mumu": 0]
*/

 

자 이렇게 해서 해당 인덱스 값이 바뀌는 것을 볼 수 있습니다.

그렇다면 마지막에 나온 callingDic의 값의 value가 순서 입니다.

 

정리해보면

["mumu", "kai", "mine", "soe", "poe"]

이렇게 만들어집니다. 저희는 그것을 result.swap를 통해 만들어 왔습니다.

 

 

 

최종 코드 입니다. 

func solution(_ players:[String], _ callings:[String]) -> [String] {
    
    var result: [String] = players
    var callingDic: [String:Int] = [:]

    for (index, player) in players.enumerated() {
        callingDic[player] = index
    }
    print("callingDic:",callingDic)
    
    
    for i in callings {
        var index = callingDic[i]
        var forent = result[index!-1]
        
        result.swapAt(index!, index!-1)
       
        callingDic[i] = callingDic[i]! - 1
        callingDic[forent] = callingDic[forent]! + 1
        print("callingDic:",callingDic)
    }
    
    print("최종 result:",result)
    
    return result
}

 

한줄 평: 맛있게 딕셔너리 배웠다. 냠냠