(Swift) Programmers 방문 길이

SteadySlower·2023년 1월 24일

programmers swift

Coding Test

목록 보기

214/305

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

문제 풀이 아이디어

Level 2 문제인데 배울 내용이 상당히 많은 문제였습니다. 이 문제의 포인트는 “길”을 어떤 자료형으로 어떤 자료형에 저장할 것인가입니다.

“길 = (선)”을 어떻게 저장할 것인가?

보통 문제에서 이렇게 좌표평면이 나오면 무조건반사(?)로 이차원 배열을 떠올리기 마련입니다. 저 역시도 바로 Array로 이차원 배열을 구현해서 풀 생각이었습니다. 이차원 배열에 지나간 길을 표시하고 그 길을 갯수를 세어서 정답을 구할 생각이었습니다.

하지만 이차원 배열은 기본적으로 좌표 (= 점)을 저장하는 자료구조입니다. 문제는 우리가 저장해야 하는 것 길이라는 것이죠. 길의 경우 출발점과 도착점이 있습니다. 그리고 출발점과 도착점이 서로 뒤바뀌더라도 같은 길로 간주합니다.

처음에 저는 2개의 이차원 배열을 선언해서 각각 수직, 수평의 길을 저장하기로 하고 수직의 길의 경우 y좌표가 더 작은 점을 저장하고 수평의 길의 경우 x좌표가 더 작은 점을 저장해서 길을 저장하려고 했습니다. 하지만 쉽지 않았습니다.

약간의 발상의 전환으로 길을 쉽게 저장할 수 있습니다. 일단 이차원 배열을 잊어버립시다. 그리고 출발점과 도착점이 서로 뒤바뀌어도 동일한 길이므로 출발점+도착점을 저장하고 도착점+출발점을 동시에 저장하는 것입니다. 이렇게 하면 같은 길이 2번 저장되게 됩니다. 이렇게 하고 마지막의 길의 갯수를 구할 때는 2로 나누어 주는 것입니다.

이렇게 하면 중복을 제거할 수 있는 Set 자료형도 사용할 수 있어서 훨씬 수월하게 중복을 체크할 수 있습니다.

Set의 원소는 Hashable

Swift의 Set의 원소는 Hashable 프로토콜을 준수해야 합니다. 저장하고자 하는 것은 좌표니까 tuple 타입을 사용하는 것이 쉽지만 아쉽게도 tuple은 Hashable이 아닙니다. 따라서 좌표를 String으로 바꾸어서 저장하도록 합시다.

코드

func solution(_ dirs:String) -> Int {
    // dir 별 좌표 변화 저장
    let moves = [
        "L": (-1, 0),
        "R": (1, 0),
        "U": (0, 1),
        "D": (0, -1),
    ]
    
    // 지난 길을 저장할 Set (중복 x)
    var routes = Set<String>()
    let dirs = dirs.map { String($0) }
    
    // 처음 위치 = 원점
    var x = 0, y = 0
    
    for dir in dirs {
        // 이동을 하고
        let nx = x + moves[dir]!.0, ny = y + moves[dir]!.1
        // 이동을 한 위치가 주어진 영역 안이라면
        if (-5...5) ~= nx && (-5...5) ~= ny {
            // 지난 길을 저장하는데 "원위치 -> 이동위치", "이동위치 -> 원위치"의 2가지로 저장한다.
            routes.insert("\(x)\(y)\(nx)\(ny)")
            routes.insert("\(nx)\(ny)\(x)\(y)")
            // 그리고 현재 위치를 변경
            x = nx
            y = ny
        }
    }
    
    // "원위치 -> 이동위치", "이동위치 -> 원위치"의 2가지로 저장했으므로 2를 나누어 준다.
    return routes.count / 2
}