📃 문제
📝 풀이
이 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제다.
고려사항
info배열의 크기는 1 이상 50,000 이하입니다.query배열의 크기는 1 이상 100,000 이하입니다.
Python 초기 코드
def dfs(dic, depth, condition, idx):
global answer
if depth == 4:
score = condition[depth]
for s in dic:
if score <= s:
answer += 1
return
if condition[depth] == '-':
for key in dic.keys():
dfs(dic[key], depth + 1, condition, idx)
else:
dfs(dic[condition[depth]], depth + 1, condition, idx)
def solution(info, query):
global answer, dic
answer = [0] * len(query)
language = ['cpp', 'java', 'python']
job = ['backend', 'frontend']
career = ['junior', 'senior']
food = ['chicken', 'pizza']
dic = {}
for l in language:
dic[l] = {}
for j in job:
dic[l][j] = {}
for c in career:
dic[l][j][c] = {}
for f in food:
dic[l][j][c][f] = []
for i in range(len(info)):
l, j, c, f, score = info[i].split()
dic[l][j][c][f].append(int(score))
for i in range(len(query)):
query[i] = list(query[i].split())
condition = [query[i][0], query[i][2], query[i][4], query[i][6], int(query[i][7])]
dfs(dic, 0, condition, i)
return answer해당 코드는 효율성에서 시간 초과가 나왔다..
어떤 경우가 있을까 생각해봤는데 조건이 "- and - and - and - 0"이 최대 100,000개(query크기) 있다면
하나의 query 조건을 만족하는 점수의 갯수는 최대 50,000개(info크기) 나올 수 있다.
그럼 50,000 * 100,000 을 하면 당연히 시간 초과가 나온다. 😂
Python 정답 코드
위의 시간 초과를 해결하기 위해 이분 탐색을 사용하였다.
# target 점수에 해당하는 가장 왼쪽의 index를 반환
def binary(lst, target):
start = 0
end = len(lst)
while start < end:
mid = (start + end) // 2
if lst[mid] < target:
start = mid + 1
else:
end = mid
return start
def dfs(dic, depth, condition, idx):
global answer
if depth == 4:
score = condition[depth]
start = binary(dic, score)
answer[idx] += len(dic) - start
return
if condition[depth] == '-':
for key in dic.keys():
dfs(dic[key], depth + 1, condition, idx)
else:
dfs(dic[condition[depth]], depth + 1, condition, idx)
def solution(info, query):
global answer, dic
answer = [0] * len(query)
language = ['cpp', 'java', 'python']
job = ['backend', 'frontend']
career = ['junior', 'senior']
food = ['chicken', 'pizza']
dic = {}
for l in language:
dic[l] = {}
for j in job:
dic[l][j] = {}
for c in career:
dic[l][j][c] = {}
for f in food:
dic[l][j][c][f] = []
for i in range(len(info)):
l, j, c, f, score = info[i].split()
dic[l][j][c][f].append(int(score))
for l in language:
for j in job:
for c in career:
for f in food:
dic[l][j][c][f].sort()
for i in range(len(query)):
query[i] = list(query[i].split())
condition = [query[i][0], query[i][2], query[i][4], query[i][6], int(query[i][7])]
dfs(dic, 0, condition, i)
return answer초기 코드에서는 점수 조회를 O(N)으로 하여 시간 초과가 났지만
이분 탐색을 활용하여 점수 조회를 O(log N)으로 줄였더니 효율성 테스트를 통과할 수 있었다!
Java 코드
Java 언어 학습을 위해 위의 Python 코드를 Java 언어로 변환해보았다.
import java.util.*;
class Solution {
static int[] answer;
static String[] language = {"cpp", "java", "python"};
static String[] job = {"backend", "frontend"};
static String[] career = {"junior", "senior"};
static String[] food = {"chicken", "pizza"};
int binary(List<Integer> list, int target) {
int start = 0;
int end = list.size();
while (start < end) {
int mid = (start + end) / 2;
if (list.get(mid) < target) {
start = mid + 1;
} else {
end = mid;
}
}
return start;
}
void dfs(Object obj, int depth, String[] condition, int idx) {
if (depth == 4) {
List<Integer> scores = (ArrayList<Integer>) obj;
int score = Integer.parseInt(condition[depth]);
int start = binary(scores, score);
answer[idx] += scores.size() - start;
return;
}
Map<String, Object> map = (HashMap<String, Object>) obj;
if (condition[depth].equals("-")) {
for (String key : map.keySet()) {
dfs(map.get(key), depth + 1, condition, idx);
}
} else {
dfs(map.get(condition[depth]), depth + 1, condition, idx);
}
}
public int[] solution(String[] info, String[] query) {
answer = new int[query.length];
Map<String, Map<String, Map<String, Map<String, List<Integer>>>>> map = new HashMap<>();
for (String l : language) {
map.put(l, new HashMap<>());
for (String j : job) {
map.get(l).put(j, new HashMap<>());
for (String c : career) {
map.get(l).get(j).put(c, new HashMap<>());
for (String f : food) {
map.get(l).get(j).get(c).put(f, new ArrayList<>());
}
}
}
}
for (String information : info) {
String[] line = information.split(" ");
map.get(line[0]).get(line[1]).get(line[2]).get(line[3]).add(Integer.parseInt(line[4]));
}
for (String l : language) {
for (String j : job) {
for (String c : career) {
for (String f : food) {
Collections.sort(map.get(l).get(j).get(c).get(f));
}
}
}
}
for (int i = 0; i < query.length; i++) {
String[] condition = query[i].replace(" and ", " ").split(" ");
dfs(map, 0, condition, i);
}
return answer;
}
}Python을 사용할 때는 데이터 타입을 명시할 필요가 없어 간단한 코드 작성이 가능했지만
Java 코드에서는 명시가 필요하기 때문에 dfs에서 Object를 매개변수로 받고 캐스팅을 사용했다.
(이런 식으로 코드를 작성하는게 적절한지는 모르겠다...)
Java 개선된 코드
위의 코드를 개선하기 위해 다른 사람의 Java 코드를 살펴보았다.
✅ "언어", "직군", "경력", "소울푸드" 가 속할 수 있는 모든 경우의 수를 구해 map에 점수를 넣어준다.
ex) [ "java", "backend", "junior", "pizza", "150" ]는 아래의 경우에 모두 해당되므로, 점수를 넣어준다.
✅ info에 대해 처리를 완료하면, 다음과 같다.
// info가 포함될 수 있는 문장
private static void makeSentence(String[] p, String str, int cnt) {
if (cnt == 4) {
if (!map.containsKey(str)) {
List<Integer> list = new ArrayList<Integer>();
map.put(str, list);
}
map.get(str).add(Integer.parseInt(p[4]));
return;
}
makeSentence(p, str + "-", cnt + 1);
makeSentence(p, str + p[cnt], cnt + 1);
}✅ query의 각 문장을 다음과 같이 만들어준다.
ex) [ "javabackendjuniorpizza", "100" ]
query[i] = query[i].replaceAll(" and ", "");
String[] q = query[i].split(" ");전체 코드
import java.util.*;
class Solution {
static Map<String, List<Integer>> map;
public static int[] solution(String[] info, String[] query) {
int[] answer = new int[query.length];
map = new HashMap<String, List<Integer>>();
for (int i = 0; i < info.length; i++) {
String[] p = info[i].split(" ");
makeSentence(p, "", 0);
}
for (String key : map.keySet())
Collections.sort(map.get(key));
for (int i = 0; i < query.length; i++) {
query[i] = query[i].replaceAll(" and ", "");
String[] q = query[i].split(" ");
answer[i] = map.containsKey(q[0]) ? binarySearch(q[0], Integer.parseInt(q[1])) : 0;
}
return answer;
}
// 이분 탐색
private static int binarySearch(String key, int score) {
List<Integer> list = map.get(key);
int start = 0, end = list.size() - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (list.get(mid) < score)
start = mid + 1;
else
end = mid - 1;
}
return list.size() - start;
}
// info가 포함될 수 있는 문장
private static void makeSentence(String[] p, String str, int cnt) {
if (cnt == 4) {
if (!map.containsKey(str)) {
List<Integer> list = new ArrayList<Integer>();
map.put(str, list);
}
map.get(str).add(Integer.parseInt(p[4]));
return;
}
makeSentence(p, str + "-", cnt + 1);
makeSentence(p, str + p[cnt], cnt + 1);
}
}❗ 후기
Python의 문법은 간단하고 단순하지만 Java 문법은 직접 데이터 명시와 캐스팅을 적용하다 보니 완성된 코드를 변환하는 것도 쉽지 않았다.
또한, 알고리즘 문제에서도 경우의 수를 늘린다면 조회가 늘어나 시간을 더 차지할 것이다고 생각하여 Dictionary (or Map) 자료구조를 사용하였다.
하지만 주어진 경우의 수를 계산했을 때 하나의 info에서 나올 수 있는 경우의 수가 16개이기 때문에 map을 사용해서 depth를 늘이는 것보다 오히려 시간을 단축할 수 있었고 코드도 간결해졌다.
이번 문제로 시간복잡도를 명확하게 계산하여 문제 분석을 더 꼼꼼히 해야 하고 Java로 문제를 많이 풀어봐야겠다는 것을 새삼 느낄 수 있었다.
📌 참고
📞피드백 너무나 환영