Algorithm

[프로그래머스] 코딩테스트 고득점 Kit 해시 C++ (폰켓몬, 완주하지 못한 선수, 전화번호 목록, 의상, 베스트앨범)

유자바 2024. 10. 24. 23:43

1️⃣ 폰켓폰

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

 

코드

// 241023 16:20 시작
// 241023 16:30 끝

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

set <int> s;

int solution(vector<int> nums) {
    int answer = 0;
    
    for (int num: nums) s.insert(num);
    
    if (s.size() > (nums.size()/2)) answer = nums.size()/2;
    else answer = s.size();
    
    
    return answer;
}
  • 생각 흐름
    • 문제를 읽으면서 '오?! 조합 문제인가?!' 싶었지만 결국 출력값을 보니 조합을 사용하지 않고도 풀 수 있을 것 같았다.
  • 풀이
    • 중복 없이 데이터를 저장하는 자료구조를 사용해야겠다는 생각을 해 set에 nums 벡터에 있는 데이터를 저장했다.
    • iterator를 써서 요소 하나하나에 접근할 필요도 없이 그냥 size 메소드만으로 문제를 해결할 수 있었다.
      • if 중복 숫자의 개수 > N/2다면, N/2를 출력하고
      • else면, 중복 숫자 개수를 출력하도록 했다
      • bc) 모든 조합을 찾고 그 중 가장 많은 종류의 폰켓몬을 선택하는 방법을 출력해야 하므로 위 조건에 따라 출력하면 모든 케이스가 커버될 것이라 생각했다.
이 문제에서 중요한 것은 
1. 어떤 자료 구조를 사용할지 결정하기와
2. 문제 출력값을 빠르게 파악하기인 것 같다

 

💡 C++ STL set 기본 사용법
     - 헤더: #include <set> 
     - iterator (반복자)
        > begin(): 시작 iterator를 반환 - rbegin(): 마지막 부분을 시작점으로 지정
        > end(): 끝 iterator를 반환 - rend(): 시작 부분을 마지막점으로 지정
     - 추가
        > insert(요소): set에 요소 추가
     - 삭제
        > erase(요소): set에서 해당하는 요소 삭제
        > clear(): set의 모든 요소 삭제
     - 조회
        > find(요소): 요소에 해당하는 iterator 반환 
        > count(요소): 요소에 해당하는 개수를 반환
     - 기타
        > empty(): 비어있으면 true, 아니면 false
        > size(): set에 포함되어 있는 원소들의 수 반환
     - 특징
        > 중복 허용 x
        > 중복 허용하려면 multiset 사용하기
     - 사용 예시
        > set<int>::iterator it;  // set에 저장된 원소: 20 30 40
           for (it=s.begin(); it!=s.end(); ++it) cout <<< *it << " ";   //output: 20 30 40
        > if (s.find(n) != s.end()) cout << *s.find(n) << '\n';  //output: n

 

 

2️⃣ 완주하지 못한 선수

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

 

  • 생각 흐름
    • 동명이인이 존재할 수 있으니 중복을 허락하는 자료구조 사용해야 하니까 입력으로 주어진 벡터 그대로 써야겠다!
    • 입력으로 받은 두 배열 모두 sort하자!
    • for문을 사용해서 participant[i]와 completion[i]를 하나씩 비교하고, 없는 이름을 answer에 저장하자!

 

코드1 - 오답

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    
    sort(participant.begin(), participant.end());
    sort(completion.begin(), completion.end());
    
    for (int i=0;i<participant.size();i++){
        if (participant[i] != completion[i]) {
            answer = participant[i];
            break;
        }
    }
    
    return answer;
}

 

위와 같은 생각 흐름을 가지고 문제를 풀었는데 사실 풀면서 for문의 i 범위가 'completion.size()-1 == participant.size()' 제한 사항에 걸릴까봐 걱정했다. 뭐 그래도 제출해보고 틀리면 그때 completion.size() 기준으로 범위 바꾸면 되지~ 라는 생각으로 제출했으나 역시나 우려했던 상황이 딱 걸린 것 같다 그래서 바로 코드를 변경했다.

 

코드2 - 정답

// 241023 17:08 시작
// 241023 17:15 끝

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    
    sort(participant.begin(), participant.end());
    sort(completion.begin(), completion.end());
    
    for (int i=0;i<completion.size();i++){
        if (participant[i] != completion[i]) {
            answer = participant[i];
            break;
        }
    }
    
    if (answer == ""){
        answer = participant[participant.size()-1];
    }
    
    return answer;
}

 

for문의 i 범위를 completion 기준으로 바꾸고 for문을 통해 모두 탐색했음에도 만약 answer이 빈 문자열이라면 answer에 participant배열의 마지막 원소를 수동으로 넣어주었다. 이렇게 코드를 변경하니 모든 테스트 케이스를 통과할 수 있었다! 

 

이 문제에서 중요한 것은
1. 정렬 잘 이용하기?

 

 

3️⃣ 전화번호 목록

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

 

  • 생각 흐름
    • 벡터 정렬하고 이중 for문을 사용해서 전체 탐색을 해버릴까?!
    • 근데 나는 flag 변수 안좋아해서 다른 방법이 쓰고 싶다
    • start_with 같은 메소드를 사용하는게 좋을 것 같은데 나는 어떻게 쓰는지 몰라..
    • 내가 쓸 수 있는 substr를 사용해서 문자열을 잘라버린 다음에 pre와 now가 같은지 확인하면 되겠다!

 

