백준 3156

• 참고코드 출처: https://hsin.hr/2006/

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>

using namespace std;

int main()
{
   int N;
   cin >> N;

   map<string, int> earliest;
   for ( int i=0; i<N; ++i ) {
      int a, b;
      string od;
      cin >> a;
      cin >> od;
      cin >> b;

      for ( int j=0; j<a; ++j ) {
         string song;
         cin >> song;
         map<string, int>::iterator it = earliest.find( song );
         if ( it == earliest.end() )
            earliest[song] = b;
         else
            it->second = min( b, it->second );
      }
   }

   vector<pair<int, string> > song_ranking;
   for ( map<string, int>::iterator it=earliest.begin(); it!=earliest.end(); ++it )
      song_ranking.push_back( make_pair( it->second, it->first ) );
   sort( song_ranking.begin(), song_ranking.end() );

   for ( int i=0; i<(int)song_ranking.size(); ++i ) {

      if ( i == 0 || song_ranking[i].first != song_ranking[i-1].first ) {

         if ( song_ranking[i].first-1 == i ) {
            cout << song_ranking[i].first << " " << song_ranking[i].second << endl;
         }
      }
   }

   return 0;
}

아래는 vector랑 sort를 안 쓰고 map만 사용해 보려고 했는데 테스트케이스는 통과해도 자꾸 틀렸다고 나오는 코드

#include <iostream>
#include <map>
#include <set>

using namespace std;

int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);

   int N;
   cin >> N; // 입력될 행

   map<string, int> rank_map; // 순위 저장
   for ( int i=0; i<N; ++i ) {
      int a, rank;
      string od;
      cin >> a; // 입력될 노래의 개수
      cin >> od; // 문자열 od
      cin >> rank; // 몇 위 이내의 곡인지

      for ( int j=0; j<a; ++j ) {
         string song;
         cin >> song; // 노래제목
         map<string, int>::iterator it = rank_map.find( song );

         // rank_map에 노래가 없으면 추가, 이미 있는 경우 현재 순위와 입력된 순위를 비교해서 더 낮은 순위로 업데이트
         if ( it == rank_map.end() )
            rank_map[song] = rank;
         else
            it->second = min( rank, it->second );
      }
   }

   map<int, string> final_map;

   set<int> before_ranks;
   for (auto& item : rank_map)
   {
      // cout << "before_rank: " << before_rank << endl;
      // cout << item.second << " " << item.first << endl;

      final_map.emplace(item.second, item.first);

      if (before_ranks.find(item.second) != before_ranks.end())
      {
         final_map.erase(item.second);
      }

      before_ranks.emplace(item.second);
   }

   for (auto& item : final_map)
   {
      cout << item.first << " " << item.second << endl;
   }

   return 0;
}

이건 그보다 전에 주어진 노래 갯수가 1일 때는 확정순위로 저장하고, 아니면 다른 로직으로 계산하는 코드. 테스트케이스만 통과하고 제출하면 틀림.

#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;

    map<int, set<string>> rankToSongs;
    map<string, set<int>> songToPossibleRanks;
    map<int, string> confirmedRanks;

    for (int i = 0; i < N; ++i) {
        int A, B;
        cin >> A;
        string od;
        cin >> od;
        cin >> B;
        set<string> songs;
        for (int j = 0; j < A; ++j) {
            string song;
            cin >> song;
            songs.insert(song);
        }

        if (A == 1)
        {
            confirmedRanks[B] = *songs.begin();
        }
        else
        {
            for (int j = 1; j <= B; ++j)
            {
                rankToSongs[j].insert(songs.begin(), songs.end());
            }

            for (auto& song : songs)
            {
                songToPossibleRanks[song].insert(B);
            }
        }
    }

    // 제거 로직
    for (auto& pair : songToPossibleRanks) {
        const string& song = pair.first;
        const set<int>& ranks = pair.second;

        if (ranks.size() > 1) {
            for (auto& rank : ranks) {
                rankToSongs[rank].erase(song);
            }
        }
    }

    // 확정된 순위 추가
    for (auto& pair : rankToSongs) {
        const int& rank = pair.first;
        const set<string>& songs = pair.second;

        if (songs.size() == 1) {
            confirmedRanks[rank] = *songs.begin();
        }
    }

    // 결과 출력
    for (auto& pair : confirmedRanks) {
        cout << pair.first << " " << pair.second << endl;
    }

    return 0;
}