개발일지

문제

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

내가 푼코드(멀리뛰기랑 구조는 같음)

#include <string>
#include <vector>

using namespace std;

long long solution(int n) {
vector<long long> pd(100000);
    pd[0] = 0;  pd[1] = 1;

    for (int i = 2; i <= n; i++)
        pd[i] = (pd[i - 1] + pd[i - 2])% 1234567;
    return pd[n] ;
}

문제

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

피보나치로 푼 코드(정답) 완전간다...

#include <string>
#include <vector>

using namespace std;

long long solution(int n) {
vector<long long> pd(2000);
	pd[0] = 1;	pd[1] = 2;

	for (int i = 2; i < n; i++)
		pd[i] = (pd[i - 1] + pd[i - 2]) % 1234567;
	return pd[n-1];
}

조합으로 풀었을때 시간초과 코드

void Combination(int n, int r, int index, int depth, int& res)
{
	if (r == 0)
	{
		res++;
	}
	else if (depth == n)
	{
		return;
	}
	else
	{
		Combination(n, r - 1, index + 1, depth + 1,res);
		Combination(n, r, index, depth + 1,res);
	}
}


long long solution(int n) {
	long long answer = 0;

	int ndiv2 = n / 2;

	for (int i = 0; i <= ndiv2; i++)
	{
		int x = 0;
		Combination(n - i, i, 0, 0, x);
		answer += x;
	}
	return answer % 1234567;
}

#include <string>
#include <vector>

using namespace std;

int solution(int n, int k) {
	int answer = 0;

	//k진수 역으로 구하기
	string s;
	while (true)
	{
		s.push_back('0' + n%k);
		n /= k;
		if (n / k < 1) 
		{
			s.push_back('0' + n%k);
			break;
		}
	}

	//역으로 구한 k진수에 0사이에 있는 숫자 담기
	vector<long long> int_arr;
	bool check = false;
	int cnt = -1;
	for (int i = s.size() - 1; i >= 0; i--)
	{
		if (s[i] == '0')
		{
			check = false;
			continue;
		}

		if (!check)
		{
			check = true;
			cnt++;
			int_arr.push_back(0);
		}
		int_arr[cnt] *= 10;
		int_arr[cnt] += s[i] - '0';
	}

	//소수 갯수 구하기

	for (int i = 0; i < int_arr.size(); i++)
	{
		if(int_arr[i] <= 1) continue;
		bool check = true;
		for (long long j = 2 ; j*j <= int_arr[i]; j++)
		{
			if(int_arr[i] % j == 0) 
			{
				check = false;
				break;			
			}
		}
		if (check) answer++;
	}
    
	return answer;
}

문제

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

나의 풀이

문제

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

나의 풀이

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> solution(vector<vector<int>> arr1, vector<vector<int>> arr2) {
    vector<vector<int>> answer(arr1.size(), vector<int>(arr2[0].size(), 0));    
    for (int row = 0; row < answer.size(); row++)   
        for (int col = 0; col < answer[0].size(); col++)        
            for (int i = 0; i < arr1[0].size(); i++)            
                answer[row][col] += arr1[row][i] * arr2[i][col];        
    return answer;
}

문제

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

내코드 

#include <string>
#include <vector>

using namespace std;


bool m_function(int& re_cnt, int& zero_cnt, int& size)
{
    int m_size = 0;
    while (size != 1)
    {
        if (size % 2) m_size++;     
        else zero_cnt++;        
        size /= 2;
        if (size == 1) m_size++;
    }
    size = m_size;
    re_cnt++;
    if (size == 1) return false;
    return true;
}

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

    if (s.size() == 1) return answer;
    int one_size = 0;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == '0') answer[1]++;
        else one_size++;
    }
    answer[0]++;
    if (one_size == 1) return answer;
    while (m_function(answer[0], answer[1], one_size));

    return answer;
}

다른사람 풀이

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

vector<int> solution(string s) {
    int zeros{0}, num_transform{0}; vector<bool> bin;
    for_each(s.cbegin(),s.cend(),[&bin](const char c){bin.emplace_back(c=='1');});  //s를 이진수로 변환
    while(true){
        if(bin==vector<bool>{true}) break;
        int ones = count(bin.cbegin(),bin.cend(),true);    //1갯수를 셈
        zeros += bin.size()-ones;                          //0갯수를 셈
        bin.clear();
        while(ones>0){ bin.emplace_back(ones%2); ones/=2; }//1갯수를 2진수로 바꿈. 순서는 거꾸로지만 계산에는 영향없음
        ++num_transform;                                   //이진변환 횟수 기록
    }
    return {num_transform,zeros};
}

문제

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

내가 푼 답

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

using namespace std;

