配列 \(se,sa\) を用意します。それぞれ、 sensei と呼ぶべき人・ san と呼ぶべき人を管理します。
入力される \(S_i,R_i\) の組ごとに、以下の操作を行えばよいです。

• \(R_i\) が teacher または doctor なら、 \(se\) の末尾に \(S_i\) を追加する。
• そうでないなら \(sa\) の末尾に \(S_i\) を追加する。

その後、 \(se\) の要素を末尾に sensei を付けながら順に出力、 \(sa\) の要素を末尾に san を付けながら順に出力すればよいです。

一連の流れは for 文と if 文の組み合わせで実現でき、時間計算量は \(O(N)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int N;
  cin >> N;
  vector<string> se,sa;
  for(int i=0;i<N;i++){
    string S,R;
    cin >> S >> R;
    if(R=="teacher" || R=="doctor"){
      se.push_back(S);
    }
    else{
      sa.push_back(S);
    }
  }
  for(auto &nx : se){
    cout << nx << " sensei\n";
  }
  for(auto &nx : sa){
    cout << nx << " san\n";
  }
  return 0;
}