2022 카카오 블라인드 채용 - 프로그래머스

https://school.programmers.co.kr/learn/challenges?order=recent&partIds=25448 

코딩테스트 연습 | 프로그래머스 스쿨

1. 신고 결과 받기

• 특징: set, map
• 구현방법 (예시는 문제의 1번 예시)
  • 유저 ID 당 index를 부여해주었다. (map<string, int> m이용) 
    • m[muzi]  = 0, m[frodo] = 1, m[apeach] = 2, m[neo] = 3
  • set<string> s[1002]를 선언하였다. (s[유저 ID 당 index] 별 set으로, 각 배열의 set은 해당 유저를 신고한 유저들의 이름을 저장)
    • set[0(muzi)] = {apeach}
    • set[1(frodo)] = {muzi, apeach}
    • set[2(apeach)] = {}
    • set[3(neo)] = {muzi, frodo}
  • report를 순회하면서, set형 배열을 채운다. 
  • 유저 ID당 유효한 신고 횟수를 저장하는 ans배열을 선언하였다. 
  • id_list(i)를 순회하면서, s[i]의 사이즈가 k 이상이면(i를 신고한 유저가 k 이상), s[i]의 set을 순회한다. 
    • s[i]의 set에는 i를 신고한 유저의 이름이 들어있는데, map에서 이에 대한 index값을 찾아서 ans[index]를 1증가시킨다. 
• 어려웠던 부분
  • "a가 b를 여러번 신고 해도, 한번만 신고한 것으로 간주한다 -> set으로 구현한다" 라고 생각을 했다. 처음에는 신고를 한 무지를 기준으로, s[무지] = {프로도, 네오} 로 set을 설정했다.( 무지가 프로도, 네오를 신고했다) 하지만 이렇게 set을 설정하면, k번이상 신고당한 유저를 찾기가 어려워졌다. 신고 당한 유저를 기준으로 s[프로도] = {무지}, s[네오] = {무지}, 이렇게 설정했다. 그러면, k번 이상 신고당한 유저를 찾기가 쉬워진다. 
  • 각 유저당 index값을 설정하기 위해 map을 이용했는데, 내가 map 사용에 익숙하지 않아 구현이 오래걸렸다.
• 찾아본 문법
  • 맵에서 키로 값 찾기.
    • map<string, int> m;
    • auto it = m.find("muzi"); int idx = it->second;
  • set 순회: for(auto e: s) cout << e << ' ';
  • map 순회: for(auto e: m) cout << e.first << ' ' << e.second; 
  • set에 값 넣을 때 insert!!!!!, push(x)
• 코드

#include <bits/stdc++.h>

using namespace std;

set<string> s[1002]; // 무지, 프로도, 어피치 네오
map<string, int> m; //muzi 0, frodo1 , apeach2, neo3
int ans[1002];
vector<string> split(string str)
{
    vector<string> ret;
    string tmp ="";
    for(int i = 0; i < str.size(); i++)
    {
        if(str[i] == ' ')
        {
            ret.push_back(tmp);
            tmp = "";
        }
        else
        {
            tmp += str[i];
        }
    }
    ret.push_back(tmp);
    return ret;
}

vector<int> solution(vector<string> id_list, vector<string> report, int k) {
    vector<int> answer;
    
    for(int i = 0; i < id_list.size(); i++)
    {
        m[id_list[i]] = i;
    }
    
    for(int i = 0; i < report.size(); i++)
    {
        vector<string> vec = split(report[i]); 
        
        string s1 = vec[0]; string s2 = vec[1];
        int idx = m[s2];
        s[idx].insert(s1);
    }
    
    
    for(int i = 0; i < id_list.size(); i++)
    {
        if(s[i].size() >= k) 
        {
            for(auto e : s[i])
            {
                int idx = m[e];
                ans[idx]++;
            }
        }
    }
    
    for(int i = 0; i < id_list.size(); i++)
    {
        answer.push_back(ans[i]);
    }
    
    return answer;
}

 

