[프로그래머스, C++] 체육복

문제 링크

코딩테스트 연습 - 체육복

 

 

 

풀이

탐욕법 문제답게 체육복이 필요하면 그 순간 여벌이 있는 학생에게 가져오는 문제다.

 

// init

lost 배열 오름차순 <--- for. 최대한 많은 학생이 체육 수업을 할 수 있도록 적은 수부터 비교

reserve 배열 오름차순 <--- for. 최대한 많은 학생이 체육 수업을 할 수 있도록 적은 수부터 비교

vector 컨테이너 하나 선언 <--- 인덱스(학생 번호-1)에 따라 가지고 있는 체육복 수, 생성자를 이용해 n개의 1로 초기화

도둑 맞은 (학생번호-1)은 체육복 수 감소(--;)

여벌복 있는 학생은 체육복 수 증가(++;)

answer = n <--- 모든 학생들은 체육수업을 간다고 전제한다.

 

// process

반복문(학생수)

{

    가지고 있는 체육복 수가 0이라면(없다면)

    {

        앞 번호에게 빌리기(앞 번호 학생의 체육복 수는 2라면)    <--- 빌릴 수 있다면 continue; 로 중복 방지

        뒷 번호에게 빌리기(뒷 번호 학생의 체육복 수는 2라면)    <--- 빌릴 수 있다면 continue; 로 중복 방지

        못빌리면 answer--;   <--- 체육 수업 나가는 학생 수 감소

    }

}

 

answer 반환

 

 

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

using namespace std;

// 학생들의 번호는 체격 순으로 바로 앞번호나 뒷번호만 빌리는 것이 가능

// 전체 학생 수 n
// 도난당한 학생들 번호 배열 lost
// 여벌의 체육복 학생 번호 reserve

// 학생 수 2이상 30 이하 --- n
// 도난 당한 학생 수 1이상 n이하, 중복 X
// 여벌 1이상 n이하, 중복 X

// 여벌 체육복을 가져온 학생이 도난당하면 빌려줄 수 없다.

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    
    // init
    sort(lost.begin(), lost.end());     // 오름차순 정렬
    sort(reserve.begin(), reserve.end());       // 오름차순 정렬
    vector<int> students(n, 1);       // 체육복을 1개씩 가지고 있다
    for(int e: lost) students[e-1]--;       // 도둑맞았다, 학생 1번은 인덱스 0
    for(int e: reserve) students[e-1]++;    // 여벌복이 있다.
    answer = n;     // 모두 체육 수업을 나갈 수 있다 전제.
    
    // process
    for(int i=0; i<n; i++){
        int obj = students[i];      // 가지고 있는 체육복 수
        if(obj==0){
            int pre = i-1;          // 앞에 번호한테 빌리기
            if(pre != -1 && students[pre]==2){
                students[pre]--;
                students[i]++;
                continue;
            }
            int next = i+1;         // 뒤에 번호한테 빌리기
            if(next != n && students[next]==2){
                students[next]--;
                students[i]++;
                continue;
            }
            answer--;       // 못빌림
        }
    }
    
    return answer;      // 체육수업을 들을 수 있는 학생의 최댓값 리턴
}