개발일지

문제

https://school.programmers.co.kr/learn/courses/30/lessons/142085

내가 쓴 풀이

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

using namespace std;

int solution(int n, int k, vector<int> enemy) {
	priority_queue<int> pq;
	pq.empty();

	for (int i = 0; i < enemy.size(); i++)
	{
		pq.push(enemy[i]);
		n -= enemy[i];
		if (n < 0)
		{
			if (k-- <= 0) { return i; }
			n += pq.top();
			pq.pop();
		}
	}
	return enemy.size();
}

참고자료

(우선순위큐)

https://jungeu1509.github.io/algorithm/use-priorityqueue/

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12946

내가 푼 코드

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> answer;
void Hanoi(int src, int use, int dest, int n)
{
	if (n <= 0)return;
	Hanoi(src, dest, use, n - 1);
	vector<int> move{ src,dest };
	answer.push_back(move);
	Hanoi(use, src, dest, n - 1);
}
vector<vector<int>> solution(int n) {
	answer.clear();
	Hanoi(1, 2, 3, n);
	return answer;
}

참고 자료

https://ehpub.co.kr/6-1-%ed%95%98%eb%85%b8%ec%9d%b4-%ed%83%80%ec%9b%8c/

문제

https://school.programmers.co.kr/learn/courses/30/lessons/72411

나의 풀이

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

using namespace std;

void Combination(string arr, vector<char> comb, int r, int index, int depth, vector<string>* con)
{
    if (r == 0)
    {
        string temp;
        for (int i = 0; i < comb.size(); i++)
            temp.push_back(comb[i]);
        con->push_back(temp);
    }
    else if (depth == arr.size())
    {
        return;
    }
    else
    {
        comb[index] = arr[depth];
        Combination(arr, comb, r - 1, index + 1, depth + 1, con);
        Combination(arr, comb, r, index, depth + 1, con);
    }
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;

    //오름차순으로 만들기
    for (int i = 0; i < orders.size(); i++) 
        sort(orders[i].begin(), orders[i].end());

    for (int j = 0; j < course.size(); j++)
    {
        //course 갯수만큼 메뉴 담기
        vector<vector<string>> con;
        for (int k = 0; k < orders.size(); k++)
        {
            vector<string> m_con;
            vector<char> comb(course[j]);
            Combination(orders[k], comb, course[j], 0, 0, &m_con);
            con.push_back(m_con);
        }

        //곂치는 코스 체크
        vector<string> vec_temp;
            int max_cnt = 0;
        for (int a = 0; a< con.size() - 1; a++)
        {
            for (int b = 0; b < con[a].size(); b++)
            {
                bool chk = false;
                string temp = con[a][b];
                int cnt = 1;
                if (temp == "") continue;
                con[a][b].clear();
                for (int c = a + 1; c < con.size(); c++)
                {
                    for (int d = 0; d < con[c].size(); d++)
                    {
                        if (temp == con[c][d])
                        {
                            cnt++;
                            chk = true;
                            con[c][d].clear();
                        }
                    }
                }
                if(!chk) continue;
                if (cnt < max_cnt)continue;

                if (cnt > max_cnt)
                {
                    vec_temp.clear();
                    max_cnt = cnt;
                }
                vec_temp.push_back(temp);
            }
        }
        vector<string>::iterator it = answer.insert(answer.end(), vec_temp.begin(), vec_temp.end());
    }
    sort(answer.begin(), answer.end());
    return answer;
}

다른사람 풀이(추천수 높음)

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

using namespace std;
map<string,int> combi;

void combination(string src, string crs, int depth) {
    if (crs.size() == depth) combi[crs]++;

    else for (int i = 0; i < src.size(); i++)
        combination(src.substr(i+1), crs+src[i], depth);
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;

    for (string &order : orders)
        sort(order.begin(), order.end());

    for (int crs : course) {
        for (string order : orders)
            combination(order, "", crs);

        int sup = 0;
        for (auto it : combi)
            sup = max(sup, it.second);
        for (auto it : combi)
            if (sup >= 2 && it.second == sup)
                answer.push_back(it.first);
        combi.clear();
    }

    sort(answer.begin(), answer.end());
    return answer;
}

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42587

