기록을

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42840

수포자가 수학을 찍는 규칙을 확인해서, 등수를 가려내는 문제이다.

코드를 좀 더 깔끔하게 구현할 수 있을텐데 직관적으로 빠르게 구현하고자 했기 때문에 코드가 다소 난잡하다.

먼저 세 학생의 답안 마킹 방법을 배열로 설정해뒀다.

이어서 맞은 개수와, 학생 index pair를 벡터에 넣고 정렬을 수행했다.

정렬 조건을 만들어주는 bool 함수만 조심해서 구현하고, 문제 조건에 맞게 조건문을 작성해준다.

#include <string>
#include <vector>
#include<bits/stdc++.h>

using namespace std;
int fir[10000];
int sec[10000];
int thr[10000];
bool cmp(pair<int, int> a, pair<int, int> b){
    //T 면 a가 앞
    if(a.second > b.second)
        return true;
    else 
        return false;
}
vector<int> solution(vector<int> answers) {
    vector<int> answer;
    for(int i = 0 ; i < 10000 ; i ++){
        if(i % 5 == 0) fir[i] = 1;
        else if(i % 5 == 1) fir[i] = 2;
        else if(i % 5 == 2) fir[i] = 3;
        else if(i % 5 == 3) fir[i] = 4;
        else if(i % 5 == 4) fir[i] = 5;
    }
    for(int i = 0 ; i < 10000 ; i ++){
        if(i % 2 == 0) sec[i] = 2;
        else if(i % 8 == 1) sec[i] = 1;
        else if(i % 8 == 3) sec[i] = 3;
        else if(i % 8 == 5) sec[i] = 4;
        else if(i % 8 == 7) sec[i] = 5;
    }
    for(int i = 0 ; i < 10000 ; i++){
        if(i % 10 == 0 || i % 10 == 1) thr[i] = 3;
        else if(i % 10 == 2 || i % 10 == 3) thr[i] = 1;
        else if(i % 10 == 4 || i % 10 == 5) thr[i] = 2;
        else if(i % 10 == 6 || i % 10 == 7) thr[i] =4;
        else if(i % 10 == 8 || i % 10 == 9) thr[i] =5;
    }
    vector<pair<int, int> > v{ {1,0}, {2,0}, {3,0} } ;
    for(int i = 0 ; i < answers.size() ; i++){
        if(fir[i] == answers[i]) v[0].second++;
        if(sec[i] == answers[i]) v[1].second++;
        if(thr[i] == answers[i]) v[2].second++;
    }
    sort(v.begin(), v.end(), cmp);
    
    if(v[0].second != 0){
       if(v[0].second != v[1].second)
           answer.push_back(v[0].first);
        else{
            if(v[1].second == v[2].second){
                answer.push_back(v[0].first);
                answer.push_back(v[1].first);
                answer.push_back(v[2].first);
                }
            else{
                answer.push_back(v[0].first);
                answer.push_back(v[1].first);
            }
        }
    }
    sort(answer.begin(), answer.end());
    return answer;
}

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42576

해쉬 카테고리에 있어서 무조건 그렇게 풀려고 시도했다.

결론적으로 multimap을 이용해서, 선수들의 이름을 map의 key에 넣고,

value는 이 문제에선 큰 의미가 없기 때문에 그냥 순서로 정해주었다.

이후, 완주 한 사람을 찾아서 원래의 map에서 지워주면 자연스럽게 남는 사람이 완주하지 못한 사람이 된다.

#include<iostream>
#include<map>
#include<string>
#include<vector>
using namespace std;
string solution(vector<string> participant, vector<string> completion) {
	string answer = "";

	multimap<string, int> mm;
	for (int i = 1; i <= participant.size(); i++) {
		mm.insert({ participant[i - 1], i });
	}
	for (int i = 0; i < completion.size(); i++) {
		mm.erase(mm.lower_bound(completion[i]));
	}
	return mm.begin()->first;
}

STL의 사용이 익숙하지 않았기 때문에, 사전에 공부가 필요했다.

동명이인이 있을 수 있다고 문제 조건에 명시되어 있으므로 map이 아닌 multimap을 사용했다.

pair를 다룬다고 생각하고 {key, value} 꼴로 map에 insert 해주면 된다.

lower_bound는 같은 key를 가진 데이터들 중에서, 가장 첫번째의 원소를 의미하는 것이다.

upper_bound를 이 문제에서 사용하지는 않았지만, upper_bound를 사용하면, 가장 마지막 원소가 아니라,

가장 마지막 원소보다 한 칸 더 이후를 의미하는 것 같았다.

자료구조에 대해 곧 자세히 정리해야겠다.

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42746

0 또는 양의 정수를 가지는 배열이 주어질 때, 그것을 나열해서 만들 수 있는 가장 큰 수를 string type으로 반환하는 문제이다.

처음에는 단순히 사전식 정렬 이후에, 가장 큰 자릿수의 숫자가 같다면, 길이가 짧은 수가 앞에 와야 큰 수를 만들어낸다고 생각했다.

