완주하지 못한 선수
참가한 선수보다 완주한 선수가 단 한명 적으니까, 그 단 한명을 찾으라는 말 같다. 음 그리고 크기가 10만이라서 O(N)만에 찾는 편이 좋겠다. 또는 O(NlogN)
음 근데 방법을 모르겠다. 그냥 생각나는 방법은 정렬하고 앞에서부터 두 배열이 같은지 확인하다가 다른 놈이 정답 같다.
일단 해보겠다.
음 내 방식이 성공했다. 그런데 해쉬를 사용하는게 문제인데 나는 정렬을 사용했으니 다른 코드들도 좀 분석해 보겠다.
방법2
c++ unrodered_map 사용
나는 주로 map을 사용했는데 이게 왠지 더 편해보인다. 음 사실 둘이 연산, 문법 규칙은 동일한거 같다. 성능이 다른듯. 밑에서 보니 RBT(레드 블랙 트리?) 를 사용한게
map
, unordered_map은 해쉬 구조인듯 하다.
키로 string을 갖고 밸류로 int를 가질 수 있다. 키 밸류 테이블 만드는 셈
그리고 내가 많이 안써본 c++로 for( auto elem: participant), 즉 auto를 좀 써보자.
음 set 이랑 map, multi_map 차이가 아래 블로그에 이렇게 설명되어 있다.
map 컨테이너는 연관 컨테이너 중 자주 사용하는 컨테이너로 원소를 key 와 value의 쌍으로 저장한다.
set은 원소로 key 하나만을 저장하지만, map 은 원소로 key와 value의 쌍(pair 객체)를 저장한다.
set처럼 원소의 key는 컨테이너에 중복 저장될 수 없으며 중복 key를 저장해야 한다면 mulitmap을 사용해야 한다.
출처: https://hyeonstorage.tistory.com/329 [개발이 하고 싶어요]
map , unrodered_map 차이!!
기본 개념 map 은 기본적으로(대부분의 STL 컨테이너들이 그렇듯이) 레드블랙 트리(Red-Black Tree 이하 RB Tree) 기반으로 되어있습니다. 때문에 모든 데이터는 정렬되어 저장됩니다.
RB Tree는 검색속도가 빠른 Binary Search Tree(BST)에 Self-Balancing 기능을 추가한 것으로 AVL Tree 만큼 엄격하진 않지만
O(logN)을 보장하는 수준으로 Balancing 되어지는 특징을 갖고 있습니다.
이러한 특성 때문에 입력되는 키 값의 분포가 고르지 못할 경우 balancing(node rotation)에 대한 비용이 계속해서 들어가기 때문에
Insert / Delete 성능이 저하될 수 있습니다. (물론 최악의 경우에도 O(logN)의 성능은 보장됩니다)
unordered_map은 hash_table 기반의 hash container입니다.
hash_table을 통해 참조를 하기 때문에 각 node들을 정렬할 필요가 없습니다.
따라서 충분한 hash_table의 크기만 주어진다면 데이터 양이 많아지더라도 Search / Insert / Delete 성능을 꾸준하게 보장할 수 있습니다.
출처: https://gracefulprograming.tistory.com/3 [Peter의 우아한 프로그래밍]
개인적으로 차이를 잘 못느끼겠다. 아직 구분해서 사용하기 어렵다는 말;;
전화번호 목록
음 접두사를 확인하는 문제인데, 어떻게 하지 아니 부분적으로 존재하는지 어떻게 확인하는걸까..... 난 이게 전에 그 무슨 tri 자료구조인가? 아닐수도 그런걸로 부분 문자열 확인하는줄 ; 그런거 없나.. kmp?
그리고 폰북의 길이가 100만이라서 O(n)문제인데.
음 방법을 모르겠다. 문자열의 일부도 아니고 접두사만 확인하는건데 ㅋㅋ
방법이 한개 생각났다. 12345 이면 1,12,123,1234,12345 까지 다 맵에 넣는다 그리고 123을 확인할때 123이 맵에 있는지 확인해보고 없으면 1,12,123을 넣자!
오 통과했다. 한가지 틀렸던 점은 길이 긴 순으로 먼저 정렬해야한다.
2번째 풀이
sort(phoneBook.begin(), phoneBook.end());
이런식으로 소트하면 앞에 부분 비교하교 길이 긴쪽이 뒤로가는거 같다.
디폴트 compare 함수 작동원리를 모르니뭐..한글로 검색하니 잘안나옴 ㅋㅋ;
그리고 그냥 앞에께 바로 뒤에 있는지 확인하면 된다. 접두사라서if ( phoneBook[i] == phoneBook[i+1].substr(0, phoneBook[i].size()) ) { answer = false; break; }
이런식. 이런 방법을 종종 본거 같다. 앞에만 비교하는 경우 정렬해서 앞뒤로 비교;
음 내 방법보다 공간적으로나 시간적으로 훨씬 유익하다. 왜냐하면 자릿수 별로 바꾸면서 맵에 넣을 필요가 없으니까.
위장
음 이 문제는 의상의 수가 30개로 적은 편이다. 의상 종류를 키로하고 의상 이름을 발류로 해야되는거 같은데, 그런데 옷 종류를 키로하면 발류인 옷 이름이 여러개 있게 된다. 즉 옷 종류에 몇개의 옷이 있는지 갯수를 세야될거 같다. 같은 옷이름인데 옷 종류가 다르지는 않을거 같다. 옷 종류가 같고 옷 이름도 같은거 같지 않고.
auto가 매우 편리했다. 이거 헤더파일이 뭐지 해서 ,그냥 auto가 뭔지 잘 몰라서 검색해 보니, 생성될때 자료형을 바탕으로 자동으로 타입을 추론해 주는것이였다.
[auto 설명 ] https://xn--vj5b11biyw.kr/80
성공했다. 그런데 만약에 같은 한 옷이 옷 종류만 다르게 적용될 수 있으면 음 복잡할듯...
베스트 앨범
[https://programmers.co.kr/learn/courses/30/lessons/42579] 베스트 앨범
이게 가장 어려워 보인다. 레벨 3 ㅋㅋ
일단 장르별로 몇번 플레이 됬는지 세고 , 장르들 중에 플레이 총 횟수 많은 장르에서 플레이가 가장 많이 된 곡, 같다면 고유번호가 낮은 곡을 고르는 식으로 장르당 두곡씩 골라서 출력하면 된다.
음 곡별로 키를 장르로 발류를 해당곡 플레이수, 고유번호로 저장하면 될거 같다. 그런데 unordered_map에 키를 장르 발류를 플레이 총수로 했는데 여기서 어떻게 플레이수가 큰 것 부터 뽑아야 되는데 정렬이 가장 효율적인가? 우선순위큐는?....음 둘이 똑같은 시간 복잡도 일듯 음 map을 정렬하는 것이 필요해 보인다.
음 못풀고 있다. 결국 항목별로 발류가 가장 큰 값의 키값을 찾아야 한다.....이 간단한걸 못하겠다. 나중으로 미루자 고민해보게
아 그리고 map은 balanced tree이고 unordered_map이 해쉬라고 한다.
배스트 앨범 - 다시 도전
특정 장르의 곡들 중에서 플레이수가 많은것, 같을 경우 고유 번호가 작은 것을 순으로 위에서 두개 골라야 한다.
여기서 보통 문제랑 다른 점은 특정 장르의 곡중에서라는거 같다.
그래서 해쉬 테이블 리스트 형태로 해야 되는데, unordered_map을 사용해서 어떻게 그렇게 하는지 모르겠다.
일단 그냥 벡터를 리스트로 하고 구현해보자.
장르를 키로하고 발류를 0~100사이의 인덱스로 하는 unordered_map을 만들어 보자.
장르 - 장르별 인덱스는 매핑을 했는데, 장르별로 플레이 수를 저장하려면 pair를 써서 <장르,플레이수>로 벡터로 저장하고, 정렬하는 편이 좋을거 같다.
진짜 겨우 풀었다. 실전이였으면 못했을듯. 다시해서 1시간 걸린거니까.
방법은 map은 "장르 이름 - 장르별 인덱스(벡터에서 검색용)" 으로 사용하고, 즉 백터에서 인덱스 찾기 검색 도구, 또는 그냥 검색 도구일뿐.........(map을 적절히 사용하지 못한건가..... 삽입 검색 시간이 해쉬라 O(1)인 점을 고려하면 괜찬은거 같기도?)
정렬이 필요한 것은 벡터에서 처리했다...! 맵에서 정렬, 검색 둘다 할려해서 복잡해지고, 맵 문법도 잘 몰라서 실패 했었다.
장르별로 두개 또는 한개씩 꺼내야 된다는 점이 vetor[장르들] 처럼 벡터를 사용한게 유효했던거 같다.
마지막에 놓친 부분은, 장르별로 2개가 없으면 1개만 골라도 된다는 조항이랑, 플레이수가 같으면 낮은 인덱스를 고르는 정렬을 놓쳐서 틀렸었다.
#include <string>
#include <vector>
#include<unordered_map>
#include<utility>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
using ll = pair<string, int>;
unordered_map<string,int> genToIndex;
unordered_map<string,int> genToPlays;
vector<ll> genTotalPlays;
//plays,index of a song
vector<pair<int,int>> songs[101];
bool cmp ( ll a, ll b){
if(a.second > b.second)
{
return true;
}
else{
return false;
}
}
bool cmp2 ( pair<int,int> a, pair<int,int> b){
if(a.first > b.first)
{
return true;
}
else if(a.first < b.first){
return false;
}
else{
if( a.second < b.second){
return true;
}
else {
return false;
}
}
}
vector<int> solution(vector<string> genres, vector<int> plays) {
vector<int> answer;
int index =0;
for(int i=0;i<genres.size();i++){
if( genToIndex.find(genres[i]) == genToIndex.end()){
genToIndex.insert(ll(genres[i],index));
genToPlays.insert(ll(genres[i],plays[i]));
index++;
}
else{
genToPlays[genres[i]] += plays[i];
}
songs[genToIndex[genres[i]]].push_back(make_pair(plays[i],i));
}
for(auto elem : genToPlays){
//cout << elem.first;
genTotalPlays.push_back(ll(elem.first,genToPlays[elem.first]));
}
sort(genTotalPlays.begin(),genTotalPlays.end(),cmp);
for(auto elem : genTotalPlays){
sort(songs[genToIndex[elem.first]].begin(), songs[genToIndex[elem.first]].end(),cmp2);
answer.push_back( songs[genToIndex[elem.first]][0].second );
if( songs[genToIndex[elem.first]].size() >= 2)
answer.push_back( songs[genToIndex[elem.first]][1].second );
}
return answer;
}다른 사람 코드를 보니 "장르 이름 - 장르별 인덱스(벡터에서 검색용)" 을 매핑하는 맵이 없다. 그냥 키를 전부 "genre"로 하고 , 필요할때는 벡터로 옮겨서 정렬을 따로 해주는 방식으로 골라냈다. 자료구조상 이게 더 효율적이라고 생각된다.
'알고리즘 문제 풀기' 카테고리의 다른 글
| 백준 - 1725번 히스토그램,6549 히스토그램에서 가장 큰 직사각형 (0) | 2020.01.03 |
|---|---|
| 프로그래머스 - 카카오 2020 블라인드 테스트 (블록 이동하기, 문자열 압축) (0) | 2020.01.02 |
| 프로그래머스 - 스택/큐 : 프린터, 쇠막대기, 주식 가격 (0) | 2019.12.30 |
| 프로그래머스 - 스택 : 탑, 다리를 지나는 트럭, 기능개발 (0) | 2019.12.27 |
| 프로그래머스 - 카카오 2020 블라인드 테스트 (자물쇠와 열쇠, 가사 검색) (0) | 2019.12.27 |