프로그래머스 : 체육복 (C++, Lv.1, 탐욕법)

 

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

코딩테스트 연습 - 체육복

 

 

소스코드

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    // 체육복 갯수를 저장하는 n크기의 벡터 저장
    vector<int> students(n,1);
    int answer = 0;
    
    //체육복 갯수 맞추기
    for(int i : reserve) students[i-1]++;
    for(int i : lost) students[i-1]--;
    
    //탐욕적으로 왼쪽, 오른쪽을 살펴 체육복 가져오기
    for(int i = 0 ; i < n ; i++) {
        if(students[i] == 0) {
            //왼쪽 친구에게 체육복 얻기
            if(i>0 && students[i-1]==2) {
                students[i-1]--;
                students[i]++;
            }
            //오른쪽 친구에게 체육복 얻기
            else if(i<n-1 && students[i+1] == 2) {
                students[i+1]++;
                students[i]++;
            }
        }
    }

    for(int n : students) if(n>0) answer++;

    return answer;
}

---

 

실패코드

왼쪽을 먼저 쭉 탐색하냐 오른쪽을 쭉 탐색하냐에 따라 오답도 달라진다 킹받게...

사실 아직도 왜 틀린지 이해를 못하겠다... 왜 탐욕법으로 하는건 되고 나름 논리적(?)이라 생각하는 코드는 안 되는걸까...

우선 프로그래머스에 질문 올려놨으니 누군가 알려줬으면 좋겠다.

https://programmers.co.kr/questions/31824

프로그래머스

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    // 체육복 갯수를 저장하는 n크기의 벡터 저장
    vector<int> students(n,1);
    int answer = 0;
    
    //체육복 갯수 맞추기
    for(int i : reserve) students[i-1]++;
    for(int i : lost) students[i-1]--;
    
    //오른쪽 친구한테 체육복 빌리기
    for(int i = 0; i < n-1; i++) {
        if(students[i] == 0 && students[i+1] == 2) {
            students[i]++;
            students[i+1]--;
        }
    }    
    //왼쪽 친구한테 체육복 빌리기
    for(int i = 1; i < n; i++) {
        if(students[i] ==0 && students[i-1] == 2) {
            students[i]++;
            students[i-1]--;
        }
    }

    for(int n : students) if(n>0) answer++;

    return answer;
}