프로그래머스 고득점 Kit 하루 만에 뽀개기 - 1. 해시(Java, C++)

https://programmers.co.kr/learn/courses/30/parts/12077

프로그래머스

- 알고리즘 풀이로 C++를 주로 사용하다가 기업 코딩테스트를 위해 java 풀이를 학습하는 사람에게 도움이 될만한 포스트입니다. 알고리즘 적인 해설내용은 줄이고 C++에 익숙한 사람들이 Java 사용시 놓칠만한 내용 위주로 작성하고 있습니다.

 

- 알고리즘 문제 풀이는 최대한 짧은 시간 안에 문제에서 주어진 제한조건(주어진 변수)에 대해서 적절한 시간복잡도를 가지는 자료구조와 알고리즘을 사용하는 것을 최우선의 목표로 한다. 반대로 기존의 자료구조와 알고리즘들의 시간복잡도를 잘 알고 있다면, 문제에서 주어진 변수범위를 이용하여 적절한 알고리즘을 생각해낼 수 있다. 

- 문제 풀이시에 왠만한 클래스들은 java.util 패키지에 있다. (Map, Set, Queue, PriorityQueue 등의 컬렉션 프레임워크 등..),

- Java에서 String은 불변객체이기 때문에 문제에서 String 연산이 많이 필요하다면 java.lang 패키지에 있는 StringBuilder를 사용한다

# 유형 설명

- C++에서의 map, set, Java에서의 TreeMap, TreeSet 등 은 Red-Black tree로 구현되어 있기 때문에 Key값에 대하여 정렬이 되고 lookup에 대한 시간복잡도는 O(logN)이다

- C++에서의 unordered_map, unordered_set, Java에서의 HashMap, HashSet 등은 hash로 구현이 되어있기 때문에 Key값에 대하여 정렬은 되지 않고, lookup에 대한 시간복잡도는 O(1)이다. 따라서 중복제거가 필요한 문제 풀이 시에 정렬이 필요하지 않다면 이 자료구조를 사용하면 된다. 

- 알고리즘 문제 풀이 시에 key값이 Object 타입이여야 하는 경우가 있다(좌표계에서의 Point(x,y) 등..). Key값이 Object일 경우 해쉬테이블에서 사용하기 위해서는 해쉬함수와 비교연산자 ==를 오버라이딩(재정의)해줘야 해줘서 시간이 더 필요하다. 그래서 C++로 문제풀이시에는 대부분 std::pair 컨테이너를 이용하여 정의한다. pair에는 비교연산자가 이미 재정의 되어있기 때문에 추가적인 코드 작성이 필요없다. 하지만 java의 경우에는 표준 라이브러리에 Pair 클래스가 없기 때문에 따로 정의를 해주고, 정렬을 위해서 Comparator를 따로 정의해줘야한다. 

1. 완주하지 못한 선수

https://programmers.co.kr/learn/courses/30/lessons/42576

코딩테스트 연습 - 완주하지 못한 선수

- participants에는 있고, completion에는 없는 선수를 찾는다. 선수의 수 N이 최대 10만이므로 10만^2 = 100억, O(N^2) 미만으로 풀어야한다. 동명이인이 있으므로 Set이 아니라 map으로 카운트해주고 소거해나간다. 

// C++
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer;
    unordered_map<string, int> umap;
    for (string name : participant) {
        ++umap[name];
    }
    for (string name : completion) {
        --umap[name];
    }
    for (auto& [key, val] : umap) {
        if (val == 1) {
            answer = key;
            break;
        }
    }

    return answer;
}

// java
import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String ans = "";
        Map<String, Integer> map = new HashMap<>();
        for(String s: participant) {
            map.put(s, map.getOrDefault(s, 0) + 1);
        }
        for(String s: completion) {
            if(map.containsKey(s)) map.put(s, map.get(s) - 1);
        }    
        for(String s: map.keySet()) {
            if(map.get(s) != 0) {
                ans = s;
                break;
            }
        }
        
        return ans;
    }
}

- 자바에는 Map 인터페이스에 구현되어있는 편리한 메서드들이 많다. 키 값이 없을 시 디폴트 값을 반환해주는 getOrDefault(), 키 유무 조회시 containsKey(), map의 전체 키를 Set으로 반환해주는 Keyset()... 

2. 전화번호 목록

https://programmers.co.kr/learn/courses/30/lessons/42577

코딩테스트 연습 - 전화번호 목록

// c++
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

bool solution(vector<string> phone_book) {  // N^2 미만
    unordered_map<string, int> umap;

    for (string& num : phone_book)
        umap[num]++;

    for (string& num : phone_book) {
        for (int i = 0; i < num.length() - 1; ++i) {
            string substring = num.substr(0, i + 1);
            if (umap[substring]) {
                return false;
            }
        }
    }

    return true;
}

// java
import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) { // 100만
        Set<String> set = new HashSet<>(Arrays.asList(phone_book));
        for(String s: phone_book) {
            for(int i = 0; i < s.length() - 1; ++i) {
                String sub = s.substring(0, i + 1);
                if(set.contains(sub)) {
                    return false;
                }
            }
        }
        
        return true;
    }
}

- Array.asList는 arrays의 정적 클래스인 ArrayList를 반환한다. 풀이에서는 중복제거를 위해 HashSet의 초기값으로 사용하였다.

