개발일지

문제 

https://www.acmicpc.net/problem/12018

내가 푼 코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int main() {
	int N, M, cnt = 0;
	priority_queue<int, vector<int>, greater<int>> que;
	cin >> N >> M;
    
	for (int i = 0; i < N; i++) {
		int p, l, min;
		priority_queue<int, vector<int>, less<int>> temp;
		cin >> p >> l;
		for (int i = 0; i < p; i++)
		{
			int list;
			cin >> list;
			temp.emplace(list);
		}
        
		int size = temp.size();
		if (size < l) 
		{
			min = 1;
		}
		else
		{
			for (int i = 0; i < l - 1; i++)
			{
				temp.pop();
			}
			min = temp.top();
		}
		que.emplace(min);
	}

	for (int i = 0; i < N; i++)
	{
		int top = que.top();
		if (M < top)
		{
			break;
		}
		M -= top;
		que.pop();
		cnt++;
	}
	cout << cnt << endl;
    
	return 0;
}

문제

https://www.acmicpc.net/problem/1781

내가 푼 코드

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

bool mysort(const pair<int, int>& a,
	const pair<int, int>& b)
{
	if(a.first == b.first)
		return (a.second > b.second);
	else
		return (a.first < b.first);
}

int main() {
	int N, S, E;
	cin >> N;

	vector<pair<int, long long int>> v(N);
	priority_queue<long long int, vector<long long int>, greater<long long int>> con;

	for (int i = 0; i < N; i++)
	{
		cin >> S >> E;
		v[i] = make_pair(S, E);
	}	

	sort(v.begin(), v.end(), mysort);

	int num = 0;
	for (int i = 0; i < N; i++)
	{
		if (v[i].first > num)
		{
			num = v[i].first;
		}
		else
		{
			continue;
		}

		for (int j = i; j < i + num; j++)
		{
			if(j == N)
				break;

			if (num == v[j].first)
			{
				int con_size = con.size();
				if (con_size < num)
				{
					con.emplace(v[j].second);
				}
				else
				{
					if (con.top() < v[j].second)
					{
						con.pop();
						con.emplace(v[j].second);
					}
					else
					{
						i = j;
						break;
					}
				}
			}
			else
			{
				i = j - 1;
				break;
			}
		}
	}

	int sum = 0;
	while (!con.empty())
	{
		sum += con.top();
		con.pop();
	}

	cout << sum << endl;
	return 0;
}

문제

https://www.acmicpc.net/problem/10825

내가 푼 코드

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

struct student
{
    string name;
    int kor;
    int eng;
    int math;
};

bool compare(const student& a, const student& b)
{
    if (a.kor != b.kor)
        return a.kor > b.kor;
    if (a.eng != b.eng)
        return a.eng < b.eng;
    if (a.math != b.math)
        return a.math > b.math;
    return a.name < b.name;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int N;
    vector<student> v;
    cin >> N;
    v.resize(N);
    for (int i = 0; i < N; i++)
    {
        student temp;
        cin >> temp.name >> temp.kor >> temp.eng >> temp.math;
        v[i] = temp;
    }
    sort(v.begin(), v.end(), compare);
    for (int i = 0; i < N; i++)
    {
        cout << v[i].name << '\n';
    }
    return 0;
}

마지막

cout << v[i].name << '\n'; 을 cout << v[i].name << endl; 하면 시간초과 나옴

문제

https://www.acmicpc.net/problem/2121

내가 쓴 코드 

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int main(void) {
	int N, W, H; 
	vector<pair<int, int>> list;
	int x, y;
	int cnt = 0;

	cin >> N >> W >> H;

	for (int i = 0; i < N; i++)
	{
		cin >> x >> y;
		list.push_back(make_pair(x, y));
	}
	sort(list.begin(), list.end());
	for (int lb = 0; lb < N-3; lb++)
	{
		//LB
		int x1 = list[lb].first;
		int y1 = list[lb].second;

		bool chk = false;

		//LT
		int lt;
		for (lt = lb + 1; lt < N - 2; lt++)
		{
			int x2 = list[lt].first;
			int y2 = list[lt].second;

			if (x2 == x1 && y2 == y1 + H) chk = true;
			if (x2 > x1 || chk) break;
		}

		if (chk) 
		{ 
			chk = false; 
		}
		else
		{
			continue;
		}

		//RB
		int rb;
		for (rb = lt + 1; rb < N - 1; rb++)
		{
			int x3 = list[rb].first;
			int y3 = list[rb].second;

			if (x3 == x1 + W && y3 == y1) chk = true;
			if (x3 > x1 + W || chk) break;
		}

		if (chk)
		{
			chk = false;
		}
		else
		{
			continue;
		}

		//RT
		int rt;
		for (rt = rb+1; rt < N; rt++)
		{
			int x4 = list[rt].first;
			int y4 = list[rt].second;

			if (x4 == x1 + W && y4 == y1 + H) chk = true;
			if (x4 > x1 + W || y4 > y1 + H || chk) break;
		}
		if (chk) cnt++;
	}

	cout << cnt << endl;

	return 0;
}

