문제 출처

회고

  • 작년 하반기에 면접을 다니면서 알고리즘은 꾸준히 풀이했지만,
  • 알고리즘 블로그를 소홀히 하게 된 거 같다.
  • 오늘부터 꾸준히 포스팅을 해보고자 한다!

1. 문제설명

  • 어떤 데이터베이스가 주어진다.
    • 크기는 최대 2500*500
    • 원소는 백만을 넘지 않는다.
  • 다른 입력으로는
    • 컬럼의 번호를 의미하는 col
    • 해시값 반환을 위한 범위 row_begin, row_end
  • 프로세스
    • col번째(즉, 각 행의 col번째) 값을 이용해 정렬한다.
      • col번째 값을 기준으로 각 행을 오름차순 정렬
      • col번째 값이 같다면 0번째 컬럼의 값을 기준으로 내림차순 정렬
    • row_begin ~ row_end 까지의 행을 행 번호로 나눈 값을 더한다.
    • 더한 값을 순차적으로 XOR 연산 한다.
  • 문제 분류
    • Implementation, Sorting, Simulation


2. 알고리즘 설계

  • 정렬 기준 구현
    • 문제에 나온대로,
    • col 값이 같을 때는 내림차순
    • 다를 때는 0번째를 기준으로 정렬
bool compare(vector<int>& v1, vector<int>& v2) {
    if(v1[target] == v2[target])
        return v1[0] > v2[0];
    return v1[target] < v2[target];
}
  • 정렬된 테이블에서 row_begin부터 row_end 행까지 각 행을 더해준다.
  • 그리고 XOR(^) 연산


3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

int target;

bool compare(vector<int>& v1, vector<int>& v2) {
    if(v1[target] == v2[target])
        return v1[0] > v2[0];
    return v1[target] < v2[target];
}

int solution(vector<vector<int>> data, int col, int row_begin, int row_end) {
    int answer = 0;
    target = col - 1;
    
    sort(data.begin(), data.end(), compare);
    
    for(int i=row_begin; i<=row_end; i++) {
        int cur = 0;
        for(int nxt : data[i-1])
            cur += nxt % i;
        answer ^= cur;
    }
    
    return answer;
}


4. 소감

  • 문제 자체는 구현 난이도가 그닥 높지 않았다.
  • 현재 구현에서는 compare 함수에서 사용되는 값을 전역으로 선언하였다.
  • 만약, compare 함수를 여러개 선언한다면 전역 변수는 좋은 선택이 아닐 것이다.
  • 방법을 찾아보고 포스팅 내용에 추가해보도록 하겠다.


5. compare 함수

  • 내가 원한 compare 함수의 이름은 bool compare(vector<int>& a, vector<int>& b, int val)과 같은 형태이다.
  • 그러나, bool cmp(const Type1& a, const Type2& b); 다음 함수 이름을 유지해야 한다.
  • 떠오른 방법은 벡터의 앞이나 끝부분에 val을 삽입하여 사용하면 될 거 같다.
    • if(a[0] == b[0])과 같은 형태로…