깊이/너비 우선 탐색(DFS/BFS)

여행경로

1차 시도

#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

vector<string> BFS(unordered_map<string, unordered_multiset<string>> ticket_field, string prev_airport, string now_airport) {
    if (prev_airport.size()) {
        ticket_field[prev_airport].erase(ticket_field[prev_airport].find(now_airport));
    }

    vector<string> optimal_route;

    for (string next_airport:ticket_field[now_airport]) {
        vector<string> route = BFS(ticket_field, now_airport, next_airport);

        if (optimal_route.size() < route.size()) optimal_route = route;
        else if (optimal_route.size() == route.size()) {

            for (int i=0; i<optimal_route.size(); i++) {
                if (optimal_route[i] != route[i]) {
                    if (optimal_route[i] > route[i]) optimal_route = route;

                    break;
                }
            }
        }
    }

    optimal_route.insert(optimal_route.begin(), now_airport);

    return optimal_route;
}

vector<string> solution(vector<vector<string>> tickets) {
    unordered_map<string, unordered_multiset<string>> ticket_field;

    for (int i=0; i<tickets.size(); i++) {
        ticket_field[tickets[i][0]].insert(tickets[i][1]);
    }

    return BFS(ticket_field, "", "ICN");
}

정확성  테스트
  테스트 1 〉	통과 (297.06ms, 3.95MB)
  테스트 2 〉	통과 (0.02ms, 3.93MB)
  테스트 3 〉	통과 (0.02ms, 3.96MB)
  테스트 4 〉	통과 (0.02ms, 3.97MB)

채점 결과
  정확성: 100.0
  합계: 100.0 / 100.0

이분탐색

입국심사

1차 시도

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

long long solution(int n, vector<int> times) {
    sort(times.begin(), times.end());
    
    long long left = 1, right = (long long)n * (long long)times.back(), mid = (left + right)>>1;
    
    while (left < right) {
        long long check_people = 0;
        bool isMultiple = false;
        
        for (int t:times) {
            check_people += mid / t;
            
            if (mid % t == 0) isMultiple = true;
            
            if (check_people > n) break;
        }
        
        if (check_people > n) {
            right = mid;
        } else if (check_people < n) {
            left = mid + 1;
        } else if (!isMultiple) {
            left--;
            right--;
        } else break;
        
        mid = (left + right)>>1;
    }
    
    return mid;
}

정확성  테스트
  테스트 1 〉	통과 (0.01ms, 3.97MB)
  테스트 2 〉	통과 (0.02ms, 3.89MB)
  테스트 3 〉	통과 (343.67ms, 3.94MB)
  테스트 4 〉	통과 (338.15ms, 6.8MB)
  테스트 5 〉	통과 (200.64ms, 6.88MB)
  테스트 6 〉	통과 (30.10ms, 6.54MB)
  테스트 7 〉	통과 (518.44ms, 6.74MB)
  테스트 8 〉	통과 (2854.43ms, 6.86MB)
  테스트 9 〉	통과 (0.01ms, 3.95MB)

채점 결과
  정확성: 100.0
  합계: 100.0 / 100.0