Computer Science & Engineering

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

이 문제는 큐를 브루트 포스로 풀었을 경우 O(n^2)의 시간 복잡도를 가지며 시간초과가 발생한다. 처음 이 풀이를 사용하지 않았을 때 테스트케이스 마지막 3개는 시간초과로 통과하지 못하였다. 그렇기 때문에 O(n)의 시간복잡도를 가지는 풀이를 사용해야했다. 문제를 보면 시간은 ms단위가 없기 때문에 정수형으로 시간을 바꾸었을 때 생각보다 큰 숫자가 나오지 않는다. 우선 카카오에서 자주 출제되는 시간을 문자열로 주어지는 문제는 가장 작은 단위로 통일하여 시간을 계산해주는 것이 좋다. 나는 toint()라는 함수를 만들어 string을 초 단위의 정수형으로 변환하는 함수를 만들어 사용하였다. 코드는 아래와 같다.

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

using namespace std;

int arr[360000];

int toint(string str) { //문자열 시간을 정수형으로 변환
    int h = stoi(str.substr(0, 2));
    int m = stoi(str.substr(3, 2));
    int s = stoi(str.substr(6, 2));
    int ret = s;
    ret += (m * 60);
    ret += (h * 3600);
    return ret;
}

string tostr(int time) { //정수형 시간을 문자열로 변환
    string ret = "";
    int h = time / 3600;
    time %= 3600;
    int m = time / 60;
    time %= 60;
    int s = time;
    if(h < 10) //1자리일 경우 0 추가
        ret += '0';
    ret += to_string(h);
    ret += ":";
    if(m < 10) //1자리일 경우 0 추가
        ret += '0';
    ret += to_string(m);
    ret += ":";
    if(s < 10) //1자리일 경우 0 추가
        ret += '0';
    ret += to_string(s);
    
    return ret;
}

string solution(string play_time, string adv_time, vector<string> logs) {
    string answer = "";
    int adv = toint(adv_time); //광고 시간 정수형으로 변환
    int play = toint(play_time); //재생 시간 정수형으로 변환
    long long mnum = 0; //최대값 저장
    long long sum = 0; //현재 누적시간
    int idx = 0; //최대값의 시작시간 저장
    for(string str : logs) {
        int s = toint(str.substr(0, 8)); //시작시간
        int e = toint(str.substr(9)); //종료시간
        for(int i = s; i < e; i++) arr[i]++; //log들이 재생한 구간 표시
    }
    
    for(int i = 0; i < adv; i++) { //00:00:00부터 광고 시간만큼 재생한 수 계산
        sum += arr[i];
    }
    
    mnum = sum;
    
    for(int i = adv; i < play; i++) { //1초씩 늘려가며 
        sum -= arr[i - adv]; //1초 전 시청인원 빼기
        sum += arr[i]; //다음 1초 시청인원 추가
        if(mnum < sum) { //최대인 경우
            idx = i - adv + 1; //최대값에서의 시작 시간 저장
            mnum = sum; //최대값 갱신
        }
    }
    
    answer = tostr(idx); //최대값에서의 시작시간을 string으로 변환
    
    return answer;
}

이 문제는 광고 재생 시간이 일정하게 유지된다. 따라서 00:00:00초부터 종료시간까지 광고 시간이 슬라이딩하며 그 시간에 시청한 사람들의 수를 계산할 수 있다. 예를 들면 광고 재생 시간이 10초인 경우

 0초~9초 -> 1초~10초 -> 2초~11초 -> ...

이런 식으로 처음 시작 시간에 시청한 인원을 빼고 그 다음 초에 시청한 인원을 더하며 슬라이딩 방식을 사용한다면 O(n)만에 모든 시간에서 최대 인원이 시청한 시간을 알 수 있다. 하나를 빼고 하나를 더할 때마다 최대값인지를 확인하며 최대값인 경우 그때의 광고 시작 시간을 저장한다. 시작 시간은 정수형이기 때문에 마지막에 그 최대값을 문자열로 변환하여 리턴해주면 된다.