너무 단순한 생각이었다. 비교하고자 하는 숫자의 길이가 다를 경우에 여러 가지 경우를 고려해줘야 한다.

그렇다면 비교하고자 하는 숫자의 길이를 같게 만들어주면 된다.

45와 4642 중에 어떤 수를 앞에 두어야 올바른 정렬일까 생각해보면,

두 수를 두 가지 방법으로 붙여서 454642와 464245를 비교하면 되는 것이다.

#include <string>
#include <vector>
#include<bits/stdc++.h>

using namespace std;
bool cmp(string a, string b){
    //a가 b보다 먼저 나오는 경우가 true
    if(a + b > b + a)
        return true;
    else
        return false;
}
string solution(vector<int> numbers) {
    string answer = "";
    
    //길이가 다른 경우가 문제니까 길이를 같게 해주려면?
    //비교하는 수 두개를 순서를 바꿔가면서 이어서 붙여보면됨.
    //길이만 같으면 사전순 비교나 크기 비교나 똑같으니까
    
    vector<string> v;
    for(int i = 0 ; i < numbers.size() ; i++)
        v.push_back(to_string(numbers[i]));    
    sort(v.begin(), v.end(), cmp);
    
    //전부 0일 수도 있나?
    bool allZero = true;
    
    for(int i = 0 ; i < v.size() ; i++){
        answer += v[i];
        if(v[i] != "0") allZero = false;
    }
    if(allZero)
        return "0";
    else
        return answer;
    
}

조합과 관련된 문제라고 기억한다. 조합과 백트레킹을 매끄럽게 다룰 수 있었다면 조금 더 빠르게 풀고 넘어갈 수 있었던 문제였다. 역량테스트 A형스러운 문제였던 기억이 난다.

가장 기본적으로 소수를 판별할 수 있어야 한다.

다음으로 정수의 자리수를 없애는 방식으로 수의 변화가 일어난다. 따라서 문자열 처리를 해주면 되겠다.

정수의 자리수에서 하나의 숫자를 지우는 것을 조합의 개념으로 이해하고, 문제를 풀이했다.

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
bool isPrime(int n) {
	if (n == 1) return false;
	for (int i = 2; i * i <= n; i++)
		if (n % i == 0) return false;
	return true;
}
int Max = -1;
int func(int n, int res) {
	
	string str = to_string(n);
	
	if (str.length() == 1) {
		if (isPrime(n)) {
			res++;
			if (Max < res) Max = res;
			//printf("\n %d 일 때 res는 %d\n", n, res);
			return res;
		}
		else {
			if (Max < res) Max = res;
			return res;
		}
	}
	
	if (isPrime(n)) {
		res++;
		if (Max < res) Max = res;
		//printf("\n %d 일 때 res는 %d\n", n, res);
	}
	else {
		//cout << n << "은 소수가 아님\n";
		if (Max < res) Max = res;
		return res;
	}
	
	//vector<int> a; //몇개의 수에서
	int a[6];
	
	for (int i = 0; i < str.length(); i++) {
		a[i] = stoi(str.substr(i, 1));
	}
	
	int select[7] = { 0,1,1,1,1,1,1 };
	
	do {
		string temp;
		for (int i = 0; i < str.length(); i++) {
		
			if (select[i])
				temp = temp + to_string(a[i]);
		}
		//cout << temp << ' ' << res << '\n';
		func(stoi(temp.substr(0,temp.length())),res);
	}while (next_permutation(select, select + str.length()));

}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tc;
	cin >> tc;
	for (int T = 1; T <= tc; T++) {
		cout << "Case #" << T << '\n';
		Max = -1;
		int a, b;
		cin >> a >> b;
		func(a, 0);
		int MaxA = Max;
		Max = -1;
		func(b, 0);
		int MaxB = Max;

		//printf("Amax = %d Bmax = %d\n", MaxA, MaxB);
		if (MaxA > MaxB)
			cout << 1 << '\n';
		else if (MaxA < MaxB)
			cout << 2 << '\n';
		else
			cout << 3 << '\n';
	}
	return 0;
}

#include<iostream>
#include<vector>
using namespace std;
int mem[100001];
int solution(vector<int> prices)
{
	int min = 1000001;
	for (int i = 0; i < prices.size(); i++) {
		if (prices[i] < min) {
			min = prices[i];
		}
		mem[i] = min;
	}
	int max = 0;
	for (int i = 0; i < prices.size(); i++) {
		if (prices[i] - mem[i] > max) {
			max = prices[i] - mem[i];
		}
	}
	return max;
}

prices 배열의 어떤 index까지의 최솟값을 mem 배열에 저장한다.

가령 prices = {1,5,2,6,2,4,0} 이런 상황이라면 mem = {1,1,1,1,1,1,0} 이렇게 되는 것이다.

최소의 가격일 때 구매해서 최대의 가격에 되팔아서 이윤의 최대치를 구하는 문제에 이용할 수 있다.

index가 시간을 의미한다고 볼 수 있다. 같은 index에서 prices와 mem의 차이가 가장 큰 지점이 정답이 된다.

최대 마진을 내야 하는 경우로 기억