[프로그래머스 Lv1] : 체육복

문제 링크

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

코딩테스트 연습 - 체육복

체육복을 도난당한 학생들이 최대한 체육복을 빌려서 체육수업을 들을 수 있도록 해주자.

 

풀이

• 나의 알고리즘

1. 잃어버린 학생들 중에 여벌옷을 가지고 있는 학생들은 빌려주지 못하고 자기가 입어야 하므로

본인 여벌옷을 입는다.

 

2. 체육복을 빌려줄 수 있는 학생들 중에 2명을 빌려줄 수 있는 학생이 아닌, 1명만 빌려줄 수 있는 학생들 먼저 도난 당한 학생들에게 체육복을 빌려준다.

이유는??

=> 만약 도난당한 학생 i에게 2명의 학생 A,B가 체육복을 빌려줄 수 있다고 하자.

이때 학생 A는 i 외에는 빌려줄 학생이 없고, 학생 B는 i 외에도 다른 학생에게 한 명 더 빌려줄 수 있다면.

학생 A가 i에게 빌려주면, B는 다른 학생에게 빌려줄 수 있으므로 도난당한 학생 2명이 수업에 참가할 수 있게된다.

만약 B가 i에게 빌려줘 버리면 A가 가지고있는 여벌옷은 무용지물이다.

 

3. 체육복을 빌려줄 수 있는 학생들 중 2번 과정에서 빌려주지 못한 학생들이 남은 도난 당한 학생들에게 빌려준다.

 

코드 작성

#include <string>
#include <vector>
#include <iostream>
using namespace std;
const int MAX_N = 30 + 5;
bool is_lost[MAX_N];
int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = n - lost.size();
    for(int i = 0; i<lost.size(); i++)
        is_lost[lost[i]] = true;
    for(int i = 0; i<reserve.size(); i++){
        int student = reserve[i];
        if(is_lost[student]){ //자기가 입어야해서 못빌려줌
            reserve[i] = -1;
            answer++;
            is_lost[student] = false;
        }
    }
    for(int i = 0; i<reserve.size(); i++){
        int student = reserve[i];
        if(student == -1)
            continue;
        int can_rent = 0;
        if(is_lost[student - 1])
            can_rent++;
        if(is_lost[student + 1])
            can_rent++;
        if(can_rent == 2 || can_rent == 0)
            continue;
        if(is_lost[student - 1]){
            reserve[i] = -1;
            answer++;
            is_lost[student - 1] = false;
            continue;
        }
        else if(is_lost[student + 1]){
            reserve[i] = -1;
            answer++;
            is_lost[student + 1] = false;
        }
    }
    
    for(int i = 0; i<reserve.size(); i++){
        if(reserve[i] == -1)
            continue;
        int student = reserve[i];
        if(is_lost[student - 1]){
            answer++;
            is_lost[student - 1] = false;
            continue;
        }
        else if(is_lost[student + 1]){
            answer++;
            is_lost[student + 1] = false;
        }
    }
    return answer;
}

1, 2, 3번 과정을 따로 작성하다 보니까 어쩔 수 없이 코드가 길어졌다.

 

• 다른 분의 알고리즘

AC를 받은 후에 다른 분들의 알고리즘을 한 번 봤더니, 내 코드의 절반도 안되는 양이었다.

그 분들의 아이디어는

int student[] 라는 배열을 만들어서 학생들마다 가지고 있는 체육복의 양을 적었다.

배열의 초기값은 모두 본인 체육복을 갖고 있으므로 0이다.

도난 당한 학생들은 배열 값에 -1, 체육복이 남는 학생들은 +1을 해준다.

이렇게 하면 도난 당했지만 본인이 여벌옷을 가지고 있는 학생들은 -1 한 후에 +1을 하기때문에 결국 값이 0이된다.

 

이제 학생들 중에 배열의 값이 1인 학생들만 체육복을 빌려줄 수 있다.

이때, 도난 당한 학생을 기준으로 앞, 뒷사람에게 모두 체육복을 빌릴 수 있는 경우에 앞사람에게 빌리는 것을 우선으로 생각한다면 최대한 많은 학생들이 체육복을 빌릴 수 있게된다.

이렇게 하면 한 사람에게 2명의 학생이 체육복을 빌려줄 수 있는 상황이 있을 때, 최대한 많은 학생들이 체육복을 빌릴 수 있게 된다.

 

코드 작성

#include <string>
#include <vector>
 
using namespace std;
int student[35];
int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    for(int i : reserve) student[i] += 1;
    for(int i : lost) student[i] += -1;
    for(int i = 1; i <= n; i++) {
        if(student[i] == -1) {
            if(student[i-1] == 1) 
                student[i-1] = student[i] = 0;
            else if(student[i+1] == 1) 
                student[i] = student[i+1] = 0;
        }
    }
    for(int i  = 1; i <=n; i++)
        if(student[i] != -1) answer++;
 
    return answer;
}

이렇게 하면 훨씬 더 간결하게 작성할 수 있다.