카카오에서 이런 문자열을 다루는 문제가 자주 나오기 때문에 문자열을 다루는 라이브러리 함수 특히 substr, stoi 등을 익혀놓는 것이 문제를 풀 때 상당히 도움이 된다.

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

문제의 카테고리가 이분탐색인 것을 알지 못하고 문제를 본다면 이분탐색을 이용하여 문제를 풀어야 한다는 것을 알아차리기가 쉽지 않다. 며칠 전에 이분탐색 여러 문제를 풀어보았기 때문에 문제를 읽고 이분탐색을 사용하면 잘 될 것이라고 생각하여 문제 접근 방향을 그렇게 정하였다. 코드는 굉장히 짧다. 아래와 같다.

소스코드

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

using namespace std;

int solution(vector<int> stones, int k) {
    int answer = 0;
    int left = 0, right = *max_element(stones.begin(), stones.end()) + 1; //초기값 설정
    for(int i = 0; i < 30; i++) { //최대 200000000이므로 log2 200000000은 30보다 충분히 작으므로 가능하다.
        int mid = (left + right) / 2; //중간 값을 설정한다. mid명이 건넌다고 생각한다.
        int maxcnt = 0; //가장 많이 건너뛴 수를 저장
        int cnt = 1; //건너뛴 횟수를 그때그때 저장
        for(int i = 0; i < stones.size(); i++) { //징검다리를 하나씩 보며
            if(stones[i] < mid) cnt++; //mid번째 사람이 건널 경우 mid보다 작은 값이 있는 돌은 mid-1명만 건널 수 있으므로 건너뛰게 된다. 따라서 숫자를 센다.
            else { //만약 mid보다 크거나 같은 경우 mid번째 사람도 돌을 밟을 수 있으므로 한번에 건너뛰는 돌의 수는 1로 다시 초기화하고 현재 돌까지 한번에 건너뛴 돌의 수를 계산
                maxcnt = max(maxcnt, cnt); //한번에 건너뛴 돌의 최대값 갱신
                cnt = 1;
            }
        }
        maxcnt = max(maxcnt, cnt); //마지막 돌까지 건널때 cnt값이 갱신되지 않을 수 있으므로 한 번 더 체크
        if(maxcnt <= k) left = mid; //최대 k개 건너 뛸 수 있으므로 가장 많이 건너뛴 수가 k보다 작거나 같은 경우 더 많은 인원이 건널 수 있다고 판단
        else right = mid; //그렇지 않으면 더 적은 사람이 건너 뛸 수 있다고 판단
    }
    answer = left; //등호가 left에 있으므로 left값이 최종 결과
    return answer;
}

이분탐색을 할 때 결과값이 left냐 right냐를 아는 것은 꽤 어렵다. 이 문제는 최대값을 구해야하는 문제이므로 등호를 포함하는 값이 정답이 될 것이다. 글쓴이는 거의 left에 등호를 붙인다.

풀이에서 중요한 부분

    1. left는 초기값으로 0, right는 최대값보다 1 큰 값으로 설정하였다. 1을 더한 이유는 만약 left = 5, right = 6일 경우 mid값으로 갱신했을 경우 mid는 항상 5이므로 left는 6이 될 수 없다. 만약 정답이 6일 경우 오답이 나올 수 있다. 따라서 left는 최소값보다 작은 값, right는 최대값보다 큰 값으로 설정하는 것이 좋다.

    2. for문을 30번 돌았다. stone배열의 원소의 최대값은 200000000(2억)이다. 따라서 2억을 커버할 수 있는 30으로 설정하였다. log2의 200000000은 30보다 훨씬 작은 수이다. 2^30은 대락 10의 9제곱이기 때문이다. 2억을 넘을 수 있는 log값으로 더 작은 수로 설정하여도 충분히 돌아간다.

    3. left가 정답인 이유는 파라매트릭 문제를 여러번 풀어봐야한다. 이 문제에서는 건너뛴 바위의 수가 k보다 작거나 같은 조건에서 가장 큰 값이어야한다. 이때 for문의 가장 마지막에 if(maxcnt <= k) left = mid;라는 코드가 있다. 이 코드가 바로 이전 말과 같은 말이다. 건너뛴 바위의 수가 k보다 작거나 같을 때 left를 mid로 설정하라는 말이다. 더 큰 값이 있을 수 있기 때문이다. 만약 이 조건을 만족하지 않을 경우 right = mid 코드가 실행될 것이다. 따라서 left는 정답이 될 수 있는 조건을 만족하지 않은 상태에서 최대값으로 갱신되기 때문에 left가 최종 정답이 되는 것이다.

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

