프로그래머스: 알고리즘 문제 풀이(c++)

1. 해시파트

1-1. 포켓몬

• set함수를 통해 중복 요소 제거
• nums.size()/2 < nums_set.size()
  : nums의 요소개수의 절반보다 nums_set의 요소가 더 많다면 최대 nums_set의 개수만큼 각기 다른 종류의 포켓몬이 존재한다는 것 <=> 어차피 최대 nums/2 종류의 개수만큼 고를 수 있기에 nums/2가 반환
• nums.size()/2 > nums_set.size()
  : nums.size()/2개 최대 고를 수 있는데 각기 다른 종류의 개수인 nums_set.size()가 더 작다면 어차피 nums_set.size()개만큼 골라야 다른 종류를 최대 고를 수 있음

#include <iostream>
#include <set>
#include <vector>

using namespace std;

int solution(vector<int> nums) {
	int ans = 0;
	set<int> nums_set(nums.begin(), nums.end());
	ans = min(nums.size()/2, nums_set.size());
	return ans;
}

1-2. 완주하지 못한 선수

• 해시를 이용하여 각 participant의 요소를 반복문을 통해 돌리며 map에 저장
• winner.find(p) == winner.end()이용
• true라면 {p:1}로 저장, 아니라면 해당 value ++
• map에 모두 저장 후 완주한 선수들에 대해 completion vector 반복문을 통해 해당 선수는 map의 value --
• 반복문 다 돌리고 맵의 value중 0이 아닌 것이 있다면 완주를 못했거나 동명이인 선수이므로 해당 선수 이름 return

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    map<string, int> winner;
    for (const string& p : participant){
        if (winner.find(p) == winner.end()) {
            winner[p] = 1;
        }
        else {
            winner[p]++;
        }
    }

    for (const string& p : completion) {
        winner[p]--;                                                                                                           
    }

    for (const string& p : participant) {
        if (winner[p] != 0) {
            return p;
        }
    }
}

 

1-3. 전화번호목록

 

=> set stl을 통해 사전순으로 자동정렬을 시킨 후 반복문을 돌리며 next원소에 대해 포함여부 확인

• vector를 set으로 변환 
• prev,next 내장함수를 통해 마지막 iterator의 이전/다음 이터레이터를 가리킴
• string의 substr함수(추출 시작 idx, 추출할 길이) 이용 

#include <string>
#include <vector>
#include <set>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    set<string> phoneBook(phone_book.begin(), phone_book.end());

    for (auto it = phoneBook.begin(); it != prev(phoneBook.end()); it++) {

        string now = *it;
        string comp = *(next(it));
        if (now == comp.substr(0, now.size())) {
            answer = false;
            break;
        }
    }
   
    return answer;
}

 

1-4. 의상

• {옷의 종류: 그 종류에 속하는 옷들의 개수}를 요소로 하는 unordered_map 생성
• 반복문 돌리며 각 종류마다 속하는 옷 개수 +1만큼 answer에 곱하며 마지막엔 -1 (아무 종류의 옷도 안입은 경우)
  ex) 상의 : a,b / 하의 : c / 액세사리 : d 
  => a,b,c,d,(a,c),(a,d),(b,c),(b,d),(c,d),(a,c,d),(b,c,d) = 11(3 x 2 x 2 - 1)
  => 종류마다 옷의 개수에 +1 하여 곱한 후 최종적으로 1 빼기 
  => 1을 더하는 이유는 안입는 경우 (a만 입는 경우, b만 입는 경우, a,b 둘 다 안입는 경우)

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 0;
    unordered_map<string, int> map;
    for (auto p : clothes) {
        //[["yellow_hat","headgear"],["blue_sunglasses","eyewear"]]인 경우
        //p : ["yellow_hat","headgear"]
        map[p[1]]++;
    }

    answer = 1;

    for (auto p : map) {
        //{"headgear" : 1}
        answer *= (p.second + 1);
    }


    return answer-1;
}

 

1-5. 베스트앨범

• 각 장르에 속하는 play의 수들을 모두 더하여 play 총합을 기준으로 정렬 : genre_arr
  => 정렬할 때는 vector로 변경 후 sort함수 이용(lambda func 이용)
