스레드로 돌아가기

leetcode에서 cpp 사용 기초 - hashmap 사용법 추가

2 min#ps#leetcode#cpp
#include <vector>
#include <unordered_map>
#include <numeric>

using namespace std;

class Solution {
public:
    vector<int> p;

    int find(int a) {
        if (p[a] == a) return a;
        return p[a] = find(p[a]);
    }

    void union_group(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        if (pa != pb) {
            p[pa] = pb;
        }
    }

    int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
        int n = source.size();
        p.resize(n);
        iota(p.begin(), p.end(), 0);

        for (const auto& swap : allowedSwaps) {
            union_group(swap[0], swap[1]);
        }

        unordered_map<int, unordered_map<int, int>> group_counts;
        for (int i = 0; i < n; ++i) {
            int root = find(i);
            group_counts[root][source[i]]++;
        }

        int matches = 0;
        for (int i = 0; i < n; ++i) {
            int root = find(i);
            if (group_counts[root][target[i]] > 0) {
                matches++;
                group_counts[root][target[i]]--; // 사용한 숫자의 개수 차감
            }
        }

        return n - matches;
    }
};

이 문제 코드 안에서 사용된 문법을 보자.

#include <vector>
#include <unordered_map>
#include <numeric>
  • #include는 필요한 표준 라이브러리를 가져오는 전처리 지시문이다.
  • <vector>는 동적 배열 vector를 사용하기 위해 필요하다.
  • <unordered_map>은 해시맵 unordered_map을 사용하기 위해 필요하다.
  • <numeric>은 iota 같은 수열 관련 함수를 사용하기 위해 필요하다.

이 코드에서는:

  • vector<int>로 부모 배열 p를 만든다.
  • unordered_map으로 그룹별 숫자 개수를 센다.
  • iota로 부모 배열을 0, 1, 2, ...로 초기화한다.

예시:

#include <vector>
#include <iostream>

using namespace std;

int main() {
    vector<int> nums = {1, 2, 3};
    cout << nums[0] << endl; // 1
}

using namespace std;: std:: 생략

using namespace std;
  • C++ 표준 라이브러리의 대부분은 std 네임스페이스 안에 있다.
  • 원래는 std::vector, std::unordered_map, std::cout처럼 써야 한다.
  • using namespace std;를 쓰면 std::를 생략할 수 있다.

예시:

#include <iostream>

using namespace std;

int main() {
    cout << "hello" << endl;
}

class: 사용자 정의 타입

class Solution {
public:
    vector<int> p;
    ...
};
  • class는 변수와 함수를 하나로 묶는 사용자 정의 타입이다.
  • LeetCode에서는 보통 Solution 클래스를 만들고 그 안에 풀이 함수를 넣는다.
  • { ... } 안에 멤버 변수와 멤버 함수를 정의한다.
  • 마지막 ;까지 있어야 클래스 정의가 끝난다.

예시:

class Person {
public:
    int age;

    void say_age() {
        cout << age << endl;
    }
};

public:: 접근 지정자

public:
  • public 아래의 멤버는 클래스 바깥에서도 접근할 수 있다.
  • class는 기본 접근 제한자가 private이기 때문에, 외부에서 호출할 함수는 보통 public: 아래에 둔다.

예시:

class A {
public:
    int x;
};

int main() {
    A a;
    a.x = 10;
}

vector<int> p;: 템플릿 자료형과 멤버 변수 선언

vector<int> p;
  • vector<int>는 int를 담는 가변 길이 배열이다.
  • <int>는 템플릿 인자로, 벡터가 어떤 타입을 저장하는지 뜻한다.
  • p는 클래스의 멤버 변수다.

일단 나는 처음에 배열을 선언해서 쓱려고했는데 벡터가 맞나보다.

예시:

vector<int> arr;
arr.push_back(5);
arr.push_back(9);
cout << arr[1] << endl; // 9

함수 정의: 반환형, 함수명, 매개변수