이 문제는 딱 보자마자 플로이드-와샬 알고리즘으로 쉽게 풀 수 있는 문제임을 직감했다. 모든 정점에서 다른 모든 정점으로의 최단 경로를 구한 다음 시작정점으로부터 한 지점을 거쳐서 각각 A, B의 집을 가는 경로의 최솟값을 구하면 된다. 코드는 다음과 같다.

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

using namespace std;

const int MN = 201;
const int INF = 1e9; //무한대

int floyd[MN][MN]; //최단 경로를 저장할 배열

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = INF;
    fill(&floyd[0][0], &floyd[n][n+1], INF); //최단 경로 무한대로 초기화
    for(int i = 1; i <= n; i++)
        floyd[i][i] = 0; //자기 자신은 0으로 초기화
    
    for(vector<int> e : fares) { //u->v와 v->u 모두 가능하므로 양방향으로 초기화
        floyd[e[0]][e[1]] = e[2];
        floyd[e[1]][e[0]] = e[2];
    }
    for(int k = 1; k <= n; k++) { //플로이드-와샬 알고리즘 수행 k정점을 통해 갔을 경우를 각각 계산
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                floyd[i][j] = min(floyd[i][j], floyd[i][k] + floyd[k][j]);
            }
        }
    }
    
    for(int k = 1; k <= n; k++) { //1번 정점부터 n번 정점까지 출발점부터 k를 지나 a, b로 각각 가는 합 계산
        int tmp = floyd[s][k] + floyd[k][a] + floyd[k][b];
        if(tmp < 0) continue; //오버플로우 방지
        answer = min(answer, tmp); //최솟값 갱신
    }
    
    return answer;
}

    초기화를 1e9인 10억으로 했기 때문에 만약 s->k, k->a, k->b 경로가 모두 없는 경우 30억으로 약 21억인 정수형 범위를 넘어가게 된다. 그렇기 때문에 오버플로우 방지로 계산한 결과 값이 0보다 큰 경우에만 최소값을 갱신해야한다. 그렇지 않으면 엄청나게 작은 수가 최소값으로 갱신될 것이다.

    플로이드-와샬 알고리즘을 수행하는 부분은 가운데에 있는 3중 반복문이다. k정점을 지나는 경우를 계속 최단 경로로 갱신하여 모든 정점에서 다른 모든 정점으로의 최단 경로를 구할 수 있다. 한 정점에서 다른 모든 정점으로의 최단 경로를 구하는 다익스트라나 벨만-포드 알고리즘은 O(n^2)의 알고리즘이 가능하지만 모든 정점에서의 최단 경로를 모두 구하는 플로이드-와샬 알고리즘은 O(n^3)의 알고리즘이 최선이다. 문제의 조건에 따라 다익스트라를 사용할지 플로이드-와샬 알고리즘을 사용할지 잘 판단해야한다.

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

이 문제는 조건을 차근차근 맞춰나가면 충분히 풀 수 있는 문제이다. 핵심은 버스의 수, 버스 1대당 탈 수 있는 인원의 수를 생각해야한다는 점이다. 시간관련 문제를 풀 때 모든 시간을 가장 작은 단위로 통일하는 것이 굉장히 편하다. 이 문제에서는 가장 작은 단위가 분이므로 모든 시간을 몇분인지 계산하면 쉽게 구할 수 있다. 특히 소수점이 나오는 시간문제는 부동 소수점으로 계산할 경우 계산 과정에서 원하는 값이 나오지 않을 수 있으므로 integer형으로 계산하는 것이 가장 좋다. 코드는 다음과 같다.

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

using namespace std;

bool cmp(string a, string b) { //내림차순 정렬
    return a > b;
}