문제

https://www.acmicpc.net/problem/6417

내가 쓴 코드

#include <iostream>
#include <cmath>
using namespace std;

int main(void) {
	int N;
	string command;
	while (true)
	{
		cin >> N;
		if(N == -1) break;
		int maxK = 0;
		for (int i = 2; i < sqrt(N)+1; i++)
		{
			int temp = N;
			bool chk = true;
			for (int j = 0; j < i; j++)
			{
				temp -= 1;
				if (temp % i == 0)
				{
					temp = (temp * (i - 1)) / i;
				}
				else
				{
					chk = false;
					break;
				}
			}
			if (chk && temp % i == 0) maxK = i;
		}

		if (maxK < 2)
		{
			cout << N << " coconuts, no solution" << endl;
		}
		else
		{
			cout << N << " coconuts, "<< maxK <<" people and 1 monkey" << endl;
		}
	}

	return 0;
}

문제

https://www.acmicpc.net/problem/10828

내 코드

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

struct Node
{
	Node* prev = nullptr;
	int value;

	Node(int val)
	{
		this->value = val;
	}
};

class Stack
{
private:
	Node* start = nullptr;
	Node* end = nullptr;
	int size = 0;
public:
	void Push(int val)
	{
		Node* newNode = new Node(val);
		if (start == nullptr)
		{
			start = end = newNode;
		}
		else
		{
			newNode->prev = end;
			end = newNode;
		}
		size++;
	}

	int Pop()
	{
		if (size > 0)
		{
			int value = end->value;
			Node* temp = end->prev;
			end = nullptr;
			delete end;
			end = temp;
			size--;
			return value;
		}
		return -1;
	}

	int Size()
	{
		return size;
	}

	int Empty()
	{
		if (size == 0) { return 1; }
		return 0;
	}

	int Top()
	{
		if (size > 0) { return end->value; }
		return -1;
	}
};


int main(void) {
	int N;
	Stack myS;
	string command;
	int val;

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> command;
		if (command == "push")
		{
			cin >> val;
			myS.Push(val);
		}
		else if (command == "pop")
		{
			cout << myS.Pop() << endl;
		}
		else if (command == "size")
		{
			cout << myS.Size() << endl;
		}
		else if (command == "empty")
		{
			cout << myS.Empty() << endl;
		}
		else if (command == "top")
		{
			cout << myS.Top() << endl;
		}
	}
	return 0;
}

큐 풀면서 스텍도 비슷해서 같이 풀어봄

문제

https://www.acmicpc.net/problem/10845

소스코드

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

struct Node
{
	Node* next = nullptr;
	int value;

	Node(int val)
	{
		this->value = val;
	}
};

class Queue
{
private:
	Node* start = nullptr;
	Node* end = nullptr;
	int size = 0;
public:
	void Push(int val)
	{
		Node* newNode = new Node(val);
		if (start == nullptr)
		{
			start = end = newNode;
		}
		else
		{
			end->next = newNode;
			end = newNode;
		}
		size++;
	}

	int Pop()
	{
		if (size > 0)
		{
			int value = start->value;
			Node* temp = start->next;
			start = nullptr;
			delete start;
			start = temp;
			size--;
			return value;
		}
		return -1;
	}

	int Size()
	{
		return size;
	}

	int Empty()
	{
		if (size == 0) { return 1; }
		return 0;
	}

	int Front()
	{
		if (size > 0) { return start->value; }
		return -1;
	}

	int Back()
	{
		if (size > 0) { return end->value; }
		return -1;
	}
};


int main(void) {
	int N;
	Queue myQ;
	string command;
	int val;

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> command;
		if (command == "push")
		{
			cin >> val;
			myQ.Push(val);
		}
		else if (command == "pop")
		{
			cout << myQ.Pop() << endl;
		}
		else if (command == "size")
		{
			cout << myQ.Size() << endl;
		}
		else if (command == "empty")
		{
			cout << myQ.Empty() << endl;
		}
		else if (command == "front")
		{
			cout << myQ.Front() << endl;
		}
		else if (command == "back")
		{
			cout << myQ.Back() << endl;
		}
	}
	return 0;
}

큐를 사용 할 수 있었지만 만들어서 문제를 풀어보았다.

https://www.acmicpc.net/problem/1931

<코드>

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

