문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/72412?language=cpp
카카오 코딩테스트에 나온 문제. 문제 이해 자체는 어렵지 않다.
문제 핵심 및 풀이
1. 효율성 검사도 하기 때문에 시간복잡도가 중요하다.
info의 크기가 50,000까지이고, query의 크기는 100,000까지이다.
이를 O(N)으로 계산한다고 했을 때,
5* 10^5 * 10^4 = 5억 정도라서 O(N)으로 탐색하기에는 아슬아슬하다.
그래서 최적화를 해야 하는 문제이다.
실제로 O(N)으로 푸니까 시간초과가 나온다.
O(N)으로 풀었을 때의 시간 복잡도가 얼마인지 모르겠긴 하다.
2. 문자열 분리
해당 문제에서 info는 띄어쓰기를 통해 구분되어 있다.'
이는 기존에 하던 대로 Java에서는 split,
C++에서는 iostream을 통해 분리해 주면 된다.
문제는 query의 구분자가 " and "와 띄어쓰기가 동시에 쓰인다는 것
이 작업을 해주는 것이 핵심이다.
3. Info와 query를 구성하는 방식
info와 query에는 5개의 String 정보가 들어가 있다.
그러면 이 정보는 구조체는 클래스를 통해 구성해야 하나?
아니면 자료구조를 잘 써야 하나 고민이 된다.
구조체나 클래스를 쓰면 나중에 찾을 때,
5개의 정보를 비교해 야하기 때문에 최적화엔 적절하지 않다.
그럼 자료구조 중 뭐를 써야 할까?
이를 위해 자료구조의 메서드별 시간복잡도를 알고 있어야 한다.
이렇듯 list 종류를 사용하는 것보다 map을 사용하는 것이 훨씬 빠르다.
게다가 map을 이용하면 인덱스를 문자열로 둘 수 있고, O(1)만에 찾을 수 있다.
여기서 나는 key-value로 (문자열, ArrayList <Integer> or vector <int>)로 구성했다.
문자열에는 query의 조건이 들어가고, value에는 점수(score)가 들어간다.
value를 배열로 둔 이유는 같은 점수가 존재할 수 있기 때문이다.
로직
로직은 key 값인 문자열에 포인트가 있다.
info에 있는 정보를 통해, 해당 조합에서 나올 수 있는 모든 경우의 수를 key값으로 만든다.
예를 들어, 어떤 하나의 정보가 "java backend junior pizza 150"이라고 가정하자.
해당 조합으로 조건을 만족할 수 있는 query들은 뭘까?
"- - - - 150 이상",
"java backend - - 150 이상",
"- backend - pizza 150 이상"
" - - junior - 150 이상"
등등이 있을 것이다.
이렇듯 우리는 나올 수 있는 모든 조건을 문자열로 만들어 key 값으로 만든다.
그리고 value로 score을 넣는다.
이렇게 하면 자연스럽게 해당 문자열 조건에서 얻을 수 있는 점수들의 리스트가 나올 것이고,
조건만으로 쉽게 그 리스트들을 알 수 있다.
하지만 여기서 한 번의 최적화가 더 필요하다.
"- - - - 150 이상"
이 경우에는 150 이상의 모든 info가 만족한다.
그런데 문자열을 통해 모든 점수를 list로 담아뒀기 때문에
이를 탐색하려면 일일이 찾아야 한다.
그래서 이 시간을 줄이고자,
key-value 별로 점수별로 오름차순으로 정렬 후,
이진 탐색(binary search)을 사용하여 최적화하였다.
즉 이 문제의 포인트는 2가지로 요약할 수 있다.
1. HashMap 또는 map을 사용하여 정보를 구성하는 것
2. 정답을 찾을 때 이진탐색을 통해 최적화하기
실수하기 쉬운 부분
query의 경우 구분자가 and와 띄어쓰기 2개가 있기 때문에 이를 분리하는데 유의해야 한다.
또한 "and"가 아닌 " and "이기 때문에 조심해야 한다.
그리고 모든 입력이 문자열로 들어오기 때문에,
문자열 부분을 분리 후 score 부분을 정수형으로 변환해줘야 한다.
코드 구현
C++ 구현 코드
↓
#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <algorithm>
#include <iostream>
using namespace std;
map<string,vector<int>> m; // (key: query 조건, value : 점수 리스트)
// 해당 info로 얻을 수 있는 모든 조건을 구한다.
void getAllCases(vector<string> info, string key, int cnt){
// 마지막 score은 부분은 문자열 조건에 필요하지 않아 key에 넣지 않음
if(cnt >= 4){
// 점수의 인덱스 부분을 문자열에서 정수형으로 변경
int score = stoi(info[4]);
// 이미 해당 키가 있어도 점수가 뒤에 추가됨
m[key].push_back(score);
return;
}
// 조건은 해당 조건 부분을 포함하냐, 포함하지않냐("-")로 나뉨
string str1 = key+info[cnt]; // 포함하는 경우 key 뒤에 부임
string str2 = key+"-"; // 포함하지 않는 경우 "-"를 뒤에 붙임
// 다음 조건 재귀호출
getAllCases(info,str1,cnt+1);
getAllCases(info,str2,cnt+1);
}
// 띄어쓰기로 구분되어 있는 query 문자열에서 "and"를 제거하는 작업
string getProblem(vector<string> problem){
string result = "";
for(string str : problem){
if(str.compare("and") == 0) continue;
result.append(str);
}
return result; // 하나의 문자열로 반환
}
vector<int> solution(vector<string> info, vector<string> query) {
vector<int> answer;
// 모든 정보를 분리하여 getAllCases 호출
for(auto it : info){
istringstream ss(it);
string buffer;
vector<string> splited;
while(getline(ss,buffer,' ')) splited.push_back(buffer);
getAllCases(splited,"",0);
}
// key 별로 리스트들을 오름차순 정렬
for(auto it : m){
sort(m[it.first].begin(),m[it.first].end());
}
// query 조건 별로 전부 실행
for(auto problem : query){
// 띄어쓰기로만 분리한 뒤 getProblem 함수 호출
istringstream ss(problem);
string buffer;
vector<string> splited;
while(getline(ss,buffer,' ')) splited.push_back(buffer);
int cntScore = stoi(splited[splited.size()-1]);
splited.pop_back(); // 마지막 점수쪽은 필요없어서 제거
string search = getProblem(splited);
vector<int> list = m[search]; // 해당 키(조건)의 점수 리스트를 가져옴
// lower_bound() : 해당 벡터에서 cntScore보다 처음으로 같거나 커지는 인덱스를 반환
// lower_bound()는 자체적으로 이진탐색을 함
int sIdx = lower_bound(list.begin(),list.end(),cntScore) - list.begin();
int number = list.size() - sIdx; // 총 갯수
answer.push_back(number);
}
return answer;
}
C++에서는 문자열 분리의 구분자를 String으로 하기 힘들기 때문에,
이를 따로따로 구분해 줬다.
그리고 이진탐색은 lower_bound를 통해 구현하였다.
↑
Java 구현 코드
↓
import java.util.*;
import java.util.stream.*;
class Solution {
// (key: query 조건, value : 점수 리스트)
static Map<String,List<Integer>> map = new HashMap<>();
public int[] solution(String[] info, String[] query) {
int[] answer = new int[query.length];
// 모든 정보를 분리하여 getAllCases 호출
for(String word : info){
String[] splited = word.split(" ");
getAllCases(splited,"",0);
}
// hashMap 안에 있는 모든 List<Integer>을 오름차순 정렬
for(List<Integer> scores : map.values()) Collections.sort(scores);
int idx = 0;
for(String q : query){
// 이런 식으로 String 2개를 구분자로 만들 수 있음
String[] splited = q.split(" and | ");
// 점수 조건을 제외하고 다 합침
String key = splited[0] + splited[1] + splited[2] + splited[3];
// 정수형을 변환
int score = Integer.parseInt(splited[4]);
int num = 0;
// 맵 안에 해당 조건의 키가 존재하는 경우
if(map.containsKey(key)){
// List를 가져오고 조건 점수를 매개변수로 하는 이진 탐색
List<Integer> list = map.get(key);
num = binarySearch(score,list);
}
answer[idx++] = num;
}
return answer;
}
// 이진 탐색 직접 구현(target : 목표 점수, list : 해당 조건에 저장된 점수 리스트)
public int binarySearch(int target, List<Integer> list){
int start = 0;
int end = list.size()-1;
int mid = 0;
while(start <= end){
mid = (start+end)/2;
if(list.get(mid) >= target) end = mid-1;
else start = mid+1;
}
return list.size() - start; // 바로 개수를 구해줌
}
// 해당 info로 얻을 수 있는 모든 조건을 구한다.
public static void getAllCases(String[] info, String cnt, int idx){
// 마지막 score은 부분은 문자열 조건에 필요하지 않아 cnt에 넣지 않음
if(idx == 4){
조건별 key-value map을 구성한다.
makeMap(cnt,Integer.parseInt(info[4]));
return;
}
// 조건은 해당 조건 부분을 포함하냐, 포함하지않냐("-")로 나뉨
getAllCases(info,cnt+info[idx],idx+1);// 포함하는 경우 cnt 뒤에 문자열 붙임
getAllCases(info,cnt+"-",idx+1); // 포함하지 않는 경우 cnt 뒤에 "-" 붙임
}
// 해당 조건을 문자열 키로하는 map을 생성
public static void makeMap(String word, int score){
// 해당 키가 존재하지 않는 경우
if(!map.containsKey(word)){
// 해당 키를 만듦
List<Integer> tmp = new ArrayList<>();
map.put(word,tmp);
}
map.get(word).add(score);
}
}
C++과 다르게 Java에서는 String을 구분자로 쓸 수 있다.
또한 위와 같이 여러 개를 구분자로 만들 수도 있다.
또한 java는 c++과 다르게 키 값을 바로 생성할 수 없으므로
hashMap.put(key, value) 연산을 통해 키를 미리 만들어야 한다.
↑
시행착오
처음에는 해당 문제를 ArrayList로 풀었다.
그 이후에 아무리 해도 안 풀려서 인터넷을 참고했다.
근데 ArrayList로는 어떻게 해도 시간초과를 피할 수가 없어서 방식을 map으로 수정했다.
이 문제에 하루는 쓴 것 같다. 구현은 괜찮았는데, 설계 자체가 힘들었다.
howudong님에게 보내주세요
토스아이디로 안전하게 익명 송금하세요.
toss.me