Hash
해시는 key-value 쌍으로 이루어 데이터를 저장하는 자료구조이다. 해시는 key-value 쌍으로 주어져 있고 배열의 인덱스를 key 값으로 사용할 수 있으므로 검색 및 저장이 빠르다. 더 나아가 해시함수(해시 알고리즘)을 이용하면 key-value의 1대1 대응을 특정 값으로 바꿀 수 있으므로 암호화에 사용된다. 해쉬 함수에 input(key)값을 넣으면 value 값이 나오므로 저장 단계의 시간복잡도는 O(1)이다. 하지만 value가 겹치는 경우가 발생하면 1대1 대응을 위반하므로 복잡도가 높아질 수 있다.
문제
완주하지 못한 선수
https://programmers.co.kr/learn/courses/30/lessons/42576
문제
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
제한사항
1. 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
2. completion의 길이는 participant의 길이보다 1 작습니다.
3. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
4. 참가자 중에는 동명이인이 있을 수 있습니다.
예시
## participant, completion, return
[leo, kiki, eden] [eden, kiki] leo
풀이
단순히 participant 배열의 모든 원소를 completion 원소와 비교해가면서 완주 여부를 파악하면 n*(n-1)의 복잡도가 걸리므로 복잡도가 높아진다. (participant와 completion 명단이 1명빼고 모두 같다는 점을 이용하여 알파벳 순 정렬 후 for문을 n번만 돌리면 완주하지 못한 선수를 찾을 수 있지만 이번에 해시를 이용해보도록 하자)
c++ std에는 hash_map이 들어있지 않다. 그리고 c++11 부터 해시 테이블이 추가되었는데 기존에 있던 hash_map과의 충돌 때문에 unordered_map으로 사용할 수 있다. (그냥 map은 tree로 구현하기 때문에 완전히 다른방식이다.)
unordered_map으로 만들고 효율적인 검색을 위해 key를 이름으로 둔다. hash map 안에서 이름을 검색하며 value를 완주여부로 이용하면 된다.
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
string solution(vector<string> participant, vector<string> completion) {
string answer = "";
unordered_map <string, int> list_complt;
for(int i=0; i<participant.size(); i++){
list_complt[participant[i]]++;
}
for(int i=0; i<completion.size(); i++){
list_complt[completion[i]]--;
}
for(auto pair: list_complt){
if(pair.second > 0){
answer = pair.first;
}
}
return answer;
}
c++11 에서는 range-based for문을 제공하여 요소기반으로 손쉽게 for문을 구성할 수 있다. for(int a : vector){…} 와 같이 작성할 수 있다.
한명(key) 당 value가 1씩 더해서 들어간다. 동명이인으로 두명이 있을 때는 list_complt 에 2로 들어간다. 참가자를 먼저 hash에 넣고 완주자의 이름을 key값으로 검색하면서 1씩 빼줬을 때, 완주자 명단에 없는 사람은 1이상의 value값을 가지고 있을 것이다.
hash는 1대1 대응이기 때문에 중복된 key-value가 들어갈 수 없다. 문제에서 동명이인이 있을 수 있다고 했다. 예를들어 “js”가 두명이 있을 때, hash에는 [“js”: 1, “js”: 1] 과 같이 들어가지 않고 [“js”: 1] 로 한번만 들어가게 된다.
python code
def solution(participant, completion):
answer = ''
dict_name = {}
# dictionary 모든 이름의 value를 0로
for name in participant:
dict_name[name] = 0
# 동명이인 검사 및 이름 개수 등록
for name in participant:
dict_name[name] += 1
# 완주자는 -1
for name in completion:
dict_name[name] -= 1
# 완주하지 못한 사람 출력
for item in dict_name.items():
if item[1] == 1:
answer = item[0]
return answer
전화번호 목록
https://programmers.co.kr/learn/courses/30/lessons/42577
문제
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.
제한사항
1. phone_book의 길이는 1 이상 1,000,000 이하입니다.
2. 각 전화번호의 길이는 1 이상 20 이하입니다.
예시
## phone_book, return
[119, 97674223, 1195524421] false
풀이
복잡도를 줄이기 위해서 한쪽 방향으로만 검색을 진행하자. string의 정렬을 이용하면 앞뒤의 관계만 검사하면 된다. sort는 접두사가 겹치는 순서로 정렬하므로 복잡하게 생각하지 않아도 된다. 예를들어 ["12", "5632", "56", "1268", "12891"] 을 오름차순으로 정리하면, ["12", "1268", "12891", "56", "5632"] 이므로 바로 뒤에 있는 문자열과 비교만 하면 된다. 비교할 때는 앞에 있는 문자열의 길이만큼 뒤에 있는 문자열을 자른 뒤에 같은지 확인하자. (substr 이용)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool solution(vector<string> phone_book) {
bool answer = true;
sort(phone_book.begin(), phone_book.end());
for(int i=0; i<phone_book.size()-1; i++){
if(phone_book[i] == phone_book[i+1].substr(0, phone_book[i].size())){
answer = false;
};
}
return answer;
}
python code
def solution(phone_book):
# str을 sort하면 접두사가 겹치는 것 순서로 정렬
phone_book = sorted(phone_book)
for i, number in enumerate(phone_book):
if i < len(phone_book) - 1:
# 현재 있는 번호가 뒤에 있는 번호의 접두사 일 때
if number == phone_book[i+1][:len(number)]:
answer = False
return answer
answer = True
return answer
위장
https://programmers.co.kr/learn/courses/30/lessons/42578
문제
스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.
예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.
종류 이름
얼굴 동그란 안경, 검정 선글라스
상의 파란색 티셔츠
하의 청바지
겉옷 긴 코트
스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.
제한사항
clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
같은 이름을 가진 의상은 존재하지 않습니다.
clothes의 모든 원소는 문자열로 이루어져 있습니다.
모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
스파이는 하루에 최소 한 개의 의상은 입습니다.
예시
## clothes, return
[[yellow_hat, headgear], [blue_sunglasses, eyewear], [green_turban, headgear]] 5
[[crow_mask, face], [blue_sunglasses, face], [smoky_makeup, face]] 3
풀이
항목을 정리하는 문제는 대부분 hash map으로 풀 수 있다. 먼저 경우의 수를 구하는 방법을 생각해보자. 하나는 착용하고 하나는 착용하지 않을 수 있으므로 착용하지 않음의 항목을 추가하는 것이 포인트이다. 모자 종류 2개, 안경 종류 1개인 경우, 경우의 수는 (2+1)*(1+1) = 6이다. 하지만 모두 착용하지 않는 경우의 수는 빼줘야하므로 마지막에 -1을 해준다. 이 계산을 하기 위해서는 항목별 옷의 개수를 세야한다.
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
int solution(vector<vector<string>> clothes) {
// 각 항목별로 나열하고 "착용x"를 추가하면 경우의 수를 구할 수 있다. (항목 +1)
// 모두 착용x 인 경우는 건너뛰어야 한다. (마지막에 -1)
int answer = 1;
unordered_map <string, int> kind;
for(int i=0; i<clothes.size(); i++){
kind[clothes[i][1]]++;
}
// 경우의수 항목1 x 항목2 x 항목3 ... -1
for(auto pair: kind){
// cout << pair.first << endl;
answer *= (pair.second+1);
}
return answer-1;
}
베스트앨범
https://programmers.co.kr/learn/courses/30/lessons/42579#
문제
스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.
속한 노래가 많이 재생된 장르를 먼저 수록합니다.
장르 내에서 많이 재생된 노래를 먼저 수록합니다.
장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.
제한사항
genres[i]는 고유번호가 i인 노래의 장르입니다.
plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
장르 종류는 100개 미만입니다.
장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
모든 장르는 재생된 횟수가 다릅니다.
예시
## genres, plays, return
[classic, pop, classic, classic, pop] [500, 600, 150, 800, 2500] [4, 1, 3, 0]
풀이
이 문제 역시 항목별 value를 정리하는 것이 중요한 문제이기 때문에 hash map을 사용하면 된다. Mapping을 시켜준 이후에 정렬을 해줘야 하는데 sort 함수를 사용해야한다. 하지만 조건이 달려있다. 재생횟수가 높은 장르 순서대로 나열하는 것은 문제가 되지 않지만, 하나의 장르 안에서 재생횟수가 높은 곡 순서대로 나열해야하며, 재생 횟수가 같으면 index는 낮은 순서부터 나열해야한다. 이 문제를 해결하기 위해 sort 함수에 3번째 인자를 받는 함수를 작성해야한다. 3번째 인자에 들어가는 함수의 조건에 따라 sort 함수가 작동한다. 밑의 풀이에서 compare 함수 와 compare_index 함수에 이 기능을 구현해 놓았다.
compare 함수는 pair vector를 인자로 받아 첫번째 pair value를 단순히 내림차순으로 바꾼다.compare_index 함수는 pair vector를 인자로 받아 두번째 pair value를 내림차순으로 바꾸고, 만약 이 값이 같으면 첫번째 pair vlaue를 오름차순으로 바꾼다.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
bool compare(pair<int, string> a, pair<int, string> b){
return a.first > b.first;
}
bool compare_index(pair<int, int> a, pair<int, int> b){
if(a.second == b.second) return a.first < b.first;
return a.second > b.second;
}
vector<int> solution(vector<string> genres, vector<int> plays) {
vector<int> answer;
unordered_map <string, int> category;
vector < pair<int, string> > temp_list;
for(int i=0; i<genres.size(); i++){
category[genres[i]] += plays[i];
}
// 내림차순 정렬
for(auto pair: category){
temp_list.push_back(make_pair(pair.second, pair.first));
}
sort(temp_list.begin(), temp_list.end(), compare);
for(auto pair: temp_list){
cout << pair.second << pair.first << endl;
}
// 가장 큰 genres category부터 genres vector에서 조회를 시작하자
vector < pair <int, int> > playsIndex;
for(auto pair: temp_list){
// 장르 안에 수록된 곡들을 pair vector <index, plays>으로 만들자
// compare_index 함수로 pair.second(plays)는 내림차순, 같으면 pair.first(index)는 오름차순으로 만든다.
// 사실 pair.second가 같은 경우는 만들지 않아도 벡터에 넣을 때 자동으로 index가 낮은 값부터 들어간다.
for(int i=0; i<genres.size(); i++){
if(pair.second == genres[i]){
playsIndex.push_back(make_pair(i, plays[i]));
}
}
sort(playsIndex.begin(), playsIndex.end(), compare_index);
// 정답 vector에 집어넣자.
for(int i=0; i<playsIndex.size(); i++){
if(i == 2) break;
answer.push_back(playsIndex[i].first);
}
// for(auto pair: playsIndex){
// cout << pair.first << ": "<< pair.second << endl;
// }
playsIndex.clear();
}
return answer;
}