CodingTest Practice/Programmers

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

몽땅마니아(MDD) 2022. 5. 22. 22:00

 

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

 

코딩테스트 연습 - 체육복

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번

programmers.co.kr

 

 

소스코드

#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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

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