[Programmers]#Level1_체육복, map, prev(), next()

 

[Programmers 알고리즘, C++]#Level 1_체육복

 

Programmers 알고리즘 문제 풀이, Level1_체육복

C++의 STL에서 제공하는 map 컨테이너를 활용하는 문제

 

---

 

Overview

 

1. 문제
2. 풀이
3. 코드

 

#1. 문제

 

#2. 풀이

1. map

[Basic C++] #38_map, 연관 컨테이너

 

• [정의] : C++의 STL에서 제공하는 map 컨테이너는, 지정된 형식의 키와 데이터 값을 한 쌍으로 저장하는 연관 컨테이너입니다. map 컨테이너는 균형 이진트리(레드-블랙 트리)로 구현되었으며, 원소의 삽입/제거 순서와 상관없이 항상 정렬된 상태를 유지하는 컨테이너입니다. 

 

2. map과 반복자

#include <iostream>
#include <map>
#include <iterator>

int main() {
    std::map<int, std::string> m;

    // 원소 삽입
    m.insert({1, "Apple"});
    m.insert({2, "Banana"});
    m.insert({3, "Cherry"});
    m.insert({4, "Date"});
    m.insert({5, "Elderberry"});

    auto it = m.find(3); // Cherry를 가리키는 반복자를 얻음

    if (it != m.end()) {
        auto prev_it = std::prev(it); // it의 이전 원소를 가리키는 반복자를 얻음
        auto next_it = std::next(it); // it의 다음 원소를 가리키는 반복자를 얻음
        
        std::cout << "Current: " << it->second << std::endl;
        std::cout << "Previous: " << prev_it->second << std::endl;
        std::cout << "Next: " << next_it->second << std::endl;
    }

    return 0;
}

 

Details

 

• [prev()와 next()] : prev()와 next() 함수는 반복자를 인자로 전달 받아, 각각 현재 반복자가 가리키는 위치의 이전 위치 그리고 다음 위치를 가리키는 반복자를 반환합니다.

 

3. 양 옆에 위치한 학생들의 체육복 소지 여부

1. 먼저, 학생의 번호와 체육복 개수를 pair로 묶어 map 컨테이너에 삽입합니다. map 컨테이너는 항상 내부적으로 정렬된 상태를 유지하며, 학생 번호 기준 오름차순으로 정렬됩니다.
2. 다음으로, reserve 목록에 포함된 학생들의 체육복 갯수를 증가시키고, lost 목록에 포함된 학생들의 체육복 개수를 감소시킵니다.
3. 마지막으로, map을 순회하며 현재 위치의 학생이 체육복이 없을 경우, 인접한 한 명 혹은 두 명의 학생의 체육복 개수여부를 확인하고 현재 번호의 학생이 수업을 들을 수 있을지 판단합니다.

 

#3. 코드

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

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int ans = 0;
    
    // #0. map : pair< 인덱스, 체육복 갯수 >
    map<int, int> m;
    for(int i=1; i<=n; i++)
    {
        m.insert({i, 1});
    }
    // #1. reserve 목록의 인덱스에 +1
    for(int i=0; i<(int)reserve.size(); i++)
        m[reserve[i]]++;
    
    // #2. lost 목록의 인덱스에 -1
    for(int i=0; i<(int)lost.size(); i++)
        m[lost[i]]--;

    for(auto it = begin(m); it != end(m); it++)
    {
        // #1. 첫 번째 학생
        if(it == begin(m))
        {
            // #1. 체육복이 1개 이상일 경우, ans++
            if(it->second >= 1)
            {
                ans++;
            }
            // #2. 체육복이 없지만, 오른쪽 학생이 2개 이상일 경우, ans++
            else
            {
                if(next(it)->second >= 2)
                {
                    next(it)->second--;
                    ans++;
                }
            }
        }
        // #2. 마지막 학생
        else if(next(it) == end(m))
        {
            // #1. 체육복이 1개 이상일 경우, ans++
            if(it->second >= 1)
            {
                ans++;
            }
            // #2. 체육복이 없지만, 왼쪽 학생이 2개 이상일 경우, ans++
            else
            {
                if(prev(it)->second >= 2)
                {
                    ans++;
                }
            }
        }
        // #3. 두 번째 ~ 마지막 직전 학생 경우, 오른쪽 왼쪽 둘다 확인
        else
        {
            // #1. 체육복이 1개 이상일 경우, ans++
            if(it->second >= 1)
            {
                ans++;
            }
            // #2. 체육복이 없을 경우
            else
            {
                // #1. 왼쪽 학생이 체육복 2개 이상일 경우
                if(prev(it)->second >= 2)
                {
                    ans++;
                    continue;
                }
                // #2. 오른쪽 학생이 체육복 2개 이상일 경우
                if(next(it)->second >= 2)
                {
                    next(it)->second--;
                    ans++;
                }
            }
        }
    }
    
    return ans;
}