문제 개요
두 친구 아말과 비말이 저녁 식사를 함께할 레스토랑을 정하려고 합니다. 두 사람은 각각 문자열로 표현된 '좋아하는 레스토랑 목록'을 가지고 있으며, 우리는 이들 사이의 공통 관심사를 인덱스 합이 가장 작은 기준으로 찾아야 합니다. 만약 인덱스 합이 같은 후보가 여러 개라면 순서에 상관없이 모두 반환하면 됩니다.
예를 들어, 입력이 다음과 같다고 가정해 보겠습니다.
- 리스트 1: ["ABC", "PQR", "MNO", "XYZ"]
- 리스트 2: ["TUV", "GHI", "KLM", "ABC"]
두 리스트에 공통으로 등장하는 레스토랑은 "ABC"뿐이며, 인덱스 합은 0 + 3 = 3입니다. 따라서 출력은 ["ABC"]가 됩니다.
해결 알고리즘
이 문제는 C++의 map 컨테이너를 활용해 간단하게 해결할 수 있습니다. 핵심 아이디어는 인덱스 합을 키(key)로, 해당 합을 가지는 공통 레스토랑들을 값(value)으로 저장하는 것입니다. map은 키를 기준으로 오름차순 자동 정렬되기 때문에, 키가 가장 작은 첫 번째 요소가 곧 최소 인덱스 합을 가진 답이 됩니다.
구체적인 단계는 다음과 같습니다.
- 인덱스 합을 키로, 문자열 벡터를 값으로 갖는 map(mp)을 정의합니다.
- 이중 반복문을 사용해 리스트 l1과 l2의 모든 요소 쌍을 비교합니다.
- 두 요소가 같다면(공통 레스토랑), 인덱스 합(i + j)을 키로 하여 map에 해당 레스토랑 이름을 추가합니다.
- 결과를 담을 벡터 res를 정의합니다.
- map의 첫 번째 요소(최소 키)를 가리키는 반복자를 얻어 그 값을 res에 저장합니다.
- res를 반환합니다.
C++ 구현 예제
아래 코드를 통해 실제 구현을 확인해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v) {
cout << "[";
for (int i = 0; i < v.size(); i++) {
cout << v[i] << ", ";
}
cout << "]" << endl;
}
class Solution {
public:
vector<string> findRestaurant(vector<string>& l1, vector<string>& l2) {
map<int, vector<string>> mp;
for (int i = 0; i < l1.size(); i++)
for (int j = 0; j < l2.size(); j++)
if (l1[i] == l2[j])
mp[i + j].push_back(l1[i]);
vector<string> res;
auto it = mp.begin();
res = it->second;
return res;
}
};
int main() {
Solution ob;
vector<string> v = {"ABC","PQR","MNO","XYZ"}, v1 = {"TUV","GHI","KLM","ABC"};
print_vector(ob.findRestaurant(v, v1));
}
실행 결과
입력:
{"ABC","PQR","MNO","XYZ"}, {"TUV","GHI","KLM","ABC"}
출력:
[ABC]
코드 설명 및 복잡도 분석
findRestaurant 함수는 두 리스트의 모든 조합을 비교하여 공통 요소를 찾고, 인덱스 합별로 그룹화합니다. map이 키 기준으로 자동 정렬되므로 mp.begin()이 가리키는 첫 번째 요소가 곧 최소 인덱스 합을 가진 그룹입니다. 원본 코드의 least = INT_MAX 변수는 실제로 사용되지 않으므로 제거했습니다. map의 정렬 특성 덕분에 별도의 최솟값 추적 없이도 정답을 얻을 수 있습니다.
- 시간 복잡도: O(n × m) — 두 리스트의 모든 요소 쌍을 비교해야 합니다. (n, m은 각 리스트의 길이)
- 공간 복잡도: O(n × m) — 최악의 경우 모든 공통 요소 쌍이 map에 저장될 수 있습니다.
리스트의 크기가 크다면, 먼저 한쪽 리스트를 unordered_map에 저장한 뒤 다른 리스트를 순회하는 O(n + m) 방식으로 최적화할 수도 있습니다.