• 정렬된 vec 통해 반복문을 이용하여 plays가 높은 장르들을 순차적으로 돌리며 이때 해당 장르의 곡들의 고유 번호와 그 곡의 play횟수를 저장하는 vector<pair<int,int>> play_arr 생성
  => 현재 장르의 모든 곡들의 정보를 저장하고 난 후 sort함수 통해 play횟수가 같은 경우엔 고유 번호순대로 정렬하고, 그 이외엔 디폴트로 play횟수(value)를 기준으로 내림차순
  => play횟수 기준으로 내림차순 + play횟수가 같을 경우엔 고유 번호를 기준으로 오름차순
• 정렬 후 해당 play_arr의 사이즈가 1일 경우 (무조건 >=1) 첫번째 요소의 고유 번호 answer vector에 push_back
  => play_arr의 사이즈가 1보다 클 경우 최대 2곡까지 수록할 수 있기 때문에 반복문을 통해 answer vector에 push_back
• 최종적으로 answer 반환

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

using namespace std;

vector<int> solution(vector<string> genres, vector<int> plays) {
	vector<int> answer;
	map<string, int> genre_arr;

	for (int i = 0; i < plays.size(); i++) {
		genre_arr[genres[i]] += plays[i];
	}

	vector<pair<string, int>> vec(genre_arr.begin(), genre_arr.end());
	sort(vec.begin(), vec.end(), [](const pair<string, int>& a, const pair<string, int>& b) {
		return a.second > b.second;
		});

	for (auto p : vec) {
		//(("classic" : 800), (...))
		string genre = p.first;
		vector<pair<int, int>> play_arr; //고유 번호, play 횟수
		for (int i = 0; i < plays.size(); i++) {
			if (genre == genres[i]) {
				play_arr.push_back(pair<int, int>(i, plays[i])); //make_pair(i,plays[i])과 동일
			}
		}
		sort(play_arr.begin(), play_arr.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
			//play횟수가 같을 경우 고유 번호순대로 정렬
			if (a.second == b.second) {
				return a.first < b.first; //오름차순(고유 번호는 play횟수가 같을 때 적을 수록 우선순위 높음)
			}
			return a.second > b.second;
			});
		if (play_arr.size() == 1) {
			answer.push_back(play_arr[0].first);
		}
		else{
			for (int i = 0; i < 2; i++) {
				answer.push_back(play_arr[i].first);
			}
		}
	}
	

	return answer;
}

 

2. 그리디(탐욕법)

2-1. 체육복

• 현재 학생들이 가지고 있는 체육복의 수를 저장하는 vector have생성(n,1)로 초기화
• lost vector 반복문을 통해 도난당한 학생의 체육복 수 -1
• reserve vector 반복문을 통해 여벌있는 학생의 체육복 수 +1
• 0번째 학생부터 반복문을 돌리며 체육복의 수가 0이라면 왼쪽이나 오른쪽 학생이 여벌 체육복이 있다면 빌림
• 최종적으로 have vector를 반복문 돌리며 체육복 수가 1이상이라면 sum에 +1

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
	vector<int> have(n, 1);
	int sum = 0;

	for (auto i : lost) {
		have[i - 1] -= 1;
	}

	for (auto i : reserve) {
		have[i - 1] += 1;
	}

	for (int i = 0;i < n;i++) {
		if (have[i] == 0){
			if (i == 0 && i+1 <n && have[i+1] > 1) {
				have[i]++;
				have[i+1]--;
			}
			else if (i == n - 1 && i-1 >= 0 && have[i - 1] > 1) {
				have[i]++;
				have[i - 1]--;
			}
			else {
				int left = i - 1;
				int right = i + 1;
				if (i-1 >=0 && have[left] > 1) {
					have[left]--;
					have[i]++;
				}
				else if (i+1 <n && have[right] > 1) {
					have[right]--;
					have[i]++;
				}
			}
		}
		
	}

	for (auto i : have) {
		if (i >= 1) {
			sum++;
		}
	}

	return sum;
}