vector<int> solution(vector<string> id_list, vector<string> report, int k) {

    int id_size = id_list.size();

    vector<int> answer(id_size, 0);
    vector<bool> vote_check(id_size,false);
    vector<vector<bool>> vote(id_size, vote_check);
    vector<int> voted_cnt(id_size, 0);

    map<string, int> list;
    for (int i = 0; i < id_size; i++)
        list.insert(pair<string, int>{ id_list[i], i });        

    sort(report.begin(), report.end());
    report.erase(unique(report.begin(), report.end()), report.end());

    for (int i = 0; i < report.size(); i++)
    {
        string a, b;
        bool chk = true;
        for (int j = 0; j < report[i].size(); j++)
        {
            if (report[i][j] == ' ') { chk = false; continue; }
            if (chk)
                a.push_back(report[i][j]);
            else
                b.push_back(report[i][j]);
        }
        vote[list[a]][list[b]] = true;
        voted_cnt[list[b]]++;
    }

    for (int i = 0; i < id_size; i++)
    {
        if (voted_cnt[i] < k) continue;

        for (int j = 0; j < id_size; j++)
            if (vote[j][i]) answer[j]++;    
    }
    return answer;
}

다른사람 풀이

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

vector<int> solution(vector<string> id_list, vector<string> report, int k) {
    // 1.
    const int n = id_list.size();
    map<string, int> Conv;
    for (int i = 0; i < n; i++) Conv[id_list[i]] = i;

    // 2.
    vector<pair<int, int>> v;
    sort(report.begin(), report.end());
    report.erase(unique(report.begin(), report.end()), report.end());
    for (const auto& s : report) {
        stringstream in(s);
        string a, b; in >> a >> b;
        v.push_back({ Conv[a], Conv[b] });
    }

    // 3.
    vector<int> cnt(n), ret(n);
    for (const auto& [a, b] : v) cnt[b]++;
    for (const auto& [a, b] : v) if (cnt[b] >= k) ret[a]++;
    return ret;
}

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

#include <string>

using namespace std;

int solution(string dartResult) {

    int cnt = 0;
    int dart[3] = { 0, };

    for (int i = 0; i < dartResult.size(); i++)
    {
        if (dartResult[i] >= '0' && dartResult[i] <= '9')
        {
            if (dartResult[i] == '1' && dartResult[i + 1] == '0')
            {
                dart[cnt++] += 10; 
                i++;
            }
            else
                dart[cnt++] += dartResult[i] - '0';
        }

        if (dartResult[i] == 'S');
        if (dartResult[i] == 'D') dart[cnt - 1] = dart[cnt - 1] * dart[cnt - 1];
        if (dartResult[i] == 'T') dart[cnt - 1] = dart[cnt - 1] * dart[cnt - 1] * dart[cnt - 1];

        if (dartResult[i] == '*')
        {
            dart[cnt - 1] *= 2;
            if (cnt != 1) dart[cnt - 2] *= 2;           
        }
        if (dartResult[i] == '#')dart[cnt - 1] *= -1;
    }

    return dart[0] + dart[1] + dart[2];
}

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

int solution(int n) {
	int answer = 0;

	for (int i = 2; i <= n; i++)
	{
		bool check = true;
		for (int j = 2; j < i; j++)
			if (i % j == 0) check = false;		

		if (check) answer++;
	}
	return answer;
}

시간초과

문제 

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

나의 답

#include <iostream>
using namespace std;
void m_fx(int a, int b, int& answer)
{
    answer++;
    if (a % 2 == 1 && b - a == 1) return;
    m_fx((a+1)/2, (b+1)/2, answer);
}

int solution(int n, int a, int b)
{
    int answer = 0;
    if (a > b) { m_fx(b, a, answer); }
    else{   m_fx(a, b, answer); }
    return answer;
}

다른사람의 답

int solution(int n, int a, int b)
{
    int answer = 0;

    while (a != b) {
        a = (a + 1) >> 1;   // 2 1 1
        b = (b + 1) >> 1;   // 4 2 1
        ++answer;
    }

    return answer;
}

문제 

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

내가쓴 답

#include <string>
#include <vector>

using namespace std;

void DFS(vector<vector<int>>& arr, int& zero, int& one,int st_row, int st_col, size_t size)
{
	if (size == 1)
	{
		if (arr[st_row][st_col] == 0)
		{
			zero++;
			return;
		}
		else
		{
			one++;
			return;
		}
	}
	int sum = 0;
	for (int i = st_row; i < st_row + size ; i++)
	{
		for (int j = st_col; j < st_col + size ; j++)
		{
			sum += arr[i][j];
		}
	}

	if (sum == 0)
	{
		zero++;
		return;
	}
	if (sum == size*size)
	{
		one++;
		return;
	}

	DFS(arr, zero, one, st_row, st_col, size / 2);
	DFS(arr, zero, one, st_row, st_col + size /2, size / 2);
	DFS(arr, zero, one, st_row + size /2, st_col, size / 2);
	DFS(arr, zero, one, st_row + size /2, st_col + size /2, size / 2);

}

vector<int> solution(vector<vector<int>> arr) {
	vector<int> answer(2,0);
	answer[0] = 0, answer[1] = 0;

	DFS(arr, answer[0], answer[1], 0, 0, arr[0].size());

	return answer;
}