[프로그래머스] 체육복 (c++)

출처 : 코딩테스트 연습 - 체육복 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 체육복

풀이 방법

map 을 이용하여 체육복 여분이 있는 학생의 번호와 여분 여부를 저장하고 

lostArr를 학생 수 만큼 할당하여 인덱스를 학생 번호로 벡터의 값을 잃어버림 유무로 잡아 저장하였다.

우선 여분을 가지고 있는데 잃어버린 학생을 먼저 처리 하였다

그 후 여분을 가지고 있는 학생의 앞 학생이 체육복을 잃어버렸으면 그 학생 우선 여분을 주고

만약 앞 학생이 잃어버리지 않았다면 여분을 가지고 있는 학생의 뒤 학생에게 체육복을 주어 

그리디한 방식으로 문제를 해결 하였다.

 

#include <string>
#include <vector>
#include <iostream>
#include <map>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {    
    map<int, int> mp;
    int answer = 0;
    int lostN = 0;
    vector<int> lostArr;
    // 여분 있는 학생의 [학생 번호, 여분 여부]
    for (int i = 0;i < reserve.size();i++) {
        mp.insert(pair<int, int>(reserve[i], 1));
    }
    // lostArr 초기화
    for(int i =0;i < n + 1;i++) {
        lostArr.push_back(0);
    }
    // [인덱스 = 학생의 번호, 값 = 1(잃어 버림), 0(잃어 버리지 않음)
    for (int i = 0;i < lost.size();i++) {
        lostArr[lost[i]] = 1;        
    }
    // 여분이 있는데 잃어버린 학생 먼저 처리
    for (int i = 0;i < reserve.size();i++) {
        if (lostArr[reserve[i]]) {
            lostArr[reserve[i]] = 0; 
            mp[reserve[i]] = 0;
        }
    }
    // 여분 있는 학생의 앞 번호가 잃어버리면 처리 아니면 뒤 학생처리
    for (int i = 0;i < reserve.size();i++) {        
        if (mp[reserve[i]] == 1) {
            if(reserve[i] - 1 > 0 && lostArr[reserve[i] - 1] ) {
                lostArr[reserve[i] - 1] = 0;
                mp[reserve[i]] = 0;
            }
            else if(reserve[i] + 1 < n + 1 && lostArr[reserve[i] + 1]) {
                mp[reserve[i]] = 0;
                lostArr[reserve[i] + 1] = 0;   
            } 
        }        
    }    
    // 체육복을 찾지 못한 학생 count
    for(int i = 0;i < lostArr.size();i++) {    
        if (lostArr[i]) lostN++;
    }
    // 총 학생에서 체육복 찾지 못한 학생 빼기
    answer = n - lostN;
    return answer;
}

더 좋은 풀이

 students 배열을 만들어 모두 0으로 초기화 한뒤 여분을 가지고 있으면 +1 lost 면 -1 을

한 후 n만큼의 반복문을 돌며 students의 값이 -1 일때 바로 앞 students의 값이 1이면 자신과 앞의 배열 값을 0으로 만들어 주고 바로 앞 값이 1이 아닐시 바로 뒤 배열 값이 1이면 자신과 바로 뒤의 배열 값을 0으로 만들어 주는 방식으로 풀이하면 좀 더 간결하게 해결 할 수 있다.

#include <string>
#include <vector>

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

    return answer;
}