int part(string a) { //string을 시간으로 변경
    pair<int,int> hm;
    hm.first = stoi(a.substr(0, 2)); //hour 분리
    hm.second = stoi(a.substr(3, 2)); //minute 분리
    int ret = hm.first * 60; //분으로 합치기
    ret += hm.second;
    return ret;
}

string timetostring(int time) { //시간을 string으로 변경
    string ret = "";
    int h = time / 60; //hour 분리
    int m = time % 60; //minute 분리
    if(h < 10) //1자리 수인 경우 앞에 '0' 붙이기
        ret += '0';
    ret += to_string(h);
    ret += ':';
    if(m < 10) //1자리 수인 경우 앞에 '0' 붙이기
        ret += '0';
    ret += to_string(m);
    return ret;
}

string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    sort(timetable.begin(), timetable.end(), cmp); //내림차순으로 정렬
    int now = 540; //9시 정각
    int end = now + (t * (n-1)); //버스 마지막 시간
    int cnt = 0; //마지막 버스 탑승자 카운트
    for(int i = 0; i < n; i++) { //n개의 버스
        if(i == n - 1) { //마지막 버스일 경우
            if(cnt == m - 1) break; //1자리 남은 경우 break
        }
        if(timetable.empty()) break; //모두 탄 경우 break
        for(int j = 0; j < m; j++) { //m개의 탑승자 수 만큼
            if(timetable.empty()) break; //모두 탄 경우 break
            int hm = part(timetable.back()); //가장 빨리온 사람 시간으로 변경
            if(hm <= now) { //현재 버스를 탈 수 있는 경우
                timetable.pop_back(); //버스에 탑승
                if(i == n - 1) { //마지막 버스인 경우
                    cnt++; //탑승자 수 증가
                    if(cnt == m-1) break; //마지막 버스 1자리 남은 경우 break
                }
            }
            else { //가장 빨리온사람도 현재 버스를 탈 수 없는 경우 break
                break;
            }
        }
        now += t; //다음 버스
    }
    if(timetable.empty()) { //모두 버스에 타고도 자리가 남은 경우
        answer = timetostring(end); //마지막 버스 탑승
    }
    else {
        int back = part(timetable.back()); //남은 탑승자 중에 가장 빠른 사람
        if(back > end) { //마지막 버스보다 뒤에 오는 경우
            answer = timetostring(end); //콘은 마지막 버스 탑승
        }
        else { //남은 탐승자 중에 가장 빠른 사람이 버스를 탈 수 있는 경우
            back--; //콘은 1분 일찍 도착해서 버스 탑승
            answer = timetostring(back);
        }
    }
    return answer;
}

이 문제에서 중요한 것은 마지막 버스이다. 마지막 버스에 자리가 있는지 없는지를 판단하는 것이다. 각 버스에 최대 m명을 태울 수 있으므로 버스가 오는 시간까지 기다리고 있는 사람은 버스에 태워 보낸다. m명이 모두 차지 않더라도 정류장에 도착한 사람이 없는 경우 버스는 출발한다. 마지막 버스가 도착했을 때 m-1명까지만 버스에 태운다. 마지막 1자리는 콘이 타야하기 때문이다. 그리고 프로그램 마지막에 판단한다. 이때 경우의 수가 3가지가 있다.

    1. 만약 정류장에 기다리는 사람이 없는 경우 콘은 마지막 버스가 출발하는 시간에 도착하면 된다.

    2. 만약 정류장에 사람이 기다리고 있지만 그 사람은 마지막 버스가 출발하는 시간보다 늦게 오는 경우 1번과 마찬가지로 마지막 버스의 시간과 같으면 된다.

    3. 마지막으로 남은 탑승자가 마지막 버스가 출발하는 시간보다 먼저 와서 기다리는 경우 그 사람보다 1분 먼저 도착하면 된다. 그렇다면 가장 높은 우선순위이기 때문에 마지막 1자리를 탈 수 있다.

