문제 링크

내 코드

주말은 진짜 살려줘.. 게다가 Hard.. ㅠㅠ

해설보고 공부나 하자..

Hierholzer’s Algorithm는 처음 들어 본다.

Solution

Approach 1: Eulerian Path (Recursive)

• 1837ms, 456.56MB
• Complexity
  • Let n be the number of pairs in the input pairs, $V$ be the number of unique vertices in the graph formed by these pairs, and $E$ be the number of edges in the graph, which equals n since each pair represents an edge.
  • Time Complexity: $O(V + E)$
  • Space Complexity: $O(V + E)$

class Solution {
public:
    vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
        unordered_map<int, deque<int>> adjacencyMatrix;
        unordered_map<int, int> inDegree, outDegree;

        // Build the adjacency list and track in-degrees and out-degrees
        for (const auto& pair : pairs) {
            int start = pair[0], end = pair[1];
            adjacencyMatrix[start].push_back(end);
            outDegree[start]++;
            inDegree[end]++;
        }

        vector<int> result;

        // Helper lambda function for DFS traversal,
        // you can make a seperate private function also
        function<void(int)> visit = [&](int node) {
            while (!adjacencyMatrix[node].empty()) {
                int nextNode = adjacencyMatrix[node].front();
                adjacencyMatrix[node].pop_front();
                visit(nextNode);
            }
            result.push_back(node);
        };

        // Find the start node (outDegree == 1 + inDegree )
        int startNode = -1;
        for (const auto& entry : outDegree) {
            int node = entry.first;
            if (outDegree[node] == inDegree[node] + 1) {
                startNode = node;
                break;
            }
        }

        // If no such node exists, start from the first pair's first element
        if (startNode == -1) {
            startNode = pairs[0][0];
        }

        // Start DFS traversal
        visit(startNode);

        // Reverse the result since DFS gives us the path in reverse
        reverse(result.begin(), result.end());

        // Construct the result pairs
        vector<vector<int>> pairedResult;
        for (int i = 1; i < result.size(); ++i) {
            pairedResult.push_back({result[i - 1], result[i]});
        }

        return pairedResult;
    }
};

Approach 2: Hierholzer’s Algorithm (Iterative)

• 494ms, 433.64MB
• Complexity
  • Let n be the number of pairs in the input pairs, $V$ be the number of unique vertices in the graph formed by these pairs, and $E$ be the number of edges in the graph, which equals n since each pair represents an edge.
  • Time Complexity: $O(V + E)$
  • Space Complexity: $O(V + E)$

class Solution {
public:
    vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
        unordered_map<int, deque<int>> adjacencyMatrix;
        unordered_map<int, int> inDegree, outDegree;

        // Build the adjacency list and track in-degrees and out-degrees
        for (const auto& pair : pairs) {
            int start = pair[0], end = pair[1];
            adjacencyMatrix[start].push_back(end);
            outDegree[start]++;
            inDegree[end]++;
        }

        vector<int> result;

        // Find the start node (outDegree == inDegree + 1)
        int startNode = -1;
        for (const auto& entry : outDegree) {
            int node = entry.first;
            if (outDegree[node] == inDegree[node] + 1) {
                startNode = node;
                break;
            }
        }

        // If no such node exists, start from the first pair's first element
        if (startNode == -1) {
            startNode = pairs[0][0];
        }

        stack<int> nodeStack;
        nodeStack.push(startNode);

        // Iterative DFS using stack
        while (!nodeStack.empty()) {
            int node = nodeStack.top();
            if (!adjacencyMatrix[node].empty()) {
                // Visit the next node
                int nextNode = adjacencyMatrix[node].front();
                adjacencyMatrix[node].pop_front();
                nodeStack.push(nextNode);
            } else {
                // No more neighbors to visit, add node to result
                result.push_back(node);
                nodeStack.pop();
            }
        }

        // Reverse the result since we collected nodes in reverse order
        reverse(result.begin(), result.end());

        // Construct the result pairs
        vector<vector<int>> pairedResult;
        for (int i = 1; i < result.size(); ++i) {
            pairedResult.push_back({result[i - 1], result[i]});
        }

        return pairedResult;
    }
};