int find(int a) {
  • int는 반환형이다.
  • find는 함수 이름이다.
  • (int a)는 int 타입 매개변수 a를 받는다는 뜻이다.

예시:

int add(int a, int b) {
    return a + b;
}

void: 반환값이 없는 함수

void union_group(int a, int b) {
  • void는 반환값이 없다는 뜻이다.
  • union_group은 두 그룹을 합치는 역할만 하므로 값을 돌려줄 필요가 없다.

예시:

void print_hello() {
    cout << "hello" << endl;
}

지역 변수 선언과 초기화

int pa = find(a);
int pb = find(b);
int n = source.size();
int matches = 0;
  • 함수 안에서 선언한 변수는 지역 변수다.
  • 선언과 동시에 =로 초기화할 수 있다.

예시:

int x = 10;
int y = x + 5;

인덱싱 []

p[a]
swap[0]
source[i]
target[i]
group_counts[root][source[i]]
  • []는 배열, vector, unordered_map 등에서 원소에 접근할 때 쓴다.
  • vector에서는 인덱스로 접근한다.
  • unordered_map에서는 키로 접근한다.

예시 1:

vector<int> v = {10, 20, 30};
cout << v[1] << endl; // 20

예시 2:

unordered_map<string, int> mp;
mp["apple"] = 3;
cout << mp["apple"] << endl; // 3

참고:

  • unordered_map에서 mp[key]를 쓰면 key가 없을 때 기본값으로 새 원소가 만들어질 수 있다.
  • 그래서 group_counts[root][target[i]]도 키가 없으면 0부터 시작한다.

참조자 &: 원본을 직접 가리키기

vector<int>& source
vector<int>& target
vector<vector<int>>& allowedSwaps
  • &는 참조자다.
  • 복사본이 아니라 원본을 직접 가리킨다.
  • 큰 vector를 함수 인자로 넘길 때 복사를 피할 수 있어서 효율적이다.

예시:

void add_one(int& x) {
    x++;
}

int main() {
    int n = 3;
    add_one(n);
    cout << n << endl; // 4
}

중첩 템플릿

vector<vector<int>>& allowedSwaps
unordered_map<int, unordered_map<int, int>> group_counts;
  • 템플릿 안에 또 다른 템플릿을 넣을 수 있다.
  • vector<vector<int>>는 2차원 배열처럼 볼 수 있다.
  • unordered_map<int, unordered_map<int, int>>는 "정수 -> 또 다른 해시맵" 구조다.

이 코드에서는:

  • 바깥 키: 그룹 루트
  • 안쪽 키: 숫자 값
  • 안쪽 값: 해당 숫자의 개수

예시:

vector<vector<int>> grid = {
    {1, 2},
    {3, 4}
};

cout << grid[1][0] << endl; // 3

멤버 함수 호출과 . 연산자

source.size()
p.resize(n)
p.begin()
p.end()
  • .은 객체의 멤버에 접근할 때 쓰는 연산자다.
  • size(), resize(), begin(), end()는 vector의 멤버 함수다.

각 함수의 의미:

  • size(): 원소 개수 반환
  • resize(n): 크기를 n으로 변경
  • begin(): 시작 위치 반복자
  • end(): 마지막 다음 위치 반복자

예시:

vector<int> v = {1, 2, 3};

cout << v.size() << endl; // 3
v.resize(5);
cout << v.size() << endl; // 5

iota(...): 연속된 값 채우기

iota(p.begin(), p.end(), 0);
  • iota(first, last, start)는 [first, last) 구간을 start, start + 1, start + 2... 로 채운다.
  • 여기서는 p를 {0, 1, 2, ..., n - 1}로 초기화한다.
  • Union-Find에서 "처음에는 모든 원소의 부모가 자기 자신"이어야 해서 자주 쓰인다.

예시:

vector<int> v(5);
iota(v.begin(), v.end(), 10);

// 결과: {10, 11, 12, 13, 14}

const auto&: 타입 추론 + 읽기 전용 참조

const auto& swap

이 표현은 세 부분으로 나눠서 보면 쉽다.

  • auto: 타입을 컴파일러가 자동으로 추론
  • &: 복사하지 않고 참조로 받음
  • const: 읽기만 하고 수정은 못 함

즉, allowedSwaps의 각 원소를 "복사 없이, 수정하지 않는 참조"로 받는 문법이다.

예시:

vector<string> words = {"aa", "bb", "cc"};

for (const auto& word : words) {
    cout << word << endl;
}

위 예시에서 word의 실제 타입은 const string&로 추론된다.

unordered_map

unordered_map<int, unordered_map<int, int>> group_counts;
  • unordered_map<Key, Value>는 해시 기반 딕셔너리다.
  • 평균적으로 삽입과 조회가 빠르다.
  • 파이썬의 dict와 비슷하게 생각하면 된다.

이 코드에서는:

  • group_counts[root]는 특정 그룹의 숫자 개수표다.
  • group_counts[root][value]는 그 그룹에서 value가 몇 번 나왔는지 의미한다.

예시:

unordered_map<int, int> count;

count[5]++;
count[5]++;
count[2]++;

cout << count[5] << endl; // 2
cout << count[2] << endl; // 1