이렇게 버스는 n개, 버스 하나 당 m명 탑승 가능이라는 조건을 하나하나 맞춰 나가고 마지막 1자리를 콘이 탈 수 있는 조건으로 위의 3가지 경우만 생각할 경우 문제를 쉽게 풀 수 있다. 이 문제의 핵심은 string으로 주어진 시간을 integer형으로 바꾸어 계산을 편하게 한 점과 조건을 하나하나 맞춰 경우의 수를 나누어 풀은 부분이라고 생각한다.

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

이 문제는 읽어보면 아주 간단한 문제이다. 문제를 읽고 DFS방식으로 풀면 금방 풀릴 것이라는 생각이 바로 들 것이다. 다단계에서 판매하는 칫솔의 수익의 10퍼센트를 자신을 추천한 사람에게 줄 때 사람들의 수익을 구하는 문제이다. 코드는 다음과 같다.

#include <string>
#include <vector>
#include <map>
using namespace std;

map<string,string> graph; //누구에게 추천받았는지를 저장
map<string, int> cost; //각 사람이 번 돈을 저장할 map

void dfs(string now, int amount) { //현재 사람이 번 돈
    string ref = graph[now]; //추천인이 누군지 찾음
    int nxt = amount / 10; //10퍼센트 떼서
    if(ref == "-") { //center를 만날 경우
        cost[now] += (amount - nxt); //자기 자신은 10퍼센트를 떼고 얻음
        return;
    }
    else { //추천인이 center가 아닌 경우
        int nxt = amount / 10; //10퍼센트를 떼서
        cost[now] += (amount - nxt);  //자기 자신은 나머지를 갖고
        if(nxt == 0) return; //만약 10퍼센트가 1원도 안나올 경우 dfs 멈춤
        dfs(ref, nxt); //추천인에게 줄 돈이 남은 경우 추천인의 추천인 계속 탐색
    }
}

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    vector<int> answer;
    for(int i = 0; i < enroll.size(); i++) { //모든 사람에 대하여
        graph[enroll[i]] = referral[i]; //자신을 추천한 사람 map으로 연결
    }
    
    for(int i = 0; i < seller.size(); i++) { //판매한 사람 모두 dfs로 추천인에게 10퍼센트씩 부여
        dfs(seller[i], amount[i] * 100); //칫솔 1개에 100원이므로 판매 수에 100을 곱한다
    }
    
    for(int i = 0; i < enroll.size(); i++) {
        if(cost.find(enroll[i]) == cost.end()) //만약 수익이 없는 사람을 발견할 경우
            answer.push_back(0); //0원 push_back
        else
            answer.push_back(cost[enroll[i]]); //map에 저장한 수익 push_back
    }

    return answer;
}

    DFS를 이용하여 자신의 추천인에게 10퍼센트를 계속 떼어 주는 것이다. 만약 현재 돈이 10원 미만이어서 10퍼센트를 떼었을 경우 1원도 나오지 않을 경우 DFS를 빠져나오게 된다. 저 조건을 뺄 경우 몇몇 테스트 케이스에서 시간초과가 발생한다. 불필요한 탐색을 거르는 장치인 것이다.

    그래프와 각 사람이 번 돈들을 map으로 표현하는 것이 핵심이었다. 다른 표현 방법으로 각 사람을 인덱스 번호로 표현하여 각각 사람의 인덱스를 가지고 있고 찾아봐야할텐데 map을 이용하여 그러한 시간을 줄이고 더 편하게 이름으로 사람을 찾을 수 있었다.

    문제의 설명이 길어 긴장했지만 읽어보니 굉장히 단순하게 풀 수 있는 방법이었다. DFS 재귀 방식 말고도 while문을 이용하여 더 빠른 시간에 풀 수 있는 방법도 있으니 그 방법도 생각해보면 좋을 것 같다.

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

