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

 

알고리즘 연습 - 모의고사 | 프로그래머스

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3,

programmers.co.kr

 

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

 

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

 

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

 

이어서 맞은 개수와, 학생 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

 

알고리즘 연습 - 완주하지 못한 선수 | 프로그래머스

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 partic

programmers.co.kr

 

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

 

결론적으로 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 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

programmers.co.kr

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

 

https://www.welcomekakao.com/learn/courses/30/lessons/42748

 

알고리즘 연습 - K번째수 | 프로그래머스

[1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3]

www.welcomekakao.com

 

벡터에 담긴 수를 잘라서 정렬 이후에, 주어진 index의 데이터를 벡터에 담아서 반환하면 되는 문제이다.

 

문제에서는 index의 시작을 1로 보고 있다는 것만 주의하면 되는 문제이다.

 

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

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
	vector<int> answer;

	for (int i = 0; i < commands.size(); i++) {
		vector<int> temp;
		for (int j = commands[i][0]-1; j <= commands[i][1]-1; j++) {
			temp.push_back(array[j]);
		}
		sort(temp.begin(), temp.end());
		answer.push_back(temp[commands[i][2] - 1]);
		temp.clear();
	}
	return answer;
}

+ Recent posts