[PS][LeetCode][Swift] Push Dominoes

서론

놀랍게도 못풀었다..
삽질을 엄청 했는데, 처음에 문제를 잘못읽어서, RR.L 경우에 가중치가 필요하지않나?.. 라는 생각도 했고,
마지막에 투포인터까지 가는 과정에서는 양사이드로 미는 것 까지는 생각했는데, 길이로 문제를 해결하려고 했다.

최근에 DP 를 틀린 적이 없는데.. 틀리다니 꽤나 충격적이었다.

풀이를 보고 푼 것을 리뷰해보자.

문제

문제는 여기에 있다.

요는, 다음과 같다.
N개의 Vertical Dominoes가 존재하고, 동시에 방향성이 존재하는 도미노들을 넘어트린다.
도미노는 넘어지는 순간 방향에 따라 인접 도미노를 넘어트린다.

양쪽에서 도미노가 넘어져갈때, 힘(개수)의 균형을 가지는 도미노가 존재하게 된다.

분석

문제에서 제시된 바와 같이, 방향성이 있는 L, R 도미노들을 동시에 쓰러트리게 된다.
그렇게 되면, RRR...LL 이런 Dominoes가 있다고 존재하면,
왼쪽에서 세번 째 R, 그리고 맨 뒤에서 두번째 L만이 힘의 균형을 가지게 되는 도미노가 된다.

여기서 생각할수 있는것은 왼쪽 -> 오른쪽, 그리고 오른쪽 -> 왼쪽으로 한번씩 쓸고 지나면서 값을 업데이트 하는 방식을 생각해 볼 수 있다.

그래서 어떻게 쓸고 지나갈꺼야?

이게 좀 고민인데, (마지막 R, 최초 L) 그냥 R, L 을 어떻게 구분할것인지..
나는 처음에는 문제를 풀 때에는 R....L 과 같은 경우 둘 사이의 길이를 생각해서 별도의 배열에 Memoization 하는 방식을 생각했다.

하지만 이것은 잘못된게.. 처리를 해주면 되긴 하겠지만, RL 같은 짧은 케이스를 번호로 구분하기 힘들다는 점이 있다.

힌트를 보고 푼 과정에서는 point 변수를 dominoes를 슥 쓸면서, 지날때
왼쪽에서 오른쪽으로 가는 경우에는 "R"이 나오는 경우에 시작 하는 방향이니까 point 변수를 dominoes의 배열 크기만큼 설정해줬다.
그리고 종료 지점인 L 이 나오면 point를 비워주었고, 그 외에는 point 값을 한칸 씩 줄여 나갔다.

point를 내가 배열의 크기만큼 지정해준 이유는, 아무리 줄어도 배열의 크기에서 -> 0으로 가는 것은 배열 전체를 순회하면서 값을 줄여도 불가능하기 때문에, 값을 구별할수 있는 Unique성을 줄 수 있는 숫자라고 생각했기 때문이다.

그래서 코드로 한방향을 짜보면..

for c in dominoes {
    if c == "R" { point = N }
    else if c == "L" { point = 0 }
    else { point = max(point - 1, 0) }
    dp[i] += point
    i += 1
}

이런 방식으로 구현 해 볼수 있겠다.

결론

저런식으로 왼쪽-> 오른쪽, 오른쪽 -> 왼쪽 방향으로 쓸게 되면
예를들어, RR....LLL 이라는 문자열이 입력됐을 경우, 각 방향마다 DP에 저장 되는 값을 생각해보면

왼쪽 -> 오른쪽: 9 9 8 7 6 5 0 0 0

오른쪽 -> 왼쪽: 0 0 5 6 7 8 9 9 9

이런식으로 지정이 된다.

오른쪽에서 왼쪽으로 가는 경우를 음수라고 생각하고 더하게 되면..

최종 : 9 9, 3 1 -1 -3 -9 -9 -9

가 된다.

이런 경우 양수는 "R", 음수는 "L" 이 되는것을 확인할수 있고, 0인 경우에는 "." 으로 표현하면 답을 도출해 낼 수 있다.

전체 코드는 다음과 같다.

class Solution {
    func pushDominoes(_ dominoes: String) -> String {
        var N = dominoes.count
        var dp : [Int] = [Int](repeating: 0, count: N)
        var point = 0
        let range = 0..<N
        var i = 0
        for c in dominoes {
            if c == "R" { point = N }
            else if c == "L" { point = 0 }
            else { point = max(point - 1, 0) }
            dp[i] += point
            i += 1
        }
        
        i = dominoes.count - 1
        point = 0
        for c in dominoes.reversed() {
            if c == "L" { point = N }
            else if c == "R" { point = 0 }
            else { point = max(point - 1, -0) }
            dp[i] -= point
            i -= 1
        }
        
        var answer = ""
        for v in dp {
            if v > 0 {
                answer += "R"
            }else if v < 0 {
                answer += "L"
            }else {
                answer += "."
            }
        }
        return answer
    }
}

후기

힌트 보고 문제 풀면서, 이 쉬운걸 왜 못풀었을까.. 하는 자책감도 들었지만,
양방향 스위핑 하면서 누적합 구하듯 푸는 방식은 언제봐도 참 편하고 간단하다.
그런데 왜 항상 이런 간단한 문제를 어렵게 길이같은 요망한걸 들고와서 자폭하는지 모르겠다.