이 문제는 문제 자체를 이해하는데도 굉장히 오래걸렸다. 다리의 길이와 다리에 올라갈 수 있는 트럭의 수를 같은 숫자를 쓰기 때문에도 헷갈렸고 다리를 트럭이 지나는데 다리의 길이만큼 시간이 필요하다는 것도 문제에 적혀져 있지 않아서 너무 아쉬운 문제였다. 이 문제는 쉽게 생각해 다리 길이만큼의 큐를 만들고 while문을 돌면서 트럭이 큐에 들어가게 만드는 것이 가장 쉬운 방법이었다. 코드는 다음과 같다.

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int on_weight = 0;
    int i = 0;
    queue<int> q; //다리를 나타낼 큐
    for(int i = 0; i < bridge_length; i++) { //다리의 길이만큼 큐에 0을 채움
        q.push(0);
    }
    while(i < truck_weights.size()) { //다리에 트럭이 모두 올라갈 때까지
        if(q.front() != 0) { //다리를 빠져나가는 트럭의 무게를 뺌
            on_weight -= q.front();
        }
        q.pop(); //다리에서 트럭 pop
        answer++; //시간 경과
        if(on_weight + truck_weights[i] <= weight) { //다리에 다음 트럭을 올려도 무게가 넘지 않을 경우
            on_weight += truck_weights[i]; //무게 추가
            q.push(truck_weights[i]); //트럭 다리에 추가
            i++; //다음 트럭
        }
        else { //그렇지 않으면 트럭 추가하지 않고 0 추가
            q.push(0);
        }
    }
    return answer+bridge_length; //마지막 트럭이 다리를 지나는 시간인 다리 길이를 더하여 리턴
}

위의 코드를 보면 다리에 다음 트럭을 올리고자할 때 무게를 넘지 않는지 체크한다. 만약 무게가 넘어갈 경우 트럭을 올리지 않고 다리의 길이를 유지할 0을 큐에 push한다. 마지막에 리턴하기 전에 bridge_length를 더하는 이유는 마지막 트럭이 다리를 모두 지나는데 bridge_length 시간만큼 들기 때문에 더해야한다.

큐를 이용해 다리에서 트럭들이 while문을 돌면서 앞으로 하나씩 이동하는 것을 표현하는 것이 핵심이었고 while문을 돌 때마다 시간이 경과하여 시간초과가 날 것이라고 생각했는데 다행히 효용성을 테스트하는 케이스는 없어서 통과할 수 있었다. 실제 구현은 간단했지만 문제 난이도는 3단계로 느껴질정도로 문제를 이해하는 것도 어려웠다. 효용성 테스트가 없어서 2단계 문제인 것 같다.

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

이 문제는 프로그래머스의 코딩테스트 연습 - 해시 - 베스트앨범이라는 문제이다.

위 링크를 타고 문제를 읽어보면 생각보다 단순하지 않게 느껴질 것이다.

우선 아래는 직접 풀은 코드이다.

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

using namespace std;

bool cmp(pair<int,int> a, pair<int,int> b) { //map에 있는 vector 정렬
    return a.second > b.second;
}

bool cmp2(pair<string,int> a, pair<string,int> b) { //vector정렬
    return a.second > b.second;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map<string,vector<pair<int,int>>> m;
    vector<pair<string,int>> v;
    for(int i = 0; i < genres.size(); i++) {
        if(m.find(genres[i]) == m.end()) { //처음 보는 장르인 경우
            vector<pair<int,int>> tmp; //벡터를 생성하여 번호와 재생 수를 저장
            tmp.push_back({i, plays[i]});
            m.insert({genres[i], tmp});
            v.push_back({genres[i], plays[i]}); //벡터에 추가
        }
        else { //이미 있는 장르인 경우
            m[genres[i]].push_back({i, plays[i]}); //map에 번호와 재생 수를 추가
            for(int j = 0; j < v.size(); j++) { //vector에서 같은 장르를 찾음
                if(genres[i] == v[j].first) {
                    v[j].second += plays[i]; //장르의 전체 재생 수 추가
                    break;
                }
            }
        }
    }
    sort(v.begin(), v.end(), cmp2); //장르별 전체 재생 수 정렬
    for(auto it = m.begin(); it != m.end(); it++) { //같은 장르의 각각 재생 수 정렬
        sort((*it).second.begin(),(*it).second.end(), cmp);
    }
    for(auto it = v.begin(); it != v.end(); it++) { //장르별 재생 수가 많은 순서대로 
        answer.push_back(m[(*it).first][0].first); //첫 번째 많은 재생 수 추가
        if(m[(*it).first].size() > 1) { //만약 재생 수가 2개 이상인 경우 추가
            answer.push_back(m[(*it).first][1].first);
        }
    }
    
    
    
    return answer;
}