나의 풀이

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

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    int num = priorities[location];

    vector<int> m_priorities = priorities;
    sort(m_priorities.rbegin(), m_priorities.rend());

    int m_rank = 0;
    for (; m_rank < m_priorities.size(); m_rank++)
    {
        if (m_priorities[m_rank] == num) break;
    }

    int cnt = 0;
    for (int i = 0; i < m_rank; i++)
    {
        while (true)
        {
            if (m_priorities[i] == priorities[cnt])
            {
                priorities[cnt] = 0;
                answer++;
                break;
            }
            cnt++;
            cnt %= priorities.size();
        }
    }

    for (int j = 0; j < priorities.size(); j++, cnt++)
    {
        cnt %= priorities.size();
        if (priorities[cnt] == num)
        {
            priorities[cnt] = 0;
            answer++;
            if(cnt == location) break;
        }
    }
    return answer;
}

베스트 추천 풀이

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

using namespace std;

int solution(vector<int> priorities, int location) {
    queue<int> printer;                         //queue에 index 삽입.
    vector<int> sorted;                         //정렬된 결과 저장용
    for(int i=0; i<priorities.size(); i++) {
        printer.push(i);
    }
    while(!printer.empty()) {
        int now_index = printer.front();
        printer.pop();
        if(priorities[now_index] != *max_element(priorities.begin(),priorities.end())) {
            //아닌경우 push
            printer.push(now_index);
        } else {
            //맞는경우
            sorted.push_back(now_index);
            priorities[now_index] = 0;
        }
    }
    for(int i=0; i<sorted.size(); i++) {
        if(sorted[i] == location) return i+1;
    }
}

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42747

나의 풀이

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

using namespace std;

int solution(vector<int> citations) {
	sort(citations.rbegin(), citations.rend());
	for (int i = citations.size(); i >0; i--)	
		if (citations[i - 1] >= i) return i;	
	return 0;
}

문제

https://school.programmers.co.kr/learn/courses/30/lessons/64065

내가 짠 코드

급하게 만들다보니 개판..

#include <string>
#include <vector>

using namespace std;

vector<int> solution(string s) {
    vector<int> answer;

    vector <vector<int>> con;
    vector<int> ss;
    int temp = 0;
    for (int i = 1; i < s.size() -1; i++)
    {
        if (s[i] >= '0' && s[i] <= '9')
        {
            temp *= 10;
            temp += s[i] - '0';
            continue;
        }
        if (s[i] == ',' && s[i-1]!='}')
        {
            ss.push_back(temp);
            temp = 0;
            continue;
        }
        if (s[i] == '}')
        {
            ss.push_back(temp);
            temp = 0;
            con.push_back(ss);
            ss.clear();
            continue;
        }
    }
    //answer.resize(con.size());
    for (int i = 1; i <= con.size(); i++)
    {
        for (int j = 0; j < con.size(); j++)
        {
            if (i == con[j].size())
            {
                for (int l = 0; l < i; l++)
                {
                    bool check = true;
                    for (int k = 0; k < answer.size(); k++)
                    {
                        if (answer[k] == con[j][l]) check = false;
                    }
                    if (check)
                    {
                        answer.push_back(con[j][l]);
                        break;
                    }
                }
            }
        }
    }

    return answer;
}

문제

https://school.programmers.co.kr/learn/courses/30/lessons/17680

내가 푼 풀이

