手袋の種類と左右がランダムに入力されるのでペアを見つけるアルゴリズム

Question

前提・実現したいこと
１. 手袋の数が入力（範囲：１～１００）
２. 手袋の種類は英字大文字、左右はL,Rのどちらかが入力される。
例：S　R　のように空白を含む1行で入力されます。
３. 同じ種類の手袋で左右が揃っているペアが何組あるか出力する。

考えたアルゴリズムです。
１．手袋の数を取得
２．その数分だけ種類と左右を配列に格納を繰り返す
３．ソートで種類をまとめる。
４．種類を判定して同じなら左右判定をして、左、右それぞれの数を数える変数を足していく。
左右が1以上になったらペアを数える。
種類が変わったら左、右それぞれの数を数える変数を０に初期化して、配列の長さ分同じことを繰り返す。

このアルゴリズムだとランタイムエラーとなりました。
2重ループでやったのですが、for文なりwhil文なり抜ける（break）条件が思いつきません。

ソースコードではなく、アルゴリズムをご教授いただければと思います。
よろしくお願いいたします。

コメントへの理解が遅く、追記遅くなりました。
ペアの数え方は、種類が同じで左右がそろっている手袋の合計数です。
6
S R
S L
A R
A L
B L
B L
であれば、Sのペアが1つとAのペアが1つの合計2ペアとなります。
正しい答えが得られるアルゴリズムが知りたいです。
よろしくお願いいたします。

Comments

[y_waiwai]

現状のコードを提示しましょう

[dodox86]

ランタイムエラーになるのはアルゴリズムの問題と言うより、そのアルゴリズムの実装の仕方（コードの書き方）に問題があるからです。質問の主旨は、質問者さんの考えたアルゴリズムをちゃんと実装するためにより細かいループの方法などを示したアルゴリズム（コード）を知りたいのか、それとも正しい答え（出力）を得る別のアルゴリズムが知りたいのか、どちらでしょうか。

[dodox86]

入力が
6
L R L R L L
のようであった場合、出力である答の手袋のペア数は、2 と言うことですよね。であれば、必ずしも配列などに入れてL/Rの突き合せをしなくても単純に計算でペア数は求められます。

[kinako_make]

ご指摘と丁寧に説明をありがとうございます。
正しい答えが得られるアルゴリズムが知りたくて質問しました。質問の意図を明記せず申し訳ありませんでした。

[dodox86]

私のコメントに対する修正が無かったので良く分かりませんが、入力について、
> 入力が
> 6
> L R L R L L

ではなく、「種類」もあるので
6
S R
S L
A R
A L
B L
B L
であれば、種類Sのペアが1つ、種類Aのペアが1つで、合計2つのペア、ということでしょうか。

Answer 1

int[][] count = new int[26][2]; で 2次元配列を用意します。
要素はゼロに初期化されています。

n を入力後、(種類、左右) のペアの値を n 回読み込みますが、
1組読み込むごとに、種類の 'A'～'Z' を 0～25 の i に、左右の 'L'、'R' を
0, 1 の j に変換し、count[i][j]++; でカウントアップします。

int sum = 0;
for (int i = 0; i < 26; i++) sum += Math.min(count[i][0], count[i][1]);

この sum が求める値です。

追記
Math.min を使わなくてもできます。

if (count[i][0] < count[i][1]) sum += count[i][0]; else sum += count[i][1];

追記2
すでに hu_さんのコードが出ているのに気づいていませんでした。
私の想定していたコートは次のようなものです。

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[][] count = new int[26][2];
        for (int n = sc.nextInt(); --n >= 0; )
			count[sc.next().charAt(0) - 'A']["LR".indexOf(sc.next())]++;
        int sum = 0;
        for (int i = 0; i < 26; i++)
			sum += Math.min(count[i][0], count[i][1]);
        System.out.println(sum);
    }
}

Comments

[kinako_make]

ありがとうございます。
Math.minというのがあるのですね！調べてみます。
とても参考になりました。

Answer 2

A.割と正攻法だと思うのが、

１．右と左で２つのリストに分ける
２．２つのリストをマッチング処理する

B.処理的に簡単だと思うのは、
１．右と左で、別のMapオブジェクトでカウントする
２．右を順番に、左用mapに存在するかチェックしながら、数を確認する

自分がやるならBのパターンかな

Comments

[kinako_make]

ありがとうございます。
mapを使ったことがないので、Aを参考にさせていただきます。

[ngsvx]

使ったことがないなら、コレを機会に使うのもあり。mapは便利だから使わないと非常に損をします。

Answer 3

どこかの問題でしたらリンク貼ってください。
ネットじゃなければ書籍名か教科書の問題など明記してください。

以下思いつきですがご参考までに。

①初期化
左右の配列2つを用意
サイズは英大文字26文字分
L[26] R[26]

②入力
手袋の数取得n
n回のループ
i=0 i<100 i+1
入力された英文字の左右を見て加算
A L　なら　L[0] +1
B R　なら　R[1] +1 など

③集計
n回のループ
i=0 i<100 i+1
L[i] R[i] を比較して小さい方をsumに加算

ペアが2組ある例
L[0]=3 R[0]=2 ならsum=sum+2

④出力
sumを出力

Comments

[kinako_make]

すみません。
通っている初心者用のプログラミングスクールの課題です。

とても参考になります！
ありがとうございます。

[mjk]

LR左右の判定は分かると思いますが、
A～Zを各配列[0]～[25] または[1]～[26]と対応させるところがやったことなければ分かりにくいかもしれませんが、それっぽいキーワードで検索すればコード出てくると思います。
javaは最近触っていないのでコードは割愛します。

[kinako_make]

丁寧にありがとうございます。
このやり方でやってみようと思います！

Answer 4

間違えて同じ内容を送っていたので1つ削除しました。

Answer 5

皆さんのアドバイスを参考にさせていただき、なんとかできました。
ありがとうございました。

import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int num = sc.nextInt();     //靴下の数を取得

        /*靴下の左右の数を数える配列、サイズは英大文字26文字分で用意
            0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
            A B C D E F G H I J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z*/
        String alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        int[] socksL = new int[alpha.length()];     
        int[] socksR = new int[alpha.length()];
        int idx = 0;    //要素数を保存

        for (int i = 0; i < num; i++){
            //靴下の種類の英文字と左右（"L","R"のいずれか）を取得
            String type = sc.next(); 
            String pair = sc.next(); 

            //文字列alphaと一致したインデックスを保存
            idx = alpha.indexOf(type);

            if("L".equals(pair)){
                //左の場合、配列socksLの文字列alphaと一致する要素数を加算
                socksL[idx]++;
            }else{
                //右の場合、配列socksRの文字列alphaと一致する要素数を加算
                socksR[idx]++;
            }
        } 
        //そろっているペア数を足していく
        int sum = 0;
        for (int i = 0; i < socksL.length; i++){
            //左右の配列の小さい法をsumに加算していく

            sum += Math.min(socksL[i], socksR[i]);
        }
        System.out.println(sum);
    }
}