문제 소개
여러 건의 거래(transaction) 정보가 주어졌다고 가정해 보겠습니다. 어떤 거래가 아래 조건 중 하나라도 만족한다면, 그 거래는 '잘못된(invalid) 거래'일 가능성이 있습니다.
- 거래 금액이 1,000달러($1,000)를 초과하는 경우
- 같은 이름의 다른 거래가 다른 도시에서 발생했으며, 두 거래의 시간 차가 60분 이내(60분 포함)인 경우
각 거래 문자열 transactions[i]는 쉼표(,)로 구분된 값들로 구성되며, 순서대로 거래자 이름, 시간(분 단위), 금액, 도시를 나타냅니다. 주어진 거래 목록에서 잠재적으로 잘못된 거래를 모두 찾아 리스트로 반환해야 합니다.
예를 들어 입력이 ["alice,20,800,mtv", "bob,50,1200,mtv"]라면, bob의 거래 금액이 1,200달러로 1,000달러를 초과하므로 정답은 ["bob,50,1200,mtv"]가 됩니다.
해결 접근 방법
이 문제는 다음과 같은 단계로 해결할 수 있습니다.
- 중복 제거와 정렬을 위해 집합(set) s를, 이름별 거래 목록 저장을 위해 맵(map) m을 정의합니다.
- i를 0부터 t의 크기 - 1까지 반복합니다.
- x := t[i]
- temp := 문자열 x를 파싱해 만든 노드(Node)
- j를 0부터 m[temp.name]의 크기 - 1까지 반복합니다.
- y := m[temp.name][j]
- y의 도시가 temp의 도시와 다르고 |y.time − temp.time| ≤ 60이라면, y를 문자열 형태로 s에 삽입하고 x도 s에 삽입합니다.
- temp의 금액이 1,000보다 크면 x를 s에 삽입합니다.
- temp를 m[temp.name]에 추가합니다.
- 집합 s에 담긴 항목들을 반환합니다.
예제 코드(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 Node{
public:
string name;
string city;
int time;
int amount;
};
class Solution {
public:
Node getNode(string s){
string temp = "";
Node ret;
int cnt = 0;
for(int i = 0; i < s.size(); i++){
if(s[i] == ','){
if(cnt == 0){
ret.name = temp;
}
else if(cnt == 1){
ret.time = stoi(temp);
}
else if(cnt == 2){
ret.amount = stoi(temp);
} else {
ret.city = temp;
}
cnt++;
temp = "";
continue;
}
temp += s[i];
}
ret.city = temp;
return ret;
}
vector<string> invalidTransactions(vector<string>& t) {
set <string >s;
map <string ,vector < Node >> m;
for(int i = 0; i < t.size(); i++){
string x = t[i];
Node temp = getNode(x);
for(int j = 0; j < m[temp.name].size(); j++){
Node y = m[temp.name][j];
if(y.city != temp.city && abs(y.time - temp.time) <= 60){
s.insert(y.name + "," + to_string(y.time) + "," + to_string(y.amount) + "," + y.city);
s.insert(x);
}
}
if(temp.amount > 1000){
s.insert(x);
}
m[temp.name].push_back(temp);
}
vector <string> ret(s.begin(), s.end());
return ret;
}
};
main(){
vector<string> v1 = {"alice,20,800,mtv","bob,50,1200,mtv"};
Solution ob;
print_vector(ob.invalidTransactions(v1));
}입력
["alice,20,800,mtv","bob,50,1200,mtv"]
출력
[bob,50,1200,mtv]
코드 설명
getNode() 함수는 입력 문자열을 쉼표를 기준으로 하나씩 읽어가며 이름, 시간, 금액, 도시 네 가지 값을 추출하고, 이를 담은 Node 객체를 반환합니다.
invalidTransactions() 함수는 같은 이름의 거래들을 map에 모아 관리합니다. 새로운 거래가 들어올 때마다 이전에 기록된 같은 이름의 거래들과 도시·시간 조건을 비교해 위반 시 두 거래를 모두 집합 s에 넣고, 금액 초과 여부도 함께 검사합니다. 결과를 set에 저장하기 때문에 중복이 자동으로 제거되며, 정렬된 상태로 반환됩니다.
출력 끝에 쉼표가 붙어 있는 것은 print_vector() 함수가 각 요소 뒤에 ", "를 붙여 출력하기 때문입니다.
시간 복잡도는 최악의 경우(모든 거래가 같은 이름인 경우) O(n²)이며, 공간 복잡도는 O(n)입니다.