[고득점Kit][그리디] 체육복 ⭐

[그리디] 체육복

난이도 ⭐

문제

내 풀이 ⭕

 #include <string>
#include <vector>

using namespace std;

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

• answer는 체육복을 입을 수 있는 사람의 수이기 때문에 총 학생 수에서 체육복을 잃어버린 학생 수를 빼준다. 일단 빌리기 전이기 때문에 answer는 이 값에서 시작한다.
• 첫 번째 for문
  • 체육복 여유분이 있는 사람이 체육복을 잃어버렸다면 그 여유분을 본인이 써야 하기 때문에 누구에게도 빌려줄 수 없다. 따라서 lost에도 속해있고 reserve에도 둘 다 속해있는 사람이 있다면 이 사람을 찾아서 제거해주어야 한다.
    • 이 사람을 찾았다면
      • lost에서도, reverse에서도 빌리는 작업을 시작하기 전에 첫 번째 for문에서 미리 이 사람을 제거해주어야 한다. 빌려야 할 필요도 빌려주어야 할 필요도 없는 사람이기 때문에!
      • answer를 증가시켜준다. lost에 속해있었긴 했지만 자신의 여유분을 쓰면 되는 사람이기 때문에 체육복을 입을 수 있는 사람이 늘어서!
      • i를 감소시켜준다. 흐아 이거때문에 왜 틀렸는지 몰랐어서 엄청 헤맸었다.
        • i를 1 만큼 감소시켜주어야 하는 이유는 erase로 제거해주었기 때문에 다음 원소가 제거된 현재 이 자리에 오기 때문이다. 따라서 i를 1 만큼 감소시켜서 새로운 원소가 오게 된 현재의 lost 위치에서부터 다시 검사해야 하기 때문에!
      • 찾았으니 더 이상 reverse를 순회하는 안쪽 for문은 더 이상 돌지 않고 break
• 두 번째 for문
  • reverse로부터 빌릴 수 있는 사람이라면 if(lost[i] - 1 == reserve[j] || lost[i] + 1 == reserve[j])
    • 빌렸으므로 answer를 증가시키고
    • 빌려준 사람을 reverse로부터 제거한다.
    • 이때 j는 증가시키지 않는다! 다음 원소가 제거된 현재 이 자리에 오기 때문에 현재 자리부터 다시 검사해야 해서.
  • 빌릴 수 없는 사람이라면 j 1 증가시켜서 잃어버린 다음 사람 검사하러 간다.

다른 분의 풀이

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

출처: 프로그래머스 (다른 사람의 풀이 중 가장 좋아요를 많이 받은 풀이다.) 정확히 어떤 분의 풀이인지는 모르겠지만 ㅠ ㅠ

비현실적이긴 하지만 만약 반에 학생이 막 만명 십만명이 넘고 잃어버린 학생 수, 여유분이 있는 학생 수도 어마어마하게 큰 수라면 내 풀이처럼 이중 for문을 사용하여 일일이 일치하는지를 검사하는 것은 시간 복잡도가 굉장히 큰 비효율적 풀이가 될 것이다. 이 풀이처럼 student라는 배열을 새로 만들어서 이 배열 딱 하나로 reserve와 lost에 속한 학생의 데이터를 나타낼 수 있게끔 합친다면 student 배열만 검사하면 되므로 반복문을 1 개만 쓸 수 있게 되어 시간 복잡도를 줄일 수 있다. 너무 좋은 풀이라고 느꼈다!

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기