iyOmSd/Title: Algorithm풀이

[Swift Algorithm] 49994 방문길이 (프로그래머스)

냄수 2021. 3. 5. 20:52
반응형

 

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

 

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

 

programmers.co.kr

풀이방법

범위가 여유있기때문에 생각하기 쉬운편에 속하는 문제였어요 

 

UDRL 문자대로 움직이고

중복되는 라인은 세지않고

범위를 넘어가지않도록 넘어갈경우 제자리!

 

튜플(Int, Int)를 이용해서 하려고했지만

Set<(Int, Int)>

튜플이 Hashable하지않아서 Set에는 사용할 수 없더라구요

 

그래서 구조체를 만들어서 사용햇고

선분은 (1,0) - (0,0) 을 연결한것과 (0,0) - (1,0)을 연결한 것이 같기때문에

== 연산자를 구현해주면 Set에서 걸러질줄 알았는데 안걸러지더라구요

그래서 한번은 그대로 한번은 순서를 바꿔서 2개씩 저장했어요

 

양방향을 Set에 저장해놓고

중복되지않는 선분 수는 마지막에 나누기 2만해주면

잘나오겠죠?!

 

private func solutionP49994(_ dirs:String) -> Int {
    struct Position: Hashable {
        var x: Int
        var y: Int
    }
    struct Line: Hashable {
        var point1: Position
        var point2: Position
        
        static func == (lhs: Line, rhs: Line) -> Bool {
            (lhs.point1 == rhs.point1 && lhs.point2 == rhs.point2) ||
                (lhs.point1 == rhs.point2 && lhs.point2 == rhs.point1)
        }
    }
    
    var visited = Set<Line>()
    var position: Position = Position(x: 0, y: 0)
    
    // 이동
    func move(c: Character) {
        switch c {
        case "U":
            if position.y == 5 {
                return
            }
            position.y += 1
        case "D":
            if position.y == -5 {
                return
            }
            position.y -= 1
        case "R":
            if position.x == 5 {
                return
            }
            position.x += 1
        case "L":
            if position.x == -5 {
                return
            }
            position.x -= 1
        default:
            break
        }
    }
    // 주어진 문자에 맞게 순회
    dirs.forEach {
        let origin = position
        move(c: $0)
        if origin != position {
            visited.update(with: Line(point1: origin, point2: position))
            visited.update(with: Line(point1: position, point2: origin))
        }
    }

    return visited.count/2
}

 

반응형