개발일지

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;
}

문제 : 

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

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

using namespace std;

int solution(string s) {
	int answer = 1000;

	if (s.size() == 1) return 1;

	vector<string> res(s.size() / 2);

	for (int j = 0; j < s.size() / 2; j++)
	{
		int div_num = j+1;
		int div_cnt = s.size() / div_num;

		int cnt = 1;
		bool ref_check = false;
		for (int k = 0; k < div_cnt; k++)
		{
			ref_check = false;
			for (int n = 0; n < div_num; n++)
			{
				if (k == div_cnt - 1) break;
				if (s[k*div_num + n] != s[(k + 1)*div_num + n])
				{
					break;
				}
				else
				{
					if (n == div_num - 1) ref_check = true;
				}
			}

			if (ref_check) { cnt++; }
			else
			{
				if (cnt == 1)
				{
					for (int n = 0; n < div_num; n++)
					{
						res[j].push_back(s[k*div_num + n]);
					}
				}
				else
				{
					string number = to_string(cnt);
					res[j] += number;
					for (int n = 0; n < div_num; n++)
					{
						res[j].push_back(s[k*div_num + n]);
					}
				}
				cnt = 1;
			}
		}

		for (int i = div_cnt * div_num; i < s.size(); i++)
		{
			res[j].push_back(s[i]);
		}

	}

	for (int i = 0; i < res.size(); i++)
	{
		if (answer > res[i].size()) answer = res[i].size();
	}

	return answer;
}

다음엔 더 최적화해서...

실패한 코드

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

void swap(int *x, int *y) {
	int temp = *x;
	*x = *y;
	*y = temp;
}

int solution(vector<int> scoville, int K) {
	int answer = 0;
	
	sort(scoville.begin(), scoville.end());

	for (int i = 0; i < scoville.size() - 1; i++)
	{
		if (scoville[i] < K)
		{
			scoville[i + 1] = scoville[i] + 2 * scoville[i + 1];
			answer++;

			int j = i;
			while (j + 2 != scoville.size())
			{
				if (scoville[j + 1] > scoville[j + 2])
				{
					swap(scoville[j + 1], scoville[j + 2]);
					j++;
				}
				else
					break;
			}
			scoville.erase(scoville.begin() + i, scoville.begin() + i + 1);
			i--;
		}
	}
	if (scoville.back() < K) return -1;

	return answer;
}

수정후 priority_queue를 사용하자..

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

int solution(vector<int> scoville, int K) {
    int answer = 0;

    priority_queue<int, vector<int>, greater<int>> pq;

    for (auto & v : scoville) pq.push(v);

    while (true)
    {
        if (pq.size() == 1)
        {
            if (pq.top() < K) return -1;
            return answer;
        }
        else if(pq.top()<K)
        {
            int sum = pq.top();
            pq.pop();
            sum += 2 * pq.top();
            pq.pop();
            pq.push(sum);
            answer++;           
        }
        else return answer;
    }
    return answer;
}

문제 : https://programmers.co.kr/learn/courses/30/lessons/42586

나의 풀이

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {

    vector<int> answer;
    vector<int> dday;

    for (int i = 0; i < progresses.size(); i++)
    {
        if ((100 - progresses[i]) % speeds[i] != 0) dday.push_back((100 - progresses[i]) / speeds[i] + 1);
        else dday.push_back((100 - progresses[i]) / speeds[i]);
    }

    int cnt = 0;
    int day = 0;

    for (int i = 0; i < dday.size(); i++)
    {
        if (dday[i] > day) {
            day = dday[i];

            for (int j = i; j < dday.size(); j++)
            {
                if (dday[j] <= day)
                {
                    cnt++;
                }
                else
                {
                    i = j - 1;
                    break;
                }
            }
            if (!cnt)break;

            answer.push_back(cnt);
            cnt = 0;
        }
    }
    return answer;
}

다른사람 풀이를 보니 한싸이클로 풀다니...

재귀함수 연습

순열(Permutation)

1.

#include <iostream>

using namespace std;

void swap(char & a, char & b)
{
	char temp = a;
	a = b;
	b = temp;
}

void permutation(char data[], int depth, int n, int r)
{
	if (depth == r)
	{
		for (int i = 0; i < r; i++)
		{
			cout << data[i];
		}
		cout << endl;

		return;
	}

	for (int i = depth; i < n; i++)
	{
		swap(data[i], data[depth]);
		permutation(data, depth + 1, 4, 4);
		swap(data[i], data[depth]);
	}
}

int main()
{
	char arr[] = { 'a', 'b', 'c', 'd' };
	permutation(arr, 0, 4, 3); // 4P3

	return 0;
}

2.

#include <iostream>
#include <vector>

using namespace std;

void repeatPermutation(vector<pair<char, bool>> check, vector<char> perm, int depth)
{
	if (depth == perm.size())
	{
		for (int i = 0; i < perm.size(); i++)
		{
			cout << perm[i] << " ";
		}
		cout << endl;
		return;
	}

	for (int i = 0; i < check.size(); i++)
	{
		if (check[i].second == true) continue;

		check[i].second = true;
		perm[depth] = check[i].first;
		repeatPermutation(check, perm, depth + 1);
		check[i].second = false;
	}
}