#include <string>
#include <vector>

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    if (cacheSize == 0) return cities.size() * 5;
    vector<string> cache;

    for (int i = 0; i < cities.size(); i++)
    {
        for (int k = 0; k < cities[i].size(); k++) cities[i][k] = tolower(cities[i][k]);

        bool Is_hit = false;
        for (int j = 0; (j < cache.size() && j < cacheSize); j++)
        {
            if (cache[j] == cities[i])
            {
                cache.erase(cache.begin() + j);
                cache.push_back( cities[i]);
                Is_hit = true;
                break;
            }
        }

        if (Is_hit) answer++;
        else
        {
            answer += 5;        
            if (cache.size() == cacheSize)cache.erase(cache.begin());
            cache.push_back(cities[i]);
        }       
    }
    return answer;
}

문제

https://school.programmers.co.kr/learn/courses/30/lessons/84512

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

using namespace std;

char spell[5] = { 'A','E','I','O','U' };
char arr[5];
vector<string> dir;
void Permutation(int depth,int n, int r) {
    if (depth == r) {
        string s = "";
        for (int j = 0; j < r; j++)
            s.push_back(arr[j]);
        dir.push_back(s);
        return;
    }

    for (int i = 0; i < n; i++) {
        arr[depth] = spell[i];
        Permutation(depth + 1, n, r);
    }
}


int solution(string word) {

    for (int i = 0; i <= 5; i++)    
        Permutation(0, 5, i);
    
    sort(dir.begin(), dir.end());

    for (int j = 0; j < dir.size(); j++)    
        if (dir[j] == word) return j;
    

    return -1;
}

문제

https://school.programmers.co.kr/learn/courses/30/lessons/17677

내가 푼 답

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

void make_vec(vector<string>& vec, string str)
{
	for (int i = 0; i < str.size(); i++)
	{
		string temp;
		if (str[i] >= 'A' && str[i] <= 'Z') str[i] += 'a' - 'A';
		if (str[i+1] >= 'A' && str[i+1] <= 'Z') str[i+1] += 'a' - 'A';
		if (str[i] >= 'a' && str[i] <= 'z' && str[i + 1] >= 'a' && str[i + 1] <= 'z')
		{
			temp.push_back(str[i]);
			temp.push_back(str[i+1]);
			vec.push_back(temp);
		}
	}
}

int solution(string str1, string str2) {
	int answer = 0;
	vector<string> s1, s2;
	make_vec(s1, str1);
	make_vec(s2, str2);
	int tot_size = s1.size() + s2.size();
	int inter_cnt = 0;
	for (int i = 0; i < s1.size(); i++)
	{
		for (int j = 0; j < s2.size(); j++)
		{
			if (s1[i] == s2[j])
			{
				inter_cnt++;
				s2.erase(s2.begin() + j);
				break;
			}
		}
	}
	if (s1.size() == 0 && s2.size() == 0) return 65536;
	answer = inter_cnt * 65536 / (tot_size - inter_cnt);

	return answer;
}

다른사람의 답

#include <bits/stdc++.h>
using namespace std;
short a, b, C[676], D[676];
int solution(string A, string B) {
    for(int i=1; i<A.size(); i++)
        if(isalpha(A[i-1]) && isalpha(A[i]))
            C[(A[i-1]&31)*26+(A[i]&31)]++;
    for(int i=1; i<B.size(); i++)
        if(isalpha(B[i-1]) && isalpha(B[i]))
            D[(B[i-1]&31)*26+(B[i]&31)]++;
    for(int i=0; i<676; i++) a+=min(C[i], D[i]), b+=max(C[i], D[i]);
    return b ? a*65536/b : 65536;
}

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12911

내가 쓴 코드

#include <string>
#include <vector>

using namespace std;

int binary_one_count(int n)
{
    int cnt = 0;
    while (true)
    {
        if (n % 2 == 1) cnt++;
        n /= 2;
        if (n / 2 < 1)
        {
            cnt++;
            break;
        }
    }
    return cnt;
}

int solution(int n) {
    int answer = n;
    int n_cnt = binary_one_count(n);

    while (n_cnt != binary_one_count(++answer));

    return answer;
}

다른 사람 코드

비트셋 머지...?

#include <bitset>

using namespace std;

int solution(int n) {
    int num = bitset<20>(n).count();

    while (bitset<20>(++n).count() != num);
    return n;
}