[백준] 23305번 수강변경 (C++)

https://www.acmicpc.net/problem/23305

 

 

이 문제는 생각보다 간단한 구현문제였다. 학생들의 수 N이 주어지고

다음 줄에 학생들이 선택한 과목들이 주어지며 이후 학생들이 원하는 과목이 주어진다.

 

이때 삼자 교환을 불가하지만 두명이 교환하고 다른 사람과 교환은 가능하다. 사실 이 문항은 구현하면서 생각해보니 딱히 필요없는 문항이라고 생각하였다.

 

그렇기 때문에 한명의 학생이 자신을 제외한 모든 학생과 강의를 교환할 수 있다고 생각하였으며

강의의 종류, 개수만 기록하여 학생들이 원하는 강의가 있는경우 개수를 줄여주고 이때 남은 강의는 학생이 원하는 강의가 아니기 때문에

그 값을 출력해주었다.

 

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {0, -1, 0, 1, 1, -1, -1, 1};
int dy[] = {-1, 0, 1, 0, -1, 1, -1, 1};
int N;
int arr[1000001];
map<int, int> m;

void solve() {
    int cnt = 0;

    for(int i = 0; i < N; i++) {
        if(m.find(arr[i]) != m.end()) {
            m[arr[i]]--;
            cnt++;
            if(m[arr[i]] == 0) m.erase(arr[i]);
        }
    }

    cout << N - cnt;
}

void input() {
    cin >> N;

    for(int i = 0; i < N; i++) {
        cin >> arr[i];
    }

    for(int i = 0; i < N; i++) {
        int a;
        cin >> a;
        m[a]++;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

solve 함수를 살펴보면

void solve() {
    int cnt = 0;

    for(int i = 0; i < N; i++) {
        if(m.find(arr[i]) != m.end()) {
            m[arr[i]]--;
            cnt++;
            if(m[arr[i]] == 0) m.erase(arr[i]);
        }
    }

    cout << N - cnt;
}

이전에 학생들이 원하는 강의를 해시테이블에 기록해주었으며

 

이번 N을 순회할때 학생들이 선택한 과목을 순회한다 이때 해시맵에 존재하는 경우 이는 학생이 원하는 과목을 들을 수 있다는 것이기 때문에  계속 1씩 줄여나갔으며 0인 경우 테이블에서 삭제해주었다.

 

이후 N에서 cnt를 빼주면 학생이 원하는 강의를 수강하지 못하는 학생 수가 나온다.