🌟

AtCoder Beginner Contest 342 C - Many Replacement 覚書き PHP

2024/05/02に公開

AtCoder

tech

PHPで解答を作成しています。

問題のリンク

解のポイント

アルファベットをkeyに設定するにはどうすればいいか？を考えること

操作の中心はアルファベットをさがす→位置を変更する
操作ごとにアルファベットを配列から検索し変更をすると計算量がえらいことになる
配列のkeyにアルファベットを設定し検索すれば計算量が少なく早い

そこで以下の順番で処理を行います
↓

アルファベットのすべての小文字をkeyにした空の配列を作る
アルファベットの配列に位置を格納していく
入替を行う
文字列にもどす

入れ替える文字が同じ場合の条件を忘れない

// 変更元の文字と変更する文字が同じ場合は何もしない
  if($c == $d) {
    continue;
  }

使用する関数/演算子

array_merge

array_merge(array ...$arrays): array

入力配列が同じキー文字列を有していた場合、そのキーに関する後に指定された値が、前の値を上書きします。

ksort
キーで昇順にソート

implode

implode(string $separator, array $array): string
// 今回の場合は""内が空白なしのため文字はつづけて返される
$result = implode('', $positions);

配列要素を文字列により連結する

全体コード

<?php

$N = trim(fgets(STDIN)); // 文字列の長さを取得する
$S = trim(fgets(STDIN)); // 文字列
$Q = trim(fgets(STDIN)); // 操作の回数

// a-zまでのアルファベットをキーにした配列を作成する
$keys = range('a', 'z');
$arrays = [];
foreach ($keys as $key) {
    $arrays[$key] = [];
}

// 文字列を1文字ずつ分割して、アルファベットをキーにした配列に格納する
for ($i = 0; $i < $N; $i++) {
  $arrays[$S[$i]][] = $i;
}

// 操作の回数分だけ繰り返す
for ($j = 0; $j < $Q; $j++) {
  // $cは変更元の文字、$dは変更する文字
  list($c, $d) = explode(' ', trim(fgets(STDIN)));

  // 変更元の文字と変更する文字が同じ場合は何もしない
  if($c == $d) {
    continue;
  }

  // 変更する文字の配列に位置を追加する
  $arrays[$d] = array_merge($arrays[$d], $arrays[$c]);

  // 変更元の文字の配列を空にする
  $arrays[$c] = [];
}

// print_r($arrays);

// 全ての位置と対応する文字を含む新しい配列を作成する
$positions = [];
foreach ($arrays as $char => $indexes) {
  foreach ($indexes as $index) {
    $positions[$index] = $char;
  }
}

// その配列をキー（位置）に基づいてソートする
ksort($positions);

// ソートされた配列から文字だけを取り出し、それを連結して最終的な文字列を作成する
$result = implode('', $positions);

echo $result;

解のポイント

使用する関数/演算子

全体コード

Discussion