- c++에서의 substr과 java의 substring의 파라미터가 약간 달라서 혼동이 있을 수 있다.
substr(pos, count): pos번째부터 count길이만큼의 부분문자열 반환
substring(start, end): [start, end) 부분문자열 반환

asList​(T... a)

static <T> List<T>

Returns a fixed-size list backed by the specified array.

HashSet​(Collection<? extends E> c)

Constructs a new set containing the elements in the specified collection.

3. 위장

https://programmers.co.kr/learn/courses/30/lessons/42578

코딩테스트 연습 - 위장

- 각 의상종류별 집합의 갯수를 세고, 이 조합으로 만들 수 있는 모든 부분집합의 갯수를 센다. 

#include <unordered_map>
#include <vector>
using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;
    unordered_map<string, int> umap;
    for (auto p : clothes) {
        ++umap[p[1]];
    }
    // {a: 2, b: 1} 이면 2+1+1*2 = 5
    for(auto& [k, v]: umap) {
        answer += v * answer;
    }
    
    return answer - 1; // 공집합
}

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int ans = 1;
        Map<String, Integer> map = new HashMap<>();
        for(var a: clothes) {
            map.put(a[1], map.getOrDefault(a[1], 0) + 1);
        }
        for(String type: map.keySet()) {
            ans += ans * map.get(type);
        }
        return ans - 1;
    }
}

- C++에서는 맵에서 키값 체크 없이도 value값 조회가 가능하지만 java에서는 항상 getOrDefault로 get 초기값을 지정해줘서 NPE를 피해준다.

4. 베스트앨범

https://programmers.co.kr/learn/courses/30/lessons/42579

코딩테스트 연습 - 베스트앨범

- 노래 장르별 갯수를 카운트하는 해시, 각 장르별로 노래들의 재생횟수를 정렬할 수 있는 해시 2개를 선언해주고 수록기준에 따라 정렬해준다. 우선순위대로 장르마다 2개씩 넣어주는데 장르곡이 1개면 1개만 넣어준다. 

// C++
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

// 1. 많이 재생된 장르
// 2. 장르 내에서 많이 재생된 노래
// 3. 고유번호가 낮은 노래

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    int N = genres.size();
    
    unordered_map<string, int> map; // {장르, 총횟수}
    unordered_map<string, vector<pair<int,int>>> umap; // {장르 : {{재생횟수, 고유번호}, {재생횟수, 고유번호}} }
    
    for(int i = 0; i < N; ++i) {
        map[genres[i]] += plays[i];
        umap[genres[i]].push_back({plays[i], i});
    }
    
    vector<pair<string, int>> totalPlay(map.begin(), map.end()); 
    sort(totalPlay.begin(), totalPlay.end(), [](pair<string,int> a, pair<string,int> b) {
        return a.second > b.second;
    }); // 내림차순으로 많이 재생된 장르 정렬
    
    for(auto& [k, v]: umap) {
        sort(v.begin(), v.end(), [](pair<int,int> a, pair<int,int> b) { // {재생횟수, 고유번호}
            if(a.first == b.first) return a.second < b.second;
            return a.first > b.first;
        });
    }
    
    int M = map.size();
    for(int i = 0; i < M; ++i) {
        string genre = totalPlay[i].first; // 먼저 뽑을 장르
        int len = umap[genre].size(); // 해당 장르 노래갯수
        
        for(int j = 0; j < (len >= 2 ? 2 : 1); ++j) { // 2개씩 넣는다
            answer.push_back(umap[genre][j].second);
        }   
    }
    
    return answer;
}

// java
import java.util.*;

class Solution {
    class M {
        int idx, play;
        M(int i, int p) {
            this.idx = i;
            this.play = p;
        }
    }
    
    public List<Integer> solution(String[] genres, int[] plays) {
        int N = genres.length;
        
        Map<String, Integer> map = new HashMap<>(); // 장르, 총횟수
        Map<String, List<M>> map2 = new HashMap<>(); // 장르: {고유변호, 재생횟수},{}...
        
        for(int i = 0; i < N; ++i) {
            map.put(genres[i], map.getOrDefault(genres[i], 0) + plays[i]);
            if(map2.containsKey(genres[i])) {
                map2.get(genres[i]).add(new M(i, plays[i]));
            } else {
                List<M> list = new ArrayList<>();
                list.add(new M(i, plays[i]));
                map2.put(genres[i], list);
            }
        }
        
        List<String> order = new ArrayList<>(map.keySet()); // 장르 순서
        order.sort((String a, String b) -> map.get(b) - map.get(a)); // 내림차순
        
        List<Integer> ans = new ArrayList<>();
        for(String g: order) {
            List<M> list = new ArrayList<>(map2.get(g));
            list.sort((a, b) -> {
                if(a.play == b.play) return a.idx - b.idx;
                return b.play - a.play;
            });
            for(int i = 0; i < (list.size() >= 2 ? 2 : 1); ++i) {
                ans.add(list.get(i).idx);
            }
        }
        
        return ans;
    }
}

- C++에서 단순 오름차순, 내림차순 정렬 외의 정렬을 할 때는 c++ compare함수나 java Comparator를 오버라이딩해야되는데, 람다식으로 써도 된다. 자바 람다식으로 Comparator를 쓸때는 boolean값이 아니라 int값을 리턴해줘야 된다

- 자바 문제 풀이시에 고정사이즈 배열을 반환해야되서 불편한 경우가 많다. 다시 배열선언 뒤 Integer값을 int로 변환해줘도 되고 stream의 매핑을 이용해도 된다