문제
Input:
source = "abcd"
target = "acbe"
original = ["a","b","c","c","e","d"]
changed = ["b","c","b","e","b","e"]
cost = [2,5,5,1,2,20]
Output:
28
요약:
최소 비용으로 string을 변환하라
soruce를 target으로 바꾸는데에 최소한의 비용을 구하라
original[i] -> changed[i]의 비용은 cost[i]다
조건:
● 1 <= source.length == target.length <= 10^5
● source와 target은 연속된 소문자로 이루어져 있다
● 1 <= cost.length == original.length == changed.length <= 2000
● original[i]와 changed는 연속된 소문자로 이루어져 있다
● 1 <= cost[i] <= 10^6
● original[i] != changed[i]
풀이 과정
설명:
hash table을 이용하여 original[i] -> changed[i]의 비용중 가장 적은 비용만을 따로 key & value로 lowestCostToConv 변수에 남겨놓고 source -> target으로 가는 비용을 가져오면 괜찮겠다는 생각이 들었다
hash table을 거치는 값들은 2000개가 채 되지 않으니 hash 충돌시 발생하는 오버헤드도 거의 일어나지 않을 것이고 original[i]와 changed[i]를 효율적으로 탐색하기에 hash가 가장 적당하다는 생각이 들었다
만일 original과 changed가 일정한 개수로 들어왔다면 고정길이 배열을 이용해 탐색속도를 줄였겠지만 유동적인데다 a -> b, a -> c와 같은 중복되는 케이스가 존재하기에 hash를 이용하게 되었다
시간복잡도:
cost를 한번만 순회하니 O(C)
original 또한 한번만 순회하니 O(N)
O(N + C)
코드:
class Solution {
public:
long long minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
long long ans = 0;
unordered_map<string, int> lowestCostToConv;
for (int i = 0; i < cost.size(); ++i) {
string conv = "";
conv += original[i];
conv += changed[i];
if (lowestCostToConv.count(conv))
lowestCostToConv[conv] = min(lowestCostToConv[conv], cost[i]);
else
lowestCostToConv.insert(make_pair(conv, cost[i]));
}
for (auto &it : lowestCostToConv)
cout << it.first << ", " << it.second << endl;
for (int i = 0; i < source.size(); ++i) {
string conv = "";
conv += source[i];
conv += target[i];
ans += lowestCostToConv[conv];
}
return ans;
}
};
풀이 결과
틀렸다
문제 이해를 제대로 하지 못했다
문제 1번 예제만봐도 알 수 있었는데 여러번의 변환을 통해 cost를 줄일 수 있었다
이는 graph로 해결해야하는데 graph쪽은 약한 관계로 조금은 답을 봐야햇다.
P.S.
class Solution {
public:
long long minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
int len = source.length();
long long totalCost = 0;
vector<vector<pair<int, int>>> adjacencyList(26);
vector<vector<long long>> minConversionCosts(26, vector<long long>(26));
// drawing graph
for (int i = 0; i < cost.size(); ++i) {
// make_pair가 없어도 됨
adjacencyList[original[i] - 'a'].push_back(
{changed[i] - 'a', cost[i]});
}
// calculate shortest paths for all possible character conversions
for (int i = 0; i < 26; ++i) {
minConversionCosts[i] = dijkstra(i, adjacencyList);
}
for (int i = 0; i < len; ++i) {
if (source[i] != target[i]) {
long long charConversionCost =
minConversionCosts[source[i] - 'a'][target[i] - 'a'];
// exception for cannot conversion
if (charConversionCost == -1) {
return -1;
}
totalCost += charConversionCost;
}
}
return totalCost;
}
private:
vector<long long> dijkstra(
int startChar, const vector<vector<pair<int, int>>>& adjacencyList) {
priority_queue<pair<long long, int>,
vector<pair<long long, int>>,
greater<pair<long long, int>>>
priorityQueue;
// 각 알파벳마다 최소 변환 cost 저장용 배열
vector<long long> minCosts(26, -1);
// 우선순위 큐 시작 character와 cost 0으로 초기화
priorityQueue.push({0, startChar});
while (!priorityQueue.empty()) {
auto [currentCost, currentChar] = priorityQueue.top();
priorityQueue.pop();
if (minCosts[currentChar] != -1 && minCosts[currentChar] < currentCost)
continue;
// 현재 character로부터 모든 가능한 변환 탐색
for (auto& [targetChar, conversionCost] : adjacencyList[currentChar]) {
long long newTotalCost = currentCost + conversionCost;
// 만약 cost가 더 싼 변환을 만나면 갱신
if (minCosts[targetChar] == -1 || newTotalCost < minCosts[targetChar]) {
minCosts[targetChar] = newTotalCost;
priorityQueue.push({newTotalCost, targetChar});
}
}
}
//각 character로 갈 수 있는 알파벳들의 최소 거리 비용을 배열로 반환
return minCosts;
}
};
요약:
모든 알파벳에대한 다른 알파벳들로 변환하는 최소 비용을 모든 경로로 탐색을 하여 계산해놓고 source -> target으로 변환할때 해당 계산한 값을 토대로 총 비용을 구한다
위의 코드는 동적 프로그래밍과 다익스트라를 합쳤는데, 다익스트라로 구한 최소 비용을 adjacencyList라는 table에 저장 함으로써 다음 source와 target의 비용 계산에 사용하였다
알게된점
1. make_pair를 안해도 c++ 11 이상부터는 중괄호를 이용해 pair를 만들어 줄 수 있다!