이 문제는 map과 vector를 이용하여 풀었다.

우선 이 문제에서는 장르별 전체 곡 수를 저장할 vector와 각 장르에서의 곡 번호와 재생 수를 저장할 map을 선언하였다.

map에는 첫 번째 인자로 string을 주어 장르 이름을 통해 접근할 수 있게하고 두 번째 인자로 vector<pair<int,int>>를 주어 곡 번호와 재생 수를 저장할 수 있게한다.

주어진 입력을 모두 돌며 map과 vector에 저장한 다음 sort함수를 이용해 장르별 재생 수와 각 장르에서의 곡별 재생수를 내림차순으로 정렬한다.

그 다음 정렬된 vector를 처음부터 돌며 가장 많은 곡을 순서대로 answer에 넣는다. 이때 한 장르의 전체 곡 수가 1개일 수 있으므로 if문을 이용해 장르의 곡 수가 2개 이상인지 확인하고 추가한다.

이 문제를 풀며 코드도 깔끔하게 작성하지 못하였고 풀이 방식도 간결하지 못하다고 느꼈지만 효용성을 채점하는 부분이 없고 정확성 채점만 존재했기 때문에 vector, map을 모두 이용하여 푸는 방법 밖에 떠올리지 못했다.

이 문제에서 중요했던 스킬은 iterator를 사용하는 것과 vmap에서 type으로 또 다른 vector를 넣어 이를 이용하는 방식이 관건이었다. 직접 작성하면서도 헷갈리는 부분이 굉장히 많았고 풀이는 처음에 맞았지만 i와 j를 잘 못 쓰는 바람에 시간이 조금 더 걸렸었다. c++을 활용한 코딩테스트 문제를 풀 때 vector는 기본이고 set과 map을 활용해야하는 문제가 굉장히 많다고 느끼기 때문에 c++의 STL을 잘 활용할 수 있는 공부가 필요하다고 생각한다. 문제를 풀고 다른 사람들의 풀이를 보고 더 짧은 코드는 어떻게 돌아가는지 이해하는 것도 중요한 것 같다.

programmers.co.kr/learn/courses/30/lessons/64064#

처음 문제를 잘 이해하지 못하여 접근방법을 잘못 알았고 아래에 첨부한 풀이도 비효율적이지만 오랜 시간을 들여 풀었기 때문에 그대로 첨부하였다.

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int answer;
bool visit[9];
set<string> rst;
void dfs(int n, vector<string> &user_id, vector<string> &banned_id, string s) {
    if(n == banned_id.size()) {
        sort(s.begin(), s.end());
        rst.insert(s);
        return;
    }
    string now = banned_id[n];
    for(int i = 0; i < user_id.size(); i++) {
        if(visit[i] || now.size() != user_id[i].size()) continue;
        int chk = 0;
        for(int j = 0; j < now.size(); j++) {
            if(now[j] == '*') continue;
            if(user_id[i][j] != now[j]) {
                chk = 1;
                break;
            }
        }
        if(!chk) {
            visit[i] = 1;
            dfs(n+1, user_id, banned_id, s + to_string(i));
            visit[i] = 0;
        }
    }
    return;
}

int solution(vector<string> user_id, vector<string> banned_id) {
    dfs(0, user_id, banned_id, "");
    answer = rst.size();
    return answer;
}

처음에는 그래프를 그려 2-sat으로 이분매칭을 이용하여 풀려고 했으나 뜻대로 되지 않아 백트래킹을 이용하여 풀었다. 

ban사용자를 하나씩 선택하여 방문하지 않은 user중 일치하는 것이 있는지 확인한 후 재귀적으로 반복한다. dfs함수의 맨 마지막 인자인 string은 지금까지 일치된 사용자의 인덱스 번호이다. 사용자를 모두 찾은 경우 string s를 정렬하여 set에 집어 넣는다. 이 과정은 중복이 일어나지 않게 하기 위해서이다. 모든 과정을 끝낸 후 set의 사이즈를 리턴하면 된다.