2. k진수에서 소수 개수 구하기

• 특징
  • k진수 구하는 알고리즘
  • 소수 구하는 알고리즘
• 구현 방법
  • n을 k진수로 바꾼다 -> k진수로 바꾼 결과를 string형 str 으로 저장
  • str을 0기준으로 분리하여, vector<int> vec에 저장
  • vec을 순회하며, vec[i]가 소수인지 판별하여 소수이면, answer++
• 어려웠던 부분
  • 처음에 아무 생각 없이 int형으로 구현했다가 segment 오류가 나서 문제 조건을 확인하고 long long으로 고쳤다. n이 100만인데, 이를 k진수로 고치면 값이 엄청 커질 수 있기 때문이다. 
• 찾아본 부분
  • 사실,,, 소수 구하는 알고리즘 O(n)밖에 몰라서 찾아봤다... 오늘 외우는 걸로
• 코드 

#include <bits/stdc++.h>

using namespace std;

vector<long long> split(string& str)
{
    string tmp = "";
    vector<long long> ret;
    for(long long i = 0; i < str.size(); i++)
    {
        if(str[i] == '0')
        {
            if(tmp.size() > 0)
            {
                ret.push_back(stoll(tmp));
                tmp = ""; 
            }
        }
        else
        {
            tmp += str[i];
        }
    }
    if(tmp.size() > 0) ret.push_back(stoll(tmp));
    return ret;
}
bool isPrime(long long _n) {
    if(_n == 1) return false;
	long long _k = (long long)sqrt(_n);
	for (long long i = 2; i <= _k; i++) {
		if (_n % i == 0) return false;
	}
	return true;
}

int solution(int n, int k) {
    int answer = 0;
    string str = "";
    
    while(n > 0)
    {
        str += to_string(n%k);
        n = n/k;
    }
    reverse(str.begin(), str.end());
    vector<long long> vec = split(str);
    for(int i = 0; i < vec.size(); i++)
    {
        long long cur = vec[i];
        if(isPrime(cur))
        {
            answer++;
        }
    }

    return answer;
}

 

3. 주차 요금 계산

• 특징
  • map
• 구현 방법
  • 쉬워서,,, 생략
• 코드

#include <bits/stdc++.h>

using namespace std;

map<int, int> m; //차량번호, 들어온시간
map<int, int> tot; // 차량번호, 누적시간
map<int, int> cnt; // 차량번호, 입/출차 횟수
map<int, int> ans; //차량번호, 가격

int com_m, com_c, cer_m, cer_c;
void split(string s)
{
    int sh = stoi(s.substr(0, 2));
    int sm = stoi(s.substr(3, 2));
    int num = stoi(s.substr(6, 4));
    string stat = s.substr(11);
    
    if(stat == "IN")
    {
        m[num] = sh * 60 + sm;
        cnt[num]++;
    }
    else // OUT
    {
        tot[num] += ( sh * 60 + sm - m[num] );
        cnt[num]++;
    }
}

vector<int> solution(vector<int> fees, vector<string> records) {
    vector<int> answer;
    
    com_m = fees[0]; com_c = fees[1]; cer_m = fees[2]; cer_c = fees[3];
    for(int i = 0; i < records.size(); i++)
    {
        split(records[i]);
    }
    
    for(auto e: cnt)
    {
        if(e.second % 2 == 1)
        {
            int tsh = 23;
            int tsm = 59;
            tot[e.first] += ( tsh * 60 + tsm - m[e.first] );
        }
    }
    
    for(auto e: tot)
    {
        if(e.second > com_m) 
        {
            int sum = e.second - com_m;
            int div = sum % cer_m;
            int minu = sum / cer_m;
            if(div > 0)
            {
                minu++;
            }
            ans[e.first] += com_c;
            ans[e.first] += (minu * cer_c);
        }   
        else
        {
            ans[e.first] += com_c;
        }
    }
    
    for(auto e : ans)
        answer.push_back(e.second);
    return answer;
}