C++で回転指示の文字列から最終的な方向を求める方法

「L」と「R」のみで構成される文字列を考えます。「L」は左回転(left rotation)、「R」は右回転(right rotation)を表します。このとき、コンパスの針(ピボット)が最終的に向く方向を求めるのが本記事の目的です。取り得る方向は北(N)、東(E)、南(S)、西(W)の4つで、初期状態ではピボットは北(N)を向いているものと仮定します。

例えば、入力が「RRLRLLR」の場合、出力は「E」になります。処理の流れを追ってみましょう。初期方向はNです。最初の「RR」で南(S)を向き、続く「LR」で再び北(N)に戻ります。その後の「LL」でも向きは北(N)のまま変わりません。最後の「R」で東(E)を向くため、最終的な答えはEとなります。

アルゴリズムの考え方

この問題は、左右の回転数の差をカウントし、それを4で割った剰余から方向を判定するというシンプルな方法で解けます。4回の回転で元の向きに戻るため、剰余演算が有効です。具体的な手順は以下の通りです。

• カウンター count を 0 に初期化する。
• direction を空文字列として初期化する。
• 文字列 s の各文字に対して以下を繰り返す。
  • s[i] が 'L' なら count を 1 減らす。
  • 'R' なら count を 1 増やす。
• count > 0(正味の右回転)の場合:
  • count % 4 == 0 → "N"
  • count % 4 == 1 → "E"
  • count % 4 == 2 → "S"
  • count % 4 == 3 → "W"
• count < 0(正味の左回転)の場合:C++では負の数の剰余が負になる点に注意が必要です。
  • count % 4 == 0 → "N"
  • count % 4 == -1 → "W"
  • count % 4 == -2 → "S"
  • count % 4 == -3 → "E"
• direction を返す。

C++での実装例

理解を深めるために、実際の実装を見てみましょう。

#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[0] == '\n')
            return NULL;
        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"

出力

E

このプログラムは文字列を一度走査するだけで済むため、時間計算量はO(n)、追加の記憶領域も定数個の変数のみでO(1)と非常に効率的です。負の剰余の扱いさえ注意すれば、剰余演算による方向判定はコンパス問題全般に応用できる汎用的なテクニックです。