C++ 체육복(프로그래머스)

프로그래머스_체육복

https://programmers.co.kr/

 

탐욕법(Greedy)

문제 해석

 

이 문제를 풀기위해 이해해야 할 내용은 다음과 같습니다.

 

목표

체육복을 가지고 체육수업을 들을 수 있는 학생의 최대값 구하기

​

방법

1. 자신의 바로 앞번호 또는 뒷번호의 학생에게만 체육복을 빌릴수 있다.

2. 여벌의 사람도 도난당했을 수 있다

 

결과

체육복을 가지고 체육수업을 들을 수 있는 학생의 최대값 출력

 

1. 통과하지 못한 코드

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < lost.size(); j++)
        {
            if (lost[j] > i)
            {
                answer++;
                break;
            }
            else if (lost[j] == i)
            {
                for ( int k = 0; k < reserve.size(); k++)
                {
                    if (reserve[k] == 0)
                        continue;
                    if (lost[j] == reserve[k])
                    {
                        answer++;
                        reserve[k] = 0;
                        lost[j] = 0;
                        break;
                    }
                    
                    if (reserve[k]-1== lost[j])
                    {
                        answer++;
                        reserve[k] = 0;
                        lost[j] = 0;
                        break;
                    }
                    else if (reserve[k] +1== lost[j])
                    {
                        answer++;
                        reserve[k] = 0;
                        lost[j] = 0;
                        break;
                    }
                    
                }
            }
        }
    }
    answer = answer + n - lost[lost.size() - 1]-1;
    return answer;
}

가독성도 없고 몇번을 실패하면서 수정하다보니 내가 짠 코드도 헷갈리게 되었다

 

answer 처리방법

1. 현재 학생 index가 lost배열의 값보다 작으면 증가

2. lost 배열값과 현재 index가 같은 경우 reserve의 앞뒤를 확인하여 같으면 증가

   2-1. lost와 reserve를 다음 index에서 처음부터 또 돌기 때문에 중복으로 증가하지 않기위해 0으로 변경

3. 모든 lost 배열 탐색 후 lost 끝값부터 n까지 증가

 

-> 주어진 테스트 값과 내가 추가하면서 테스트 한 결과는 맞았지만 제출 시 실패

-> lost와 reserve값을 중간에 바꿔버리니 다음 학생 index를 확인할때 뭔가 로직이 꼬여서 실패한걸로 보인다.(재현은 실패)

 

 

2. 통과한 코드

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    vector<int> student(n, 1);
    for (int i = 0; i < lost.size(); i++)
    {
        student[lost[i] - 1]--;
    }
    for (int i = 0; i < reserve.size(); i++)
    {
        student[reserve[i] - 1]++;
    }
    for (int i = 0; i < student.size(); i++)
    {
        if (student[i] == 0)
        {
            if (i != n - 1 && student[i + 1] == 2)
            {
                student[i]++;
                student[i+1]--;
            }
            else if (i != 0 && student[i - 1] == 2)
            {
                student[i]++;
                student[i - 1]--;
            }
        }
    }
    for (int i = 0; i < student.size(); i++)
    {
        if (student[i] > 0)
            answer++;
    }
    return answer;
}

코드가 눈으로 쭉 읽힌다..

 

answer 처리방법

1. student라는 vector를 하나 추가(1로 세팅)

2. lost값 위치의 값들을 0으로 변경

3. reserve값 위치의 값들을 2으로 변경

4. 0인 위치에서 앞뒤로 확인하여 2인경우 둘다 1로 만들어준다

5. 마지막에 student를 순회하여 0보다 큰경우 answer를 증가시켜 최대값을 구한다.

 

 

실패한 이유(후기)

최대값이나 최소값을 구하는 문제는 대부분 재귀나 탐색하여 처리하는 경우가 많다(DP 등..)

다른 자료구조를 추가하여 관리할 생각을 안하고 원본을 동적으로 변경하다 보니 코드도 더러워지고 가독성도 떨어지며 원하는 결과를 출력하지도 못하였다.

예전에 DP를 풀때는 자료구조를 추가해서 했었는데 오랜만에 하다보니 생각도 못하고 풀어버렸다.

다시 머리에 각인을!!