bool cmp(pair<int, int> a, pair<int, int> b)
{
	if (a.second == b.second)
	{
		return a.first < b.first;
	}
	return a.second < b.second;
}

int main()
{
	int N;
	int start, end;
	vector<pair<int, int>> list;

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> start >> end;
		list.push_back(make_pair(start, end));
	}

	sort(list.begin(), list.end(), cmp);

	int time = list[0].second;
	int cnt = 1;	

	for (int i = 1; i < N; i++)
	{
		if (time <= list[i].first)
		{
			time = list[i].second;
			cnt++;
		}
	}
	cout << cnt;
}

문제

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

내가 쓴 코드

#include <string>
#include <vector>

using namespace std;

vector<int> factor(int a) {
	vector<int> vec_fac(0);

	if (a <= 0) return vec_fac;

	for (int i = 2; i <= a / 2; i++) {
		if (a % i == 0) { vec_fac.push_back(i); }
	}
	vec_fac.push_back(a);
	return vec_fac;
}

int GetMinValue(vector<int> arr)
{
	int min_value = 100000000;
	for (int i = 0; i < arr.size(); i++)
	{
		if (min_value > arr[i]) min_value = arr[i];
	}
	return min_value;
}

vector<int> GetMaxInt(vector<int> src, vector<int> cmp)
{
	vector<int> res(0);
	int temp;
	for (int i = src.size() - 1; i >= 0; i--)
	{
		temp = src[i];
		for (int j = 0; j < cmp.size(); j++)
		{
			if (cmp[j] % temp == 0)
			{
				temp = 0;
				break;
			}
		}
		if (temp == 0) continue;
		res.push_back(temp);
	}
	return res;
}

int ResultMaxInt(vector<int> MaxInt, vector<int> vec_arr1, vector<int> vec_arr2)
{
	if (MaxInt.size() == 0) return 0;
	int res;
	for (int j = 0; j < MaxInt.size(); j++)
	{
		res = MaxInt[j];
		for (int i = 0; i < vec_arr1.size(); i++)
		{
			if (vec_arr1[i] % res != 0)
			{
				res = 0;
				break;
			}
		}

		for (int i = 0; i < vec_arr2.size(); i++)
		{
			if(res == 0) break;
			if (vec_arr2[i] % res == 0)
			{
				res = 0;
				break;
			}
		}

		if(res != 0) break;
	}

	return res;
}

int solution(vector<int> arrayA, vector<int> arrayB) {
	int answer = 0;

	int minA, minB, resA, resB;
	vector<int> factorA(0), factorB(0);
	minA = GetMinValue(arrayA);
	minB = GetMinValue(arrayB);
	factorA = factor(minA);
	factorB = factor(minB);

	resA = ResultMaxInt(GetMaxInt(factorA, factorB), arrayA, arrayB);
	resB = ResultMaxInt(GetMaxInt(factorB, factorA), arrayB, arrayA);

	return (resA > resB)? resA : resB;
}

베스트 코드

#include <bits/stdc++.h>
using namespace std;

int f(int a, int b){return a % b == 0 ? b : f(b, a % b);}
int f(vector<int> &a, vector<int> &b){
    int A = a[0];
    for (int x : a) A = f(max(A, x), min(A, x));
    for (int x : b)
    if (x % A == 0)
        return 0;
    return A;
}
int solution(vector<int> a, vector<int> b) {
    return max(f(a, b), f(b, a));
}

 현타..

문제

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

내가 쓴 코드

#include <string>
#include <vector>

using namespace std;

vector<double> solution(int k, vector<vector<int>> ranges) {
    vector<double> answer(0);
    vector<float> ubak_con(0);

    while (true)
    {
        if (k <= 1) break;
        int temp = k;
        k = (k % 2 == 0) ? k /= 2 : k = 3 * k + 1;
        ubak_con.push_back((float)(temp + k) / 2);
    }

    for (int i = 0; i < ranges.size(); i++)
    {
        double sum = 0; 
        int start = ranges[i][0];
        int end = ubak_con.size() + ranges[i][1];
        for (int j = start; j < end; j++)
        {
            sum += (double)ubak_con[j];
        }

        if (start > end) { sum = -1; }
        answer.push_back(sum);
    }
    return answer;
}

(signal: segmentation fault (core dumped)) 에러나서 바꿈

	for (int j = ranges[i][0]; j < ubak_con.size() + ranges[i][1]; j++)
        {
            sum += (double)ubak_con[j];
        }

//(signal: segmentation fault (core dumped)) 에러나서 아래로 바꿈

	int start = ranges[i][0];
        int end = ubak_con.size() + ranges[i][1];
        for (int j = start; j < end; j++)
        {
            sum += (double)ubak_con[j];
        }