1. 문제 소개

2211. Count Collisions on a Road

2. 나의 풀이

배열을 순회해서 충돌하는 횟수를 카운팅했다.
중요한 점은 배열의 시작에서 연속적으로 오른쪽으로 이동하는 차들을 추적해야햔다.
시간복잡도는 $O(n)$이다.

class Solution:
    def countCollisions(self, directions: str) -> int:
        n = len(directions)          # 문자열 길이(사용하진 않지만 입력 크기 정보)

        ans, state = 0, directions[0]  # ans: 총 충돌 횟수, state: 왼쪽 구간의 "마지막 상태"
        r_cnt = 0                    # r_cnt: 아직 멈추지 않고 오른쪽으로 달리는 'R' 차량의 개수

        for i, d in enumerate(directions):  # 각 위치 i에서 차량 상태 d를 순회
            if d == "R":
                # 새로운 'R'을 만나면, 오른쪽으로 진행 중인 R 차량 수를 1 증가
                r_cnt += 1
                state = "R"           # 최근 관찰 상태를 'R'로 설정 (왼쪽에 달리는 차가 있다는 의미)

            elif d == "S":
                # 정지 상태 'S'를 만나면,
                #   - 왼쪽에서 달려오던 모든 'R'들이 이 위치에서 멈추며 각각 1번씩 충돌한다.
                ans += r_cnt          # 달리고 있던 R 개수만큼 충돌
                r_cnt = 0             # 모두 멈췄으므로 더 이상 진행 중인 R은 없음
                state = "S"           # 이 위치에 정지한 차가 존재하므로 상태를 'S'로 고정

            else:
                # d == "L" 인 경우 (왼쪽으로 이동하는 차량)
                if r_cnt > 0:
                    # 왼쪽에 아직 멈추지 않은 R 차량들이 있다면:
                    #   - 패턴: ... R R R L
                    #   - 이 L은 가장 오른쪽 R과 먼저 부딪혀 1번 충돌 후 멈추고(S),
                    #   - 나머지 R 들은 이 정지 상태 'S'에 차례대로 부딪히며 각각 1번씩 더 충돌한다.
                    #   → 총 충돌 횟수: r_cnt(각 R) + 1(L이 부딪힐 때) = r_cnt + 1
                    ans += r_cnt + 1  # 연쇄 충돌 횟수를 한 번에 반영
                    r_cnt = 0         # 모든 R이 멈췄으므로 진행 중인 R 없음
                    state = "S"       # 충돌 이후 이 위치는 정지 상태 'S'

                else:
                    # 왼쪽에 진행 중인 R이 하나도 없는 경우:
                    #   - 이 L은 왼쪽 끝으로 그냥 빠져나가거나,
                    #   - 혹은 이미 정지 상태 'S'와 부딪힐 수도 있다.
                    if state == "S":
                        # 바로 왼쪽에 정지 상태가 있는 경우:
                        #   - 패턴: ... S L
                        #   - 이 L은 그 S에 부딪혀 1번 충돌 후 멈춘다.
                        ans += 1      # S와의 충돌 1회
                        state = "S"   # 충돌 후에도 그 위치에는 S(정지)가 남음
                    else:
                        # state가 'R'도 'S'도 아닌 경우(초기 L 구간 등):
                        #   - 왼쪽에 정지한 차도, R도 없으므로 충돌 없이 왼쪽으로 빠져나간다.
                        #   - 단지 상태를 'L'로 유지하여, 이후 로직에서 "왼쪽에 S가 없다"는 정보를 반영.
                        state = "L"

        return ans                    # 계산된 총 충돌 횟수 반환

3. 다른 풀이

이번에는 다른 풀이도 시도했다.
배열의 왼쪽 끝에서 "L"을, 오른쪽 끝에서 "R"을 제거하고, 충돌이 가능한 "R", "L"을 카운팅했다.
시간복잡도는 $O(n)$이다.

class Solution:
    def countCollisions(self, directions: str) -> int:
        i = 0
        # 왼쪽 끝에서 연속된 'L'은 충돌에 참여하지 않고 빠져나가므로 제거
        while i < len(directions) and directions[i] == "L":
            i += 1

        j = len(directions) - 1
        # 오른쪽 끝에서 연속된 'R'도 충돌 없이 빠져나가므로 제거
        while j >= 0 and directions[j] == "R":
            j -= 1

        ans = 0
        # i~j 구간은 "충돌 가능성이 있는 중앙 구간"
        for k in range(i, j+1):
            # 이 구간의 L 또는 R 은 모두 언젠가 충돌을 거쳐 멈춘다
            if directions[k] == "R" or directions[k] == "L":
               ans += 1

        return ans

4. 마무리

이번에는 첫 풀이는 내 풀이고, 두번째 풀이는 힌트를 보고 풀었다.
둘 다 그래도 내 힘으로 푼 것 같아서 좋다.