C++로 회전 문자열(L/R)에서 피벗의 최종 방향 구하기

문제 개요

어떤 문자열이 주어지며, 이 문자열은 오직 두 가지 문자로만 구성되어 있다고 가정해 봅시다. L은 왼쪽 회전(left rotation), R은 오른쪽 회전(right rotation)을 의미합니다. 우리의 목표는 이 회전 명령들을 모두 수행한 후 피벗(pivot)이 향하게 되는 최종 방향을 찾는 것입니다.

방향은 나침반의 네 방위, 즉 북(N), 동(E), 남(S), 서(W)로 표현하며, 처음에 피벗은 항상 북쪽(N)을 가리키고 있다고 가정합니다.

예를 들어 입력이 "RRLRLLR"라면 출력은 E(동)가 됩니다. 그 과정을 살펴보면 다음과 같습니다.

초기 방향: N
RR → S (오른쪽으로 두 번 회전)
LR → 다시 N
LL → 여전히 N
R → E (최종 방향)

따라서 최종 결과는 E입니다.

접근 방법

이 문제는 각 회전을 숫자로 누적하는 간단한 아이디어로 해결할 수 있습니다.

카운터 변수 count를 0으로 초기화하고, 결과를 저장할 direction 문자열을 빈 값으로 준비합니다.
문자열을 처음부터 끝까지 순회하면서, 문자가 'L'이면 count를 1 감소시키고, 그렇지 않으면('R'이면) 1 증가시킵니다.
순회가 끝난 뒤 count의 부호와 4로 나눈 나머지를 기준으로 최종 방향을 결정합니다.

양수인 경우 (순방향 회전이 더 많음)

count % 4 == 0 → N
count % 4 == 1 → E
count % 4 == 2 → S
count % 4 == 3 → W

음수인 경우 (역방향 회전이 더 많음)

count % 4 == 0 → N
count % 4 == -1 → W
count % 4 == -2 → S
count % 4 == -3 → E

C++에서 음수에 대한 나머지 연산(%)은 부호를 유지하므로(-1 % 4 == -1), 위 조건 분기를 그대로 사용할 수 있습니다. 마지막으로 계산된 direction을 반환하면 됩니다.

예제 코드

아래 구현을 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;

string get_dir(string s) {
   int count = 0;
   string direction = "";
   for (int i = 0; i < s.length(); i++) {
      if (s[i] == 'L')
         count--;
      else
         count++;
   }
   if (count > 0) {
      if (count % 4 == 0)
         direction = "N";
      else if (count % 4 == 1)
         direction = "E";
      else if (count % 4 == 2)
         direction = "S";
      else if (count % 4 == 3)
         direction = "W";
   }
   if (count < 0) {
      if (count % 4 == 0)
         direction = "N";
      else if (count % 4 == -1)
         direction = "W";
      else if (count % 4 == -2)
         direction = "S";
      else if (count % 4 == -3)
         direction = "E";
   }
   return direction;
}

int main() {
   string s = "RRLRLLR";
   cout << get_dir(s);
}

입력

"RRLRLLR"

출력

정리

이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n), 추가 메모리는 O(1)입니다. 회전 횟수를 정수로 누적한 뒤 4로 나눈 나머지만 확인하면 되기 때문에, 문자열 길이가 매우 길어도 효율적으로 최종 방향을 계산할 수 있습니다.