오늘 한 내용

---

• C++ 코드카타
• 물리 강의 수강
• Ch3 팀 프로젝트(Stat UI 반영)

코드카타 문제

---

오늘의 코드카타 문제는 다음과 같다.
프로그래머스(연속된 부분 수열의 합) : https://school.programmers.co.kr/learn/courses/30/lessons/77485

문제를 요약하자면, 1 ~ N까지의 원소가 차례대로 배치된 N x N 배열에서 시작점과 끝점까지의 테두리 부분만 시계방향으로 회전을 한 후 회전한 원소들 중 가장 작은 원소를 반환하면 된다.

예를 들어, 3 x 3 행렬이 있다고 하자.

여기서 (1, 1) -> (3, 3)으로 회전을 한다고 하면 회전할 영역은 다음과 같다.

시계 방향으로 회전하면 다음과 같이 되고 가장 작은 원소는 1이 된다.

위 과정을 주어진 문제의 횟수 만큼 반복해야 한다.

처음 보았을 때, 정말 단순하게 그래프 문제인가 싶었지만 노드를 연결하는 것 자체가 불필요한 작업이라서 구현 문제라는 것을 인지하게 되었다.

구현 방식은 다음과 같았다.

1. 먼저, 시작 노드의 값을 임시 변수에 넣는다.
2. 이후 왼쪽 테두리 -> 아래쪽 테두리 -> 오른쪽 테두리 -> 위쪽 테두리 순으로 시계 방향으로 이동한다. 이동할 때마다 최솟값을 업데이트 한다.
3. 위쪽 테두리의 2번째 노드가 시작 노드가 시계 방향으로 이동했을 때의 값이므로, 2번째 노드에 임시 변수의 값을 넣어준다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
    vector<int> answer;
    vector<vector<int>> board(rows, vector<int>(columns));
    
    // 미리 보드 형성
    int n = 1;
    for (int i = 0; i < rows; ++i)
    {
        for (int j = 0; j < columns; ++j)
        {
            board[i][j] = n;
            n++;
        }
    }
    
    for (int i = 0; i < queries.size(); ++i)
    {
    	// 시작점, 끝점을 각각 저장한다.
        int r1 = queries[i][0] - 1;
        int c1 = queries[i][1] - 1;
        int r2 = queries[i][2] - 1;
        int c2 = queries[i][3] - 1;
        
        int temp = board[r1][c1];
        // 최솟값은 일단 임시 변수로 초기화
        int min_val = temp;
        
        // 왼쪽 테두리
        for (int i = r1; i < r2; ++i)
        {
            board[i][c1] = board[i + 1][c1];
            min_val = min(min_val, board[i][c1]);
        }
        
        // 아래쪽 테두리
        for (int i = c1; i < c2; ++i)
        {
            board[r2][i] = board[r2][i + 1];
            min_val = min(min_val, board[r2][i]);
        }
        
        // 오른쪽 테두리
        for (int i = r2; i > r1; --i)
        {
            board[i][c2] = board[i - 1][c2];
            min_val = min(min_val, board[i][c2]);
        }
        
        // 위쪽 테두리
        for (int i = c2; i > c1; --i)
        {
            board[r1][i] = board[r1][i - 1];
            min_val = min(min_val, board[r1][i]);
        }
        
        board[r1][c1 + 1] = temp;
        
        answer.push_back(min_val);
    }
    
    return answer;
}