[알고리즘 C++] 나머지 한 점

https://programmers.co.kr/learn/courses/18/lessons/1878https://programmers.co.kr/learn/courses/18/lessons/1878

항상 JAVA로 알고리즘 문제를 풀다 C++로의 풀이를 시작하게 되었다.

그 참에 프로그래머스 문제를 차근차근 풀어보려 한다.

오늘의 문제

나머지 한 점

나의 풀이

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

vector<int> solution(vector<vector<int> > v) {
    vector<int> ans;
    
    vector<int> x;              // x 좌표 벡터
    vector<int> y;              // y 좌표 벡터
    for(int i=0;i<3;i++){       // 벡터에 각각 추가
        x.push_back(v.at(i).at(0));
        y.push_back(v.at(i).at(1));
    }
    sort(x.begin(), x.end());   // 순서대로 정렬
    sort(y.begin(), y.end());
    
    if(x.at(0) == x.at(1))      // 인덱스 0, 1 값이 같으면 2가 답이겠고
        ans.push_back(x.at(2));
    else                        // 같지 않으면 0이 답을것임
        ans.push_back(x.at(0));
    
    if(y.at(0) == y.at(1))      // 위와 동일
        ans.push_back(y.at(2));
    else
        ans.push_back(y.at(0));
    
    return ans;
}

모범 답안

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

vector<int> solution(vector<vector<int> > v) {
    vector<int> ans = {0,0};
    for(int i=0; i<3; i++)
    {
        ans[0] ^= v[i][0]; // XOR 비트연산 사용
        ans[1] ^= v[i][1];
    }
    return ans;
}

배울 점

XOR을 쓰는것은 생각도 못했다. 그 김에 비트연산 정리

1. AND(&): 둘 다 1일 경우 1
2. OR(|): 둘 중 하나라도 1일 경우 1
3. NOT(~): 1이면 0, 0이면 1
4. XOR(^): 같으면 0, 다르면 1
5. L_shift(<<): 정수일 경우 2배
6. R_shift(>>): 정수일 경우 1/2배

=> int result = A ^ B ^ C 를 하면 결국 다른 숫자가 저장이 되는 것
** 추가로 XOR 연산은 교환, 결합 법칙이 성립하여 생각하기가 좋다