[프로그래머스 C++] 테이블 해시 함수

[프로그래머스 C++] 테이블 해시 함수

 

https://school.programmers.co.kr/learn/courses/30/lessons/147354

프로그래머스

---

 

해결전략

 

정렬

누적 합계

비트 연산

 

---

 

정답 코드

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// 행 번호, (문제에서 col로 주어진)특정 열의 값, 첫 번째 열의 값을 저장하는 구조체
struct Value {
    int rowNum; int colVal; int firstVal;

    // Value의 생성자. 행 번호, 특정 열의 값, 첫 번째 열의 값을 초기화한다.
    Value(int a, int b, int c) {
        rowNum = a;
        colVal = b;
        firstVal = c;
    }

    // 연산자 오버로딩을 통해 < 연산자를 정의
    // 주어진 열의 값이 같을 경우 첫 번째 열의 값으로 비교하고, 그렇지 않을 경우 주어진 열의 값으로 비교한다
    bool operator<(const Value& oper) const
    {
        if (colVal == oper.colVal) {
            return firstVal > oper.firstVal;
        }

        return colVal < oper.colVal;
    }
};

vector<Value> order; // 행, col번째 값, 첫번째 컴럼의 값을 저장하는 벡터

int solution(vector<vector<int>> data, int col, int row_begin, int row_end) {
   
    int r = data.size(); // 행 크기
    int c = data[0].size(); // 열 크기
    
    // 각 행에 대해 '1.해당 행'의 '2.(문제에서 주어진 col)특정 열의 값'과 '3.첫 번째 열의 값'을 Value 객체로 저장하고 이를 order 벡터에 추가
    for (int i = 0; i < r; i++) {
        order.push_back({ i, data[i][col-1], data[i][0] });
    }
    
    sort(order.begin(), order.end()); // order 벡터를 정렬. 정렬 기준은 Value 객체의 < 연산자에 의해 결정됨.


    int answer = 0; // 결과를 저장할 변수
    for (int i = row_begin; i <= row_end; i++) // 문제에서 주어진 행 범위
    {
        int temp = 0;
        for (int j = 0; j < c; j++) { // 해당 행의 모든 원소에 대해
            temp += (data[order[i-1].rowNum][j] % i); // 원소 값을 해당 행 번호로 나눈 나머지를 더함
        }
        
        answer = answer ^= temp; // 결과값에 temp를 XOR 연산
    }

    return answer;
}

int main() {
    vector<vector<int>> testdata = { {2,2,6}, {1,5,10}, {4,2,9}, {3,8,3} };
    int test_col = 2;
    int test_row_begin = 2;
    int test_row_end = 3;

    solution(testdata, test_col, test_row_begin, test_row_end);

    return 0;
}

 

 

 

주의할 점

문제에서 

• 1 ≤ data[i][j] ≤ 1,000,000
  • data[i][j]는 i + 1 번째 튜플의 j + 1 번째 컬럼의 값을 의미합니다.

라고 주어졌기 때문에 0이 아닌 1부터다

 

    for (int i = 0; i < r; i++) {
        order.push_back({ i, data[i][col-1], data[i][0] });
    }

	// ...
    
    for (int i = row_begin; i <= row_end; i++) // 문제에서 주어진 행 범위
    {
        int temp = 0;
        for (int j = 0; j < c; j++) { // 해당 행의 모든 원소에 대해
            temp += (data[order[i-1].rowNum][j] % i); // 원소 값을 해당 행 번호로 나눈 나머지를 더함
        }
        
        answer = answer ^= temp; // 결과값에 temp를 XOR 연산
    }

 

나는 배열의 시작이 0부터이니 아래와 같이 -1를 해주어야 했다.

• data[ i ][ col - 1 ]
• data[ order[ i - 1 ].rowNum][ j ]

 

---

 

정답 코드 - 더 깔끔한 버전

 

#include <vector>
#include <algorithm>
using namespace std;

int Col = 0;

bool Compare(const vector<int>& a, const vector<int>& b) {
    if (a[Col] == b[Col])
        return a[0] > b[0];

    return a[Col] < b[Col];
}

int solution(vector<vector<int>> data, int col, int row_begin, int row_end) {
    
    Col = col - 1; // 문제는 0이 아닌 1부터 시작이기 때문에 -1

	sort(data.begin(), data.end(), Compare); // 문제 조건에 맞게 정렬

    int answer = 0;
    for (int i = row_begin; i <= row_end; i++) 
    {
        int temp = 0;
        for (int j = 0; j < data[0].size(); j++) {
            temp += data[i - 1][j] % i; // mod 연산
        }
        answer = answer ^ temp; // XOR 연산
    }

    return answer;
}

 

 

 

---