스레드로 돌아가기

leetcode에서 cpp 사용 기초 - map 잘써보기

1 min#ps#leetcode#cpp
#include <vector>
#include <unordered_map>
#include <cmath>

using namespace std;

#define ll long long // 세미콜론안붙인다

class Solution {
public:
    vector<ll> distance(vector<int>& nums) {
        int n = nums.size();
        // 각 숫자의 모든 인덱스와 총합을 미리 저장
        unordered_map<int, vector<int>> groups;
        unordered_map<int, ll> total_sum_map;
        
        for (int i = 0; i < n; ++i) {
            groups[nums[i]].push_back(i);
            total_sum_map[nums[i]] += i;
        }

        // 각 숫자가 몇 번째로 등장했는지 지금까지의 인덱스 합은 얼마인지 추적
        unordered_map<int, int> count_map;
        unordered_map<int, ll> prefix_sum_map;
        vector<ll> arr;

        for (int i = 0; i < n; ++i) {
            int val = nums[i];
            ll curIdx = i;
            
            ll total_sum = total_sum_map[val]; // 현재 값에 대한 인덱스 총합
            int total_count = groups[val].size(); // 현재 값이 몇개인지?
            ll prefix_sum = prefix_sum_map[val]; // 현재 값의 누적합
            int count_so_far = count_map[val]; // 현재 인덱스 이전의 그 값 개수

            ll left = (ll)count_so_far * curIdx - prefix_sum;
            
            ll right_sum = total_sum - (prefix_sum + curIdx);
            int right_count = total_count - 1 - count_so_far;
            ll right = right_sum - (ll)right_count * curIdx;

            arr.push_back(left + right);

            prefix_sum_map[val] += curIdx;
            count_map[val]++;
        }

        return arr;
    }
};

처음엔 deque써서 회전큐같이 풀었다가 TLE나서 prefix로 선회했다. 먼저 각 숫자 nums[i]가 등장하는 모든 인덱스들의 총합 total_sum_map과 인덱스 목록 groups을 미리 저장한다.

그 다음 배열을 한 번 더 순회하며, 현재 인덱스 curIdx를 기준으로 왼쪽에 있는 같은 값들의 거리 합이랑 오른쪽 거리합을 나눠서 계산한다.

  • 왼쪽 구간: (현재까지 그 숫자가 나온 횟수) * 현재 인덱스 - (현재까지의 인덱스 누적합)
  • 오른쪽 구간: (나머지 인덱스의 합) - (나머지 등장 횟수) * 현재 인덱스

이거 나도 처음에 뇌가 돌아버릴뻔했는데, 알고보니 분배법칙이었다.

[2, 3, 7]이 있고, 현재 idx가 7이라고 해보겠다.

왼쪽에 있는 2,3과의 거리를 구하는 법?

7-2 + 7-3 이다. 보이는 지?

(왼쪽 개수 * 내 위치) - (왼쪽 인덱스들의 합) 이렇게 된다.

C++ PS 필수 문법: deque, #define, typedef

알고리즘 문제를 풀 때 코딩 속도를 높여주고, 코드를 간결하게 작성할 수 있게 돕는 유용한 문법들입니다.

1. 매크로 정의 #define

단축어를 만들 때 사용합니다. 코드 길이를 획기적으로 줄일 수 있어 C++로 PS(Problem Solving)를 할 때 즐겨 사용됩니다. 끝에 세미콜론(;)을 붙이지 않는 것에 주의하세요.

#define ll long long
#define pb push_back
#define all(v) (v).begin(), (v).end()

// 사용 예시
ll big_number = 10000000000;
vector<int> v;
v.pb(1); // v.push_back(1)과 동일

2. 별칭 지정 typedef & using

기존 자료형에 새로운 이름을 부여하는 기능입니다. 구조체나 긴 템플릿 타입을 타이핑하기 편하게 만듭니다. 요즘 Modern C++(C++11 이후)에서는 좀 더 직관적인 using을 자주 사용합니다.

// typedef 방식
typedef long long ll;
typedef pair<int, int> pii;

// using 방식 (Modern C++ 권장)
using ll = long long;
using pii = pair<int, int>;

// 사용 예시
pii my_pair = {1, 2};

3. 양방향 큐 std::deque (Double Ended Queue)

std::deque는 양쪽 끝에서 데이터 삽입과 삭제가 모두 O(1)O(1)의 시간 복잡도로 빠르게 이루어지는 자료구조입니다. 게다가 배열(Vector)처럼 중간 요소에 인덱스([])로 접근하는 Random Access도 가능해 다재다능하게 쓰입니다. (Vector는 뒤에서만 삽입/삭제 효율이 좋습니다.)

#include <deque>
#include <iostream>

using namespace std;

int main() {
    deque<int> dq;

    // 양 끝 삽입
    dq.push_back(2);    // 뒤에 2 삽입: [2]
    dq.push_back(3);    // 뒤에 3 삽입: [2, 3]
    dq.push_front(1);   // 앞에 1 삽입: [1, 2, 3]

    // 인덱스 접근 
    cout << "인덱스 1 참조: " << dq[1] << endl; // 출력: 2

    // 양 끝 삭제
    dq.pop_back();      // 뒤에서 꺼냄: [1, 2]
    dq.pop_front();     // 앞에서 꺼냄: [2]
    
    return 0;
}