문제 링크
실패한 문제 풀이
- 실패한 풀이
정확성은 모두 맞췄지만 효율성에서는 전부 실패했다.
쿼리 하나를 검사하기 위해서 모든 회원들에 대해서 for문을 돌려야 하기 때문에 효율성면에서 떨어진다는 생각이 들었고 이를 갈아엎기로 했다.
- 실패한 코드
import java.util.*;
import java.util.*;
class Solution {
class Person{
String language;
String part;
String career;
String food;
int score;
public Person(String language, String part, String career, String food,int score){
this.language = language;
this.part = part;
this.career = career;
this.food = food;
this.score = score;
}
public String toString(){
return language + " " + part + " " + career + " " + food + " "+score;
}
}
public int[] solution(String[] info, String[] query) {
int[] answer = new int[query.length];
List<Person> arr = new ArrayList();
for(int i =0; i<info.length; i++){
String [] data = info[i].split(" ");
arr.add(new Person(data[0],data[1],data[2],data[3],Integer.parseInt(data[4])));
}
//System.out.println(arr.toString());
for(int i=0; i<query.length; i++){
String [] test = new String[5];
List<Person>arr2 = new ArrayList<>();
arr2.addAll(arr);
int len = arr2.size();
//System.out.println(i+ ": len : "+len);
for(int j=0; j<5; j++){
if(j<3){
test[j]= query[i].split("and")[j].trim();
}else if(j==3){
test[j] = query[i].split("and")[3].trim().split(" ")[0].trim();
}else{
test[j] = query[i].split("and")[3].trim().split(" ")[1].trim();
}
}
//System.out.println(Arrays.toString(test));
for(int k=len-1; k>=0; k--){
for(int j=0; j<test.length; j++){
if("-".equals(test[j])){
continue;
}else if(j==0){
if(!test[j].equals(arr2.get(k).language)){
arr2.remove(k);
break;
}
}else if(j==1){
if(!test[j].equals(arr2.get(k).part)){
arr2.remove(k);
break;
}
}else if(j==2){
if(!test[j].equals(arr2.get(k).career)){
arr2.remove(k);
break;
}
}else if(j==3){
if(!test[j].equals(arr2.get(k).food)){
arr2.remove(k);
break;
}
}else{
// System.out.println(test[j]);
if(Integer.parseInt(test[j])>arr2.get(k).score){
arr2.remove(k);
}
}
}
}
answer[i]=arr2.size();
}
return answer;
}
}문제 풀이
접근법 1.
이전에는 사람들에 대한 정보가 담기는 info 배열을 parsing해서 담았다.
하지만 - 라는 정보도 함께 고려해서 저장하기로 했다.
ex)java backend junior pizza 150
이라는 데이터에 대해서
language = java, part=backend 이렇게 담았던것을 모든 문자열을 합쳐서 Map의 키로 만들었다. (javabackendjuniorpizza와 같은 형태로.)
하지만 각 정보에 - 가 들어올경우 그 부분에 대해서는 고려하지 않기 떄문에
javabackendjuniorpizza와 -backendjuniorpizza는 같은 값이라고도 볼수있다.
그렇기에 각 부분마다 (기존의 정보, -) 2가지 가능성을 고려해서 2의 4제곱의 key가 나오게 되었다.
이렇게 저장하게 되면 같은 키에 대해서 다른 점수를 가진 데이터를 저장하게 되는데 value를 arraylist형으로 선언하여 같은 키값이 들어올경우 arraylist에 value값들을 저장해주었다.
public void makeKey(String info){
String [] temp = info.split(" ");
String [] language = {temp[0],"-"};
String [] part = {temp[1],"-"};
String [] career ={temp[2],"-"};
String [] food = {temp[3],"-"};
int score = Integer.parseInt(temp[4]);
for(int i=0; i<language.length;i++){
for(int j=0; j<part.length;j++){
for(int k=0; k<career.length;k++){
for(int p=0; p<food.length; p++){
String key = language[i]+part[j]+career[k]+food[p];
if(infoMap.containsKey(key)){
ArrayList<Integer> arr = infoMap.get(key);
arr.add(score);
//Collections.sort(arr);
infoMap.put(key,arr);
}else{
ArrayList<Integer> arr = new ArrayList();
arr.add(score);
infoMap.put(key,arr);
}
}
}
}
}
return;
}접근법 2.
value들에 대한 정렬을 쿼리를 처리하기 전에 한번 다 정리해야지 시간단축을 할 수 있다.else{ savekey.add(entry.getKey()); Collections.sort(entry.getValue()); }
접근법 3.
정렬된 배열에서 최소값을 찾는 것은 이분탐색(binary_search 사용)
이것을 활용하여 정렬된 배열에서 찾고싶은값 이상인 부분이 최초로 등장하는 부분을 찾는 알고리즘이 Lower bound, 찾고싶은값 초과하는 부분이 최초로 등장하는 부분을 찾는 알고리즘이 Upper bound 이다.
이 문제에서는 점수 이상이 몇명인지 찾는문제이므로 Lower bound 알고리즘을 적용했다.
while (end > start) // end가 start보다 같거나 작아지면, 그 값이 Lower Bound이므로 반복을 종료한다.
{
mid = (start + end) / 2;
if (arr.get(mid) >= score) // 중간값이 원하는 값보다 크거나 같을 경우, 끝값을 중간값으로 설정하여 다시 탐색한다.
end = mid;
else start = mid + 1; // 중간값이 원하는 값보다 작을 경우, 시작값을 중간값+1로 설정하여 다시 탐색한다.
}
return arr.size()-start;
}코드
import java.util.*;
class Solution {
static Map<String,ArrayList<Integer>>infoMap = new HashMap();
public int[] solution(String[] info, String[] query) {
int[] answer = new int[query.length];
//키 만들기
for(int i=0; i<info.length; i++){
makeKey(info[i]);
}
//value값들 정렬
ArrayList<String> savekey = new ArrayList();
for(Map.Entry<String,ArrayList<Integer>> entry : infoMap.entrySet()){
if(savekey.contains(entry.getKey())){
continue;
}else{
savekey.add(entry.getKey());
Collections.sort(entry.getValue());
}
}
//query부분 처리
for(int i=0; i<query.length; i++){
String [] temp = query[i].split(" ");
String key = temp[0]+temp[2]+temp[4]+temp[6];
if(!infoMap.containsKey(key)){
answer[i]=0;
continue;
}
ArrayList<Integer> arr = infoMap.get(key);
if("-".equals(temp[7])){
answer[i] = arr.size();
}else{
int score = Integer.parseInt(temp[7]);
//이분탐색
answer[i] = binarySearch(arr,score);
}
}
//System.out.println(infoMap.toString());
return answer;
}
public void makeKey(String info){
String [] temp = info.split(" ");
String [] language = {temp[0],"-"};
String [] part = {temp[1],"-"};
String [] career ={temp[2],"-"};
String [] food = {temp[3],"-"};
int score = Integer.parseInt(temp[4]);
for(int i=0; i<language.length;i++){
for(int j=0; j<part.length;j++){
for(int k=0; k<career.length;k++){
for(int p=0; p<food.length; p++){
String key = language[i]+part[j]+career[k]+food[p];
if(infoMap.containsKey(key)){
ArrayList<Integer> arr = infoMap.get(key);
arr.add(score);
//Collections.sort(arr);
infoMap.put(key,arr);
}else{
ArrayList<Integer> arr = new ArrayList();
arr.add(score);
infoMap.put(key,arr);
}
}
}
}
}
return;
}
public int binarySearch(ArrayList<Integer> arr, int score){
int mid=0;
int end = arr.size();
int start = 0;
while (end > start) // end가 start보다 같거나 작아지면, 그 값이 Lower Bound이므로 반복을 종료한다.
{
mid = (start + end) / 2;
if (arr.get(mid) >= score) // 중간값이 원하는 값보다 크거나 같을 경우, 끝값을 중간값으로 설정하여 다시 탐색한다.
end = mid;
else start = mid + 1; // 중간값이 원하는 값보다 작을 경우, 시작값을 중간값+1로 설정하여 다시 탐색한다.
}
return arr.size()-start;
}
}
하루하루는 성실하게 인생 전체는 되는대로