Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 해결하는 외계인 사전(Alien Dictionary) 문제 – 위상 정렬 완벽 가이드

문제 설명

새로운 외계인 언어가 있다고 가정해 보겠습니다. 이 언어는 라틴 알파벳을 사용하지만, 글자들 사이의 순서는 아직 알려져 있지 않습니다. 우리에게는 이 언어의 규칙에 따라 사전순으로 정렬된 비어 있지 않은 단어 목록이 주어지며, 이 목록을 분석해 해당 언어에서 글자들이 배열된 순서를 찾아내야 합니다.

예를 들어 입력이 ["wrt", "wrf", "er", "ett", "rftt"]라면, 올바른 출력은 "wertf"입니다.

해결 접근 방식: 위상 정렬(Topological Sort)

이 문제의 핵심은 인접한 두 단어를 나란히 놓고 앞에서부터 한 글자씩 비교하여 글자 간의 선행 관계를 도출하는 것입니다. 처음으로 글자가 달라지는 지점을 찾으면, 앞 단어의 글자가 뒷 단어의 글자보다 먼저 온다는 정보를 얻을 수 있습니다. 이렇게 수집한 관계들을 방향 그래프로 구성한 뒤 위상 정렬을 수행하면 전체 글자 순서를 알아낼 수 있습니다. 구체적인 절차는 다음과 같습니다.

  • 진입 차수 맵(degree) 생성: 각 글자의 진입 차수를 저장할 맵을 정의하고, 단어 목록에 등장하는 모든 글자의 차수를 0으로 초기화합니다.

  • 그래프(graph) 생성: 글자 간 선후 관계를 저장할 인접 리스트 형태의 맵을 정의합니다.

  • 관계 추출: 인접한 두 단어를 비교하되, 두 단어 길이 중 작은 값(l)까지만 살펴봅니다. 처음으로 글자가 달라지는 위치(x ≠ y)에서 x → y 간선을 그래프에 추가하고 y의 진입 차수를 1 증가시킨 후 비교를 종료합니다.

  • 위상 정렬 준비: 결과 문자열 ret을 빈 문자열로 초기화하고, 진입 차수가 0인 모든 글자를 큐(q)에 삽입합니다.

  • BFS 순회: 큐가 빌 때까지 앞쪽 글자를 하나씩 꺼내 ret에 이어 붙이고, 해당 글자가 가리키는 모든 글자의 진입 차수를 1씩 감소시킵니다. 차수가 0이 된 글자는 다시 큐에 넣습니다.

  • 유효성 검사: 최종적으로 ret의 길이가 degree에 등록된 글자 수와 같다면 ret을 반환하고, 그렇지 않다면(그래프에 순환 사이클이 존재해 순서를 확정할 수 없는 경우) 빈 문자열을 반환합니다.

C++ 구현 예제

아래 코드를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   string alienOrder(vector<string>& words) {
      map<char, int> degree;
      map<char, vector<char> > graph;
      int n = words.size();
      for (int i = 0; i < words.size(); i++) {
         for (int j = 0; j < words[i].size(); j++) {
            degree[words[i][j]] = 0;
         }
      }
      for (int i = 0; i < n - 1; i++) {
         int l = min((int)words[i].size(), (int)words[i + 1].size());
         for (int j = 0; j < l; j++) {
            char x = words[i][j];
            char y = words[i + 1][j];
            if (x != y) {
               graph[x].push_back(y);
               degree[y]++;
               break;
            }
         }
      }
      string ret = "";
      queue<char> q;
      map<char, int>::iterator it = degree.begin();
      while (it != degree.end()) {
         if (it->second == 0) {
            q.push(it->first);
         }
         it++;
      }
      while (!q.empty()) {
         char x = q.front();
         q.pop();
         ret += x;
         vector<char>::iterator sit = graph[x].begin();
         while (sit != graph[x].end()) {
            degree[*sit]--;
            if (degree[*sit] == 0) {
               q.push(*sit);
            }
            sit++;
         }
      }
      return ret.size() == degree.size() ? ret : "";
   }
};
main(){
   Solution ob;
   vector<string> v = {"wrt","wrf","er","ett","rftt"};
   cout <<(ob.alienOrder(v));
}

입력 및 출력

입력:

{"wrt","wrf","er","ett","rftt"}

출력:

wertf

복잡도 분석

그래프를 구축하는 과정은 주어진 모든 문자를 한 번씩 훑으므로 O(C)의 시간이 걸립니다. 여기서 C는 전체 문자의 개수입니다. 위상 정렬 단계 역시 글자 수(최대 26개)와 간선 수에 비례하므로 전체 시간 복잡도는 O(C)이며, 알파벳 종류가 고정되어 있어 공간 복잡도 또한 상수 수준으로 매우 효율적입니다.