코드1 - 오답

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool solution(vector<string> phone_book) {
    
    sort(phone_book.begin(), phone_book.end());
    
    string pre = phone_book[0];
    for (int i=1;i<phone_book.size();i++){
        string now = phone_book[i].substr(0,pre.size());
        if (pre == now) return false;
    }
    
    return true;
}

 

 

당연히 될 줄 알았는데..? 뭐지..? 싶었으나 다시 코드를 보니 pre를 갱신하지 않고 있었다...! 

 

 

코드2 - 정답

// 241023 19:00 시작
// 241023 19:14 끝

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool solution(vector<string> phone_book) {
    
    sort(phone_book.begin(), phone_book.end());
    
    string pre = phone_book[0];
    for (int i=1;i<phone_book.size();i++){
        string now = phone_book[i].substr(0,pre.size());
        if (pre == now) return false;
        pre = phone_book[i];
    }
    
    return true;
}

 

pre를 갱신해주니 해결되었다^&^

알고리즘은 매우 간단하다 이전 문자열의 길이만큼 현재 문자열을 substr을 사용해 자르고 두 문자열이 같으면 접두어 존재, 다르면 접두어 존재x

 

이 문제에서 가장 중요한 것은
1. 벡터 정렬하기
2. 접두어 존재를 어떻게 판별할지 정하기 - 저는 substr로 문자열 잘랐습니다. start_with와 같은 함수 사용해도 좋을 듯 합니다

 

 

4️⃣ 의상

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

 

  • 생각 흐름
    • map에 종류랑 그 수 저장해서 곱하면 되겠다

 

코드

// 241024 14:55 시작
// 241024 15:02 끝

#include <string>
#include <vector>
#include <map>

using namespace std;

map <string, int> m;

int solution(vector<vector<string>> clothes) {
    int answer = 1;
    
    for (auto cloth: clothes) m[cloth[1]]++;
    
    for (auto key: m) answer *= (key.second+1);
    
    return answer-1;
}

 

알고리즘은 간단하니까 알고리즘 대신 map 사용법을 정리해보려한다.

 

💡 C++ STL map 기본 사용법
     - 헤더: #include <map>
     - 특징
        > 중복 허용 x
        > first, second의 pair 객체로 저장되고, first는 key, second는 value이다.
        > 검색, 삽입, 삭제가 O(logn)의 시간복잡도를 가진다.
        > map은 내부에서 자동으로 key를 기준으로 오름차순 정렬을 함
           (내림차순 정렬하고 싶으면 map <int, int, greater> m; or 데이터에 - 붙이기)
     - 기본 형태: map <key, value> m;
     - 추가
        > m.insert({"c++",100});  // key가 중복되면 insert가 수행되지 않으므로 주의
        > m[key[i]]++;
     - 삭제
        > m.erase(m.begin()+2);  // 특정 위치의 요소 삭제
        > m.erase("c++");  // key값을 기준으로 요소 삭제
        > m.erase(m.begin(), m.end());  // 모든 요소 삭제
        > m.clear();  // 모든 요소 삭제
     - 조회
        > m.find("c++) != m.end()
        > iterator 사용해 begin()부터 end()까지 찾기

 

 

5️⃣ 베스트앨범

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

 

  • 생각 흐름
    • map에 {장르, 장르별 재생 횟수 합계} 저장하기
    • 장르, {재생 횟수, 고유 번호}를 저장하는 map 만들기 -> 재생횟수 기분으로 내림차순 정렬해야 하니까 {}는 vector로 저장하고 sort 사용하기

 

코드

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

map <string, int> m1;
map <string, vector<pair<int,int>>> m2;

bool compare1(pair<string,int> a, pair<string,int> b){
    return a.second > b.second;
}

bool compare2(pair<int,int> a, pair<int,int> b){
    if (a.first == b.first) return a.second < b.second;
    else return a.first > b.first;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    
    for (int i=0;i<genres.size();i++){
        m1[genres[i]] += plays[i];
        m2[genres[i]].push_back({plays[i], i});
    }
    
    vector <pair<string,int>> v1(m1.begin(), m1.end());
    sort(v1.begin(), v1.end(), compare1);
    
    for (auto& m:m2){
        sort(m.second.begin(), m.second.end(), compare2);
    }
    
    for (auto v:v1){
        for (int i=0;i<m2[v.first].size();i++){
            answer.push_back(m2[v.first][i].second);
            if (i) break;
        }
    }
    
    
    return answer;
}

 

 

문제 풀면서 겪었던 어려움이 있는데 정리를 해보겠다..

 1. vector<pair<string,int>> v1(m1.begin(), m1.end()); 를 통해 맵에 있는 벡터를 v1에 바로 저장할 수 있던 걸 까맣게 잊어버리고 있었다. 이거 꼭 기억하기⭐️

 2. map에 저장된 vector 정렬하기

    - m2.second.begin() 이렇게 쓸 수 있는 것도 잊어버린 나란 녀석..

    - 그리고 m2 sort할 때 auto&가 아닌 auto를 써서 auto에 복사된 값만 정렬하고 원본 데이터를 정렬하지 못했다. 이거 때문에 시간을 엄청 잡아먹었다. 꼭.. 기억할 것!!

 3. answer에 답을 푸시할 때 for문의 i 변수의 범위 때문에 테스트 케이스에서 엄청 틀렸다. i<2로 설정했는데 왜 틀린거지..? 아직 잘 모르겠다🧐