int main()
{
	const int p = 3;
	vector<char> word = { 'a', 'b', 'c', 'd' };
	vector<char> perm(p);
	vector<pair<char, bool>> check;

	for (int i = 0; i < word.size(); i++)
	{
		check.push_back(make_pair(word[i], false));
	}

	repeatPermutation(check, perm, 0);

	return 0;
}

3. STL 사용 next_permutation

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

using namespace std;

int main(){

	vector<char> v = {'a', 'b', 'c', 'd'};
	const int r = 3;

	do
	{
		for(int i = 0; i < r; i++)
		{
			cout << v[i] << " ";
		}
		cout << '\n';

	}while(next_permutation(v.begin(),v.end()));   

}

실행결과

조합(Combination)

1.

#include <iostream>
#include <vector>

using namespace std;

void Combination(vector<pair<char, bool>> check, vector<char> perm,int index, int depth)
{
	if (depth == perm.size())
	{
		for (int i = 0; i < perm.size(); i++)
		{
			cout << perm[i] << " ";
		}
		cout << endl;
		return;
	}

	for (int i = index; i < check.size(); i++)
	{
		if (check[i].second == true) continue;

		check[i].second = true;
		perm[depth] = check[i].first;
		Combination(check, perm, index + 1, depth + 1);
		check[i].second = false;
	}
}

int main()
{
	const int p = 3;
	vector<char> word = { 'a', 'b', 'c', 'd' };
	vector<char> perm(p);
	vector<pair<char, bool>> check;

	for (int i = 0; i < word.size(); i++)
	{
		check.push_back(make_pair(word[i], false));
	}

	Combination(check, perm, 0, 0);

	return 0;
}

2. STL 사용 prev_permutation

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    const int r = 3;
    
    vector<char> arr{'a', 'b', 'c', 'd'};
    vector<bool> temp(arr.size(), false);
    for(int i = 0; i < r; i ++) // 앞부터 r개의 true가 채워진다. 나머지 뒤는 false.
        temp[i] = true;
 
    do {
        for (int i = 0; i < arr.size(); ++i) {
            if (temp[i])
                cout << arr[i] << ' ';
        }
        cout << endl;
    } while (prev_permutation(temp.begin(), temp.end()));
}

next_permutation 은 현재부터 오름차순으로

prev_permutation 은 현재부터 내림차순으로 정렬해주는 STL 함수로 여러곳에서 활용가능할듯하다

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

using namespace std;

int solution(int n, vector<string> data) {
    int answer = 0;

    vector<char> KakaoFriends = { 'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T' };

    do
    {
        bool check = false;
        int k_position[2];
        int k_distance;

        for (int j = 0; j < n; j++)
        {
            for (int i = 0; i < KakaoFriends.size(); i++)
            {
                if (KakaoFriends[i] == data[j][0]) k_position[0] = i;
                if (KakaoFriends[i] == data[j][2]) k_position[1] = i;
            }

            k_distance = abs(k_position[0] - k_position[1]) - 1;

            if (data[j][3] == '=')
            {
                if (k_distance == data[j][4] - '0') check = true;
                else check = false;
            }
            else if (data[j][3] == '>')
            {
                if (k_distance > data[j][4] - '0') check = true;
                else check = false;
            }
            else if (data[j][3] == '<')
            {
                if (k_distance < data[j][4] - '0') check = true;
                else check = false;
            }
            else
            {
                check = false;
            }
            if (!check) break;
        }
        if (check)
        {
            answer++;
        }

    } while (next_permutation(KakaoFriends.begin(), KakaoFriends.end()));

    return answer;
}

이 문제는 수학 문제와 관련이 많고

어떤 규칙이 있을지 살펴보다가

서로소인경우 w+h-1인것을 알게되었다.

이후 못쓰는 사각형 조건 2가지를 발견하였고

1. if (w == 1 || h == 1) return 0;

2. 최대공배수 * (w*h/최대공배수 -1)

전체 사각형의 수 w*h 에서 빼주면 된다.

참고로 (long long)w * h 안해주면 값이 초과되어 실패가 될 수 있다.

int gcd(int a, int b) { return (a % b == 0 ? b : gcd(b, a % b)); }

long long solution(int w, int h) {
	long long answer = 1;

	if (w == 1 || h == 1)
	{
		return 0;
	}

	int a = gcd(w, h);
	answer = ((long long)w * (long long)h) - (w / a + h / a - 1) * a;

	return answer;
}

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

using namespace std;

vector<string> solution(vector<string> record) {
	vector<string> answer;


	map<string, string> id;

	for (int i = 0; i < record.size(); i++)
	{
		string a[3];
		int k = 0;
		for (int j = 0; j < record[i].size(); j++)
		{
			if (record[i][j] != ' ')
			{
				a[k].push_back(record[i][j]);
			}
			else
			{
				k++;
			}
		}
		if (a[0] == "Enter" || a[0] == "Change")
		{
			id.erase(a[1]);
			id[a[1]] = a[2];
		}
	}
	for (int i = 0; i < record.size(); i++)
	{
		string a[3];
		int k = 0;
		for (int j = 0; j < record[i].size(); j++)
		{
			if (record[i][j] != ' ')
			{
				a[k].push_back(record[i][j]);
			}
			else
			{
				k++;
			}
		}
		if (a[0] == "Enter")
		{
			answer.push_back(id[a[1]] + "님이 들어왔습니다.");
		}
		if (a[0] == "Leave")
		{
			answer.push_back(id[a[1]] + "님이 나갔습니다.");
		}
	}
	return answer;
}