일단 씻고 나가자
순위 검색 본문
이것도 푸는 데 진짜 한참 걸렸다.
문제 자체는 쉬워서 호기롭게 도전했지만 정확성만 맞히는 데에도 한참 걸렸다.
기본기가 중요하다고 느낀 문제.
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/72412
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
Problem
간략하게 DB를 만들고, 문제에 주어지는 쿼리를 날려보라 이거다.
문제는 설명할 것이 없고, 효율성까지 따졌을 때 크게 대두되는 문제는 다음과 같다.
- 어떤 식으로 DB를 만들 것인가?
- 와일드 카드 ( - ) 가 나왔을 때 어떻게 검색할 것인가?
- 저장된 점수들 중 X점 이상 받은 사람의 수를 어떻게 찾을 것인가?
이때 와일드 카드에 대해 미리 구상을 마치고 DB 구성을 들어가야 하며,
X점 이상 받은 사람의 수를 구하는 알고리즘에 대해서도 염두 해야 시간 초과를 피할 수 있다.
Idea
우선 워스트 케이스를 생각해 두고 문제에 들어가야 한다.
info 의 경우 언어 * 직군 * 경력 * 소울 푸드 총 24가지의 경우가 존재하며,
최대 50,000 가지가 주어질 수 있다.
query 의 경우에는 최대 100,000 가지가 주어질 수 있다.
먼저 자료구조에 대한 아이디어이다.
DB 형태로 조건을 타고 가다 보니
자료구조는 당연히 HashMap 이 최선일 것이다.
근데 조건이 4개이므로..
HashMap< String, HashMap< String, HashMap< String, HashMap< String, ArrayList<Integer> > > > >
초기화에서만 해도 이런 기괴한 형태를 띄게 된다..
조건이 4개여서 망정이지 5개 10개로 늘어났다면 더 긴 지렁이가..
또한 와일드 카드 ( - ) 에 대한 고민이 필요한데,
별다른 전처리 없이 info 데이터를 모두 저장한다면
최대 100,000 의 query 가 모두 "- and - and - and - and - X" 일 때
매번 모든 DB 의 점수를 탐색해야 하는 비효율이 발생한다.
따라서 데이터를 저장할 때 미리 와일드 카드에 대한 정보를 저장하는 것이 중요하다.
마지막으로 X점 이상인 점수의 개수를 찾는 알고리즘은
필연적으로 정렬이 필요한데,
매 query 마다 해당하는 점수 list 를 정렬하여 탐색한다면
info 데이터가 "java backend junior pizza X" 하나의 종류로만 50,000 가지 점수가 주어지고,
query 가 "java and backend and junior and pizza 0" 하나로 100,000 가지가 주어지는 상황에서
[100,000 query * 50,000 개 데이터 정렬] 이라는 최악의 워스트 케이스가 탄생한다.
따라서 미리 24 가지의 종류에 주어진 점수들을 정렬해놓고,
매 query 마다 정렬된 정보에서 X점 이상을 탐색하는 방법이 필요하다.
Solution
자료구조의 경우 다른 분들이 푼 답안을 찾아본 결과
보통 HashMap<String, ArrayList<Integer>> 으로
"가 and 나 and 다 and 라" 까지를 통채로 key 로 저장한 케이스가 대부분인 것 같다.
근데 난 뭐랄까.. 이 방법이 개발자스럽지 않다고 생각해서..
형태가 DB 스럽지도 않고..
만약 종류가 늘어나거나 했을 때의 유지보수가 전혀 안 되지 않을까 하는 생각이 들었다.
(그냥 스스로의 고집이다. 코테에 뭔 유지보수가 필요하냐)
어쨌든 그래서 통째로 저장하는 방법보다
Object 를 이용한 형변환을 통해 HashMap 을 손쉽게 초기화하고 탐색하는 방법을 고안하였다.
root = new HashMap<>();
prevList.add(root);
for(int i=0; i<types.length; i++) {
for(Object obj : prevList) {
prevMap = (HashMap<String, Object>) obj;
for(String type : types[i]) {
temp = i < types.length-1 ? new HashMap<String, Object>() : new ArrayList<Integer>();
prevMap.put(type, temp);
tempList.add(temp);
}
}
prevList = new ArrayList<>(tempList);
tempList.clear();
}
간략하게 코드를 설명하면, HashMap<String, Object> 라는 root map을 생성하고,
다음 for문에서 root 의 value 인 Object 를 (HashMap<String, Object>) object 로 다운캐스팅하여 또 생성,
또 다음 for문에서 이전의 HashMap 들을 가져와서 반복.. 하는 식으로 map 을 초기화하였다.
이때 마지막 Object 는 점수의 목록을 저장하는 ArrayList 가 될 것이므로 HashMap 으로 캐스팅하면 안 되기에,
마지막 경우에서만 Object 를 ArrayList 로 다운캐스팅하여 저장하였다.
for(Object obj : prevList) {
tempMap = (HashMap<String, Object>) obj;
tempList.add(tempMap.get(data[i]));
tempList.add(tempMap.get(WILD_CARD));
}
이는 검색의 경우에서도 동일하게 진행되며,
깔끔하게 root String 검색 -> ( (HashMap) object ) String 검색 -> ... -> ArrayList 점수 목록
의 형태로 다운캐스팅을 연속하며 검색이 가능하게 된다.
와일드 카드 ( - ) 의 경우
앞서 설명했듯 query 가 주어졌을 때
그제서야 와일드 카드를 고려하게 된다면 시간 초과를 발생시킬 수 있으므로,
데이터를 저장할 때 미리 와일드 카드 데이터를 저장하여 검색 속도를 향상 시키는 방법을 적용했다.
String WILD_CARD = "-";
String[][] types = {
{"cpp", "java", "python", WILD_CARD},
{"backend", "frontend", WILD_CARD},
{"junior", "senior", WILD_CARD},
{"chicken", "pizza", WILD_CARD}
};
먼저 종류를 저장할 때 미리 와일드 카드를 저장하며
와일드 카드 또한 하나의 종류로 취급하였다.
for(int i=0; i<data.length-2; i++) {
for(Object obj : prevList) {
tempMap = (HashMap<String, Object>) obj;
tempList.add(tempMap.get(data[i]));
tempList.add(tempMap.get(WILD_CARD));
}
prevList = new ArrayList<>(tempList);
tempList.clear();
}
// 깔끔한 형변환 실패. 개선 필요
for(Object obj : prevList) {
tempMap = (HashMap<String, Object>) obj;
scoreList = (ArrayList<Integer>) tempMap.get(data[data.length-2]);
scoreList.add(score);
scoreList = (ArrayList<Integer>) tempMap.get(WILD_CARD);
scoreList.add(score);
}
또한 데이터를 하나씩 저장할 때,
주어진 종류 뿐만 아니라 와일드 카드도 함께 저장하여
나올 수 있는 모든 경우에 점수를 다 저장하였다.
즉, "java backend junior pizza 10" 라는 데이터가 주어졌을 때,
- [java] , [-]
- [java backend] , [java -] , [- backend] , [- -]
- [java backend junior] , [java backend -] , [java - junior] , [java - -] , [- backend junior] ...
- ...
같은 방법으로 2배씩 늘어나며 나올 수 있는 모든 경우의 수를 List 에 저장하고,
탐색이 점수를 저장하는 ArrayList 까지 도달했을 때, List 의 모든 경우의 수에 점수를 모두 저장하여
모든 경우를 고려 + query 시 한 번에 탐색 가능 의 이점을 생각하였다.
마지막으로 X점 이상인 점수 개수를 찾는 정렬 및 알고리즘에 대해선
데이터가 모두 저장 되었을 시점에 미리 전체 정렬 방식과
정렬된 점수 List 에 이진 탐색 기법을 적용하여 탐색하는 방식을 통해
알고리즘을 고안하였다.
for(Object obj : objList) {
scoreList = (ArrayList) obj;
Collections.sort(scoreList);
}
먼저 query 의 탐색 이전에 먼저 전체 점수 ArrayList 들을 sort 했으며,
(나의 경우 모든 ArrayList 가 아닌, 데이터가 들어간 ArrayList 들만 추출 후 sort 하였다)
public static int lowerBinarySearchAndCount(ArrayList<Integer> scores, int score) {
int down = 0;
int up = scores.size();
while(down < up) {
int mid = (down + up) / 2;
if(scores.get(mid) < score) {
down = mid + 1;
}else {
up = mid;
}
}
return scores.size() - down;
}
주어진 X점 이상의 개수를 구해야할 땐 이진 탐색의 LowerBound 를 적용하였다.
이전에 미리 ArrayList 들을 sort 하였기에 이진 탐색 시엔 sort 가 필요하지 않다.
Code (HashMap, Binary Search)
HashMap 을 이용하여 DB 를 구축하고,
와일드 카드를 고려하여 데이터를 저장하고,
X점 이상을 탐색할 때를 고려하여 우선 정렬 + 이진 탐색을 적용한
전체 코드는 다음과 같다. (조금 길다..)
import java.util.*;
class Solution {
public int[] solution(String[] infos, String[] querys) {
// 사용할 변수들
String WILD_CARD = "-";
String[][] types = {
{"cpp", "java", "python", WILD_CARD},
{"backend", "frontend", WILD_CARD},
{"junior", "senior", WILD_CARD},
{"chicken", "pizza", WILD_CARD}
};
ArrayList<Object> objList;
ArrayList<Integer> scoreList;
ArrayList<Object> prevList;
ArrayList<Object> tempList;
HashMap<String, Object> root;
HashMap<String, Object> prevMap;
HashMap<String, Object> tempMap;
Object temp;
Object prev;
// hashmap (DB) 초기화
prevList = new ArrayList<>();
tempList = new ArrayList<>();
root = new HashMap<>();
prevList.add(root);
for(int i=0; i<types.length; i++) {
for(Object obj : prevList) {
prevMap = (HashMap<String, Object>) obj;
for(String type : types[i]) {
temp = i < types.length-1 ? new HashMap<String, Object>() : new ArrayList<Integer>();
prevMap.put(type, temp);
tempList.add(temp);
}
}
prevList = new ArrayList<>(tempList);
tempList.clear();
}
objList = new ArrayList<>(prevList);
// info (Data) 저장
String[] data;
tempList = new ArrayList<>();
prevList = new ArrayList<>();
for(String info : infos) {
data = info.split(" ");
int score = Integer.parseInt(data[data.length-1]);
prevList = new ArrayList<>();
prevList.add(root);
for(int i=0; i<data.length-2; i++) {
for(Object obj : prevList) {
tempMap = (HashMap<String, Object>) obj;
tempList.add(tempMap.get(data[i]));
tempList.add(tempMap.get(WILD_CARD));
}
prevList = new ArrayList<>(tempList);
tempList.clear();
}
for(Object obj : prevList) {
tempMap = (HashMap<String, Object>) obj;
scoreList = (ArrayList<Integer>) tempMap.get(data[data.length-2]);
scoreList.add(score);
scoreList = (ArrayList<Integer>) tempMap.get(WILD_CARD);
scoreList.add(score);
}
}
// 점수 sort
for(Object obj : objList) {
scoreList = (ArrayList) obj;
Collections.sort(scoreList);
}
// query 분석
int[] answer = new int[querys.length];
String[] queryArr;
for(int i=0; i<querys.length; i++) {
queryArr = querys[i].split(" and | ");
prev = root;
for(int j=0; j<queryArr.length-1; j++) {
prev = ((HashMap<String, Object>) prev).get(queryArr[j]);
}
answer[i] = lowerBinarySearchAndCount((ArrayList<Integer>) prev, Integer.parseInt(queryArr[queryArr.length-1]));
}
return answer;
}
// 이진 탐색 메서드
public int lowerBinarySearchAndCount(ArrayList<Integer> scores, int score) {
int down = 0;
int up = scores.size();
while(down < up) {
int mid = (down + up) / 2;
if(scores.get(mid) < score) {
down = mid + 1;
}else {
up = mid;
}
}
return scores.size() - down;
}
}
시간과 공간이 많이.. 많이 들었지만..
통과는 했으니까.. 괜찮.. 을 것이다..
End
생각보다 시간과 공간이 많이 들어서 형변환 방식이 많이 비효율적인가 생각이 든다.
다른 분들의 방식인 String 통째로 저장 방식과 많이 다른 것 같지도 않고..
그래도 덕분에 문제 풀면서 자바의 형변환에 대해 많이 익숙해지고 공부한 좋은 기회가 되었다.
결과는 아쉽지만.. 새로운 걸 얻게 되었으니 기분 좋게 마무리 ^!^
'Coding-Test > 프로그래머스를 자바라' 카테고리의 다른 글
| 가장 긴 팰린드롬 (0) | 2024.06.28 |
|---|---|
| 과제 진행하기 (0) | 2024.03.21 |
| 최고의 집합 (0) | 2024.02.25 |
| 단체사진 찍기 (0) | 2024.02.16 |
| 야근 지수 (1) | 2024.02.11 |
