[C++][알고리즘] 프로그래머스::체육복 풀이

https://programmers.co.kr/learn/courses/30/lessons/42862

코딩테스트 연습 - 체육복 | 프로그래머스

설명

탐욕법

탐욕법 카테고리 문제이므로, 최적의 해를 구한다는 보장은 없고, 모든 문제에 대해 그리디알고리즘을 적용할 수 없다.

어떤 문제에 대해서는 동적프로그래밍보다 더 높은 효율을 보이지만 매번 이 알고리즘이 더 최선의 해를 선택한다는 보장이 없다 이거다.

 

시행착오

 

 
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int check(int lostmem, vector<int>&reserve) {
    vector<int>::iterator iter;
    for (int i = 0; i < reserve.size(); i++) {
        if (lostmem - 1 == reserve[i]) {
            reserve.erase(reserve.begin() + i);
            return 1;
        }
        if (lostmem + 1 == reserve[i]) {
            reserve.erase(reserve.begin() + i);
            return 1;
        }
    }
    return 0;
}
int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = n - lost.size();
    for (int i = 0; i < lost.size(); i++) {
        answer += check(lost[i], reserve);
    }
 
    return answer;
}

맨처음엔 이터레이터와 vector 클래스가 가지고있는 erase 함수를 이용해서 reserve 배열 즉,

유니폼이 2개인 애들이 자신의 여분을 빌려주면 reserve 배열에서 삭제하고 

check 함수의 return value를 answer에 더해주면서 유니폼을 입을수 있는 사람 수를 구하는 방식인데...

 

몇몇의 테스트케이스에서 실패가 되었다. 다른 방식으로 맞추고 나도 어느 부분이 문제인진 잘 모르겠다.

 

 

다른 풀이법(만점)

 
int solution(int n, vector<int> lost, vector<int> reserve) {
    vector<int> list(n, 1);
    int answer=0;
    for (int i = 0; i < lost.size(); i++) {
        list[lost[i] - 1]--;
    }
    for (int i = 0; i < reserve.size(); i++) {
        list[reserve[i] - 1]++;
    }
    for (int i = 0; i < list.size(); i++) {
        if (list[i] == 0) {
            if (i != 0 && list[i - 1] == 2) {
                list[i - 1]--;
                list[i]++;
            }
            else if (i != list.size() - 1 && list[i + 1] == 2) {
                list[i + 1]--;
                list[i]++;
            }
        }
    }
    for (int i = 0; i < list.size(); i++) {
        if (list[i] !=0) {
            answer++;
        }
    }
    return answer;
}

이건 만점이 아니지 솔직히

결국 요번에도 OTK(원턴킬) 실패. 언제쯤 한번에 성공하는 쾌감을 맛볼 수 있을까 ㅠ.