[Leetcode] 838. Push Dominoes

문제 : https://leetcode.com/problems/push-dominoes/description/

 

---

배열을 하나 만들어서 문자열 길이만큼 0을 채운다.

이 배열에 L이라면 음수를, R이라면 양수를 채울 것이다. '.' 인 경우는 0.

'L', 'R'을 만나서 배열을 갱신할 때 시작점과 얼마나(인덱스) 떨어져 있는지 저장한다.

문자가 'L'이라면 왼쪽으로 가면서 -1, -2, -3 … 이런식으로 다음 문자를 만날 때까지 채워준다.

'R'이라면 오른쪽으로 가면서 1, 2, 3 … 을 다음 문자를 만날 때까지 채워준다.

문자가 있는 부분은 양수나 음수로 적절히 채운다. 나는 L은 '-1', R은 '1'을 채워줬다.

주의할 점이 2가지 있다.

 

1. "R . . . L"

이 경우 정답은 "R R . L L"이 된다.

위의 알고리즘대로 채우면 처음에는 "1 1 2 3 0" 이 채워진다. ("R R R R .")

다음 L을 탐색하면서 채우면 "1 -3 -2 -1 -1"이 된다. ("R L L L L")

정답과 다르다.

배열에는 도미노의 시작점과의 거리를 저장했으므로 만약 기존 배열에 존재하는 값과 더하려는 값의 합이 0이라면 좌우 대칭으로 R, L이 존재한다는 의미가 된다.

따라서 그 합이 0인 경우 배열 값을 0으로 만들고(.) 그 이후는 탐색하지 않는다.

이렇게 갱신한 배열은 "1 1 0 -1 -1"("R R . L L")이 된다.

 

2. "R . . L"

이 경우 정답은 "R R L L"이 된다.

1번 알고리즘대로 채우면 처음에는 "1 1 2 0" 이 채워지고 ("R R R .") L을 탐색하면서 채우면 "1 -2 -1 -1"이 된다. ("R L L L")

L을 채울 때 합 0이 나오지 않아서 끝까지 채워지게 되는 것이다.

배열에 이미 값이 있는 경우(0이 아닌 경우) 더하려는 값과 비교해보자.

위의 예시에서 2번째 인덱스를 보자. "R R R ." = "1 1 2 0", "R L L L" = "1 -2 -1 -1"

2번째 인덱스를 더하면 -1이 된다. 이는 R보다 L이 더 멀리서 시작되었다는 뜻이다. 따라서 더 가까이에서 시작된 R이 정답이 되어야 한다.

그래서 조건을 하나 더 추가하여 값이 이미 있는 경우 그 값과 갱신하려는 값을 비교해서 더 멀리서 시작된 경우로 갱신하고자 하는 경우 갱신을 그만둔다.

 

문자열을 탐색하면서 배열을 완성시켰을 때, 해당 배열을 앞에서부터 탐색하면서

0인 경우 '.' 양수인 경우 'R' 음수인 경우 'L'을 정답 문자열에 채워나간다.

 

---

소스코드 : https://gist.github.com/fpdjsns/eeb1e3297d283c6999e7fa486124649a