[Codejam][2020][QR] 1. Vestigium

문제 : https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/000000000020993c

---

Vestigium은 라틴어로 trace를 의미한다.

정사각형 행렬(let, arr)의 trace는 arr[i][i](왼쪽 위에서 오른쪽 아래까지의 요소들) 의 합이다.

정사각형 행렬이 주어질 때, trace의 값과 중복되는 요소가 있는 행, 열의 수를 각각 구해라.

예를 들어, 

2 1 3

1 3 2

1 2 3

행렬이 주어지면 trace 값은 2 + 3 + 3 = 8.

중복되는 요소가 있는 행의 수는 0.

중복되는 요소가 있는 열의 수는 1열, 3열이 있으므로 2를 출력한다.

---

trace값은 i = [0, N)을 탐색하면서 arr[i][i]의 합을 구한다.

이제 arr 배열을 탐색하면서 행, 열의 요소들을 저장하는 set을 각각 채운다.

탐색 시 set에 이미 해당 값이 있다면 정답을 1씩 더해준다.

for (int i = 0; i < N; i++) {
    // 이미 정답에 추가한 행, 열을 또 추가하면 안되므로 정답에 추가했는지 flag를 하나 준비.
    findR = false; 
    findC = false;
	
    // i행, i열이 정답이 가능한지 확인하기 위한 set.
    // 탐색한 배열 요소값을 추가한다.
    set<int> rSet, cSet; 
    for (int j = 0; j < N; j++) {
        // 열이 정답에 추가되지 않았을 때, arr[j][i]가 열에 있는지 확인
        if (!findR && rSet.find(arr[j][i])!= rSet.end()) {
            findR = true; c++; // 정답에 추가
        }
        // 행이 정답에 추가되지 않았을 때, arr[i][j]가 행에 있는지 확인
        if (!findC && cSet.find(arr[i][j]) != cSet.end()) {
            findC = true; r++; // 정답에 추가
        }
        
        // 탐색한 요소 값을 set에 추가.
        rSet.insert(arr[j][i]);
        cSet.insert(arr[i][j]);
	}
}

시간복잡도는 모든 배열을 탐색하는데 드는 시간인 O(N^2)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/codejam/2020/QR/1.%20Vestigium.cpp