Swift ) 프로그래머스 (Lv3) - 방문길이 (Hash OR Set)

programmers.co.kr/learn/courses/30/lessons/49994

코딩테스트 연습 - 방문 길이

안녕하세요 후르륵짭짭 입니다.

굉장히 큰 도움이 된 문제라 가져왔습니다.

내일이면 네이버 코딩테스트인데,,, 또 떨어질까,,, 많이 걱정이 되네요 ㅠㅠ

시험 보기 전에 가장 기억 남는 문제를 가져왔습니다.

 

** 중첩 HASH **

저는 사실,,,, 이 문제를 어렵게 풀었습니다.

하지만 건질게 있는게, Dictionary in Dictionary 로 문제를 풀었습니다.

처음으로 이렇게 중첩 Hash를 사용해 보는 거라 많이 어색했지만 언젠간 도움이 될 것 같아서,,,

중첩 Hash를 사용한 이유는,,, 좌표를 저장 하기 위해서 였습니다.

그래서 처음에 Y에 해당하는 X 좌표들을 가져오고 해당하는 좌표에 URLD 방향을 저장하는 String 배열을 담았습니다.

//Y : [X]
    var dict : [Int : [Int : [String] ] ] = [:]

이렇게 말이죠!

잠시 예시를 보도록 하겠습니다. 

중첩 Hash를 사용하는데 고정된 값을 넣어줄 때는 아래 처럼 해주면 됩니다.

var dict : [Int : [Int : Int]] = [:]

dict[1] = [2:3,3:4]

print(dict[1]!)

//결과
[2: 3, 3: 4]

당황 했는데요. 처음에는 배열에 Hash 넣어줘야 싶었지만 사실은 그게 아니라 그냥 하나의 배열에 선언해주면 됐습니다.

일반적은 Dictionary 선언 처럼!

만약에 탐색과 삽입을 하고 싶다면 아래 처럼 이차원 배열과 같은 형태로 탐색해주고 삽입을 해주면 됩니다.

print(dict[1]![2]!)

dict[1]![4] = 5

print(dict[1]!)

//결과
3
[2: 3, 3: 4, 4: 5]

그래서 위와 같은 문제를 풀 때,

if let exist = dict[currentY] {
            
            if let list = exist[currentX] {
                
                if !list.contains(char) {
                    dict[currentY]![currentX]?.append(char)
                    currentFlag = true
                }
                
            }
            else{
                dict[currentY]![currentX] = [char]
                currentFlag = true
            }
            
        }
        else{
            dict[currentY] = [currentX : [char]]
            currentFlag = true
        }

이렇게, 현재 Y값을 가지고 있는 Dictionary 를 확인하고 없다면 새로운 값을 넣어주고

있는데 해당하는 X 값이 없다면 이차원 배열 형태로 삽입해주고

존재한다며 [String] 이기 때문에 추가해줬습니다.

 

** 문제 해설 **

이 문제를 풀었을 때, 한번에 통과 하지 못 했습니다.

그런데 LRLRLR를 해줬는데 결과가 1이 아니라 2가 나오는 것을 보고 잘 못 된 점을 찾았습니다. 

문제의 핵심은 "처음 걸어본 길" 이였습니다. 

처음에는 단순하게 단방향으로 생각했으나,,,, 양방향으로 생각해야 했습니다.

위의 그림 처럼 생각을 해줘야 합니다.

따라서 저는 중첩 해쉬를 두개 만들어서 

Current 에서 next로 가는 것 

next 에서 current로 가는 것

두가지의 경우로 길을 만들어줘서 둘다 간 적이 없을 때, 정답을 올려주는 방식으로 해결 했습니다.

-- 코드 -- 

func solution(_ dirs:String) -> Int {
    
    //Y : [X]
    var dict : [Int : [Int : [String] ] ] = [:]
    
    var currentX : Int = 0
    var currentY : Int = 0
    
    let dirsArray = Array(dirs).map{String($0)}
    
    var answer = 0
    
    for char in dirsArray {
        
        
        var nextX = currentX
        var nextY = currentY
        var nextChar = ""
        
        switch char {
            
        case "U":
            
            nextY = currentY + 1
            nextChar = "D"
            
        case "D":
    
            nextY = currentY - 1
            nextChar = "U"
            
        case "L":
            
            nextX = currentX - 1
            nextChar = "R"
            
        default:
            
            nextX = currentX + 1
            nextChar = "L"
        }
        
        print(currentY , currentX)
        print(nextY , nextX , answer)
        print()
        
        if !(-5...5).contains(nextY) || !(-5...5).contains(nextX) {
            continue
        }
        
        var currentFlag = false
        var nextFlag = false
        
        if let exist = dict[currentY] {
            
            if let list = exist[currentX] {
                
                if !list.contains(char) {
                    dict[currentY]![currentX]?.append(char)
                    currentFlag = true
                }
                
            }
            else{
                dict[currentY]![currentX] = [char]
                currentFlag = true
            }
            
        }
        else{
            dict[currentY] = [currentX : [char]]
            currentFlag = true
        }
        
        if let exist = dict[nextY] {
            
            if let list = exist[nextX] {
                
                if !list.contains(nextChar) {
                    dict[nextY]![nextX]?.append(nextChar)
                    nextFlag = true
                }
                
            }
            else{
                dict[nextY]![nextX] = [nextChar]
                nextFlag = true
            }
            
        }
        else{
            dict[nextY] = [nextX : [nextChar]]
            nextFlag = true
        }
        
        
        if nextFlag && currentFlag {
            answer += 1
        }
        
        
        currentY = nextY
        currentX = nextX
        
    }
    
    return answer
}

 

** 더 좋은 코드 **

저는 Hash로 풀었는데,,,,, 사실 String으로 Set으로 하면 쉽게 해결 할 수 있는 문제였습니다.

Set의 특징은 중복된 것은 들어 올 수 없다는 특징이 있습니다. 

따라서 현재에서 미래로 가는 것은 자동으로 중복 체크를 해주기 때문에

미래에서 현재로 가는 것만 확인 해주면 됩니다.

String으로 경우로 만들고 Set으로 중복 문제를 해결하면 쉽게 해결 할 수 있었는데,,, 

저는 너무 직관적으로 해결하려 했습니다 ㅎㅎㅎㅎ

 

김기현님의 코드 입니다.

func solution(_ dirs:String) -> Int {
    var current = (0, 0)
    var set = Set<String>()
    let direction = dirs.map { String($0) }

    for str in direction {
        var point = current
        var row = point.0
        var col = point.1

        if str == "U" {
            col += 1
        } else if str == "D" {
            col -= 1
        } else if str == "L" {
            row -= 1
        } else if str == "R" {
            row += 1
        }

        if col > 5 || col < -5  {
            continue
        }

        if row > 5 || row < -5 {
            continue
        }

        point.0 = row
        point.1 = col

        if !set.contains("\(point)\(current)") {
            set.insert("\(current)\(point)")
        }
        current = point
    }

    print("set: \(set)")

    return set.count
}