알고리즘 문제 풀어보기

행렬 테두리 회전하기

문제 설명

rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다.

x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다.
다음은 6 x 6 크기 행렬의 예시입니다.

이 행렬에 (2, 2, 5, 4) 회전을 적용하면, 아래 그림과 같이 2행 2열부터 5행 4열까지 영역의 테두리가 시계방향으로 회전합니다. 이때, 중앙의 15와 21이 있는 영역은 회전하지 않는 것을 주의하세요.

행렬의 세로 길이(행 개수) rows, 가로 길이(열 개수) columns, 그리고 회전들의 목록 queries가 주어질 때, 각 회전들을 배열에 적용한 뒤, 그 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

rows는 2 이상 100 이하인 자연수입니다.
columns는 2 이상 100 이하인 자연수입니다.
처음에 행렬에는 가로 방향으로 숫자가 1부터 하나씩 증가하면서 적혀있습니다.
즉, 아무 회전도 하지 않았을 때, i 행 j 열에 있는 숫자는 ((i-1) x columns + j)입니다.
queries의 행의 개수(회전의 개수)는 1 이상 10,000 이하입니다.
queries의 각 행은 4개의 정수 [x1, y1, x2, y2]입니다.
x1 행 y1 열부터 x2 행 y2 열까지 영역의 테두리를 시계방향으로 회전한다는 뜻입니다.
1 ≤ x1 < x2 ≤ rows, 1 ≤ y1 < y2 ≤ columns입니다.
모든 회전은 순서대로 이루어집니다.
예를 들어, 두 번째 회전에 대한 답은 첫 번째 회전을 실행한 다음, 그 상태에서 두 번째 회전을 실행했을 때 이동한 숫자 중 최솟값을 구하면 됩니다.

풀이 코드

function pushOrPop(query, arr, matrix, flag) {
    const [x1, y1, x2, y2] = query;
    for (y = y1-1, len = y2 - 1, x = x1 - 1; y <= len; y++) {
        flag ? arr.push(matrix[x][y]) : matrix[x][y] = arr.pop();
    }
    for (x = x1, len = x2 - 1, y = y2 - 1; x <= len; x++) {
        flag ? arr.push(matrix[x][y]) : matrix[x][y] = arr.pop();
    }
    for (y = y2-2, len = y1 - 1, x = x2 - 1; y >= len; y--) {
        flag ? arr.push(matrix[x][y]) : matrix[x][y] = arr.pop();
    }
    for (x = x2-2, len = x1, y = y1 - 1; x >= len; x--) {
        flag ? arr.push(matrix[x][y]) : matrix[x][y] = arr.pop();
    }
}

function solution(rows, columns, queries) {
    const answer = [];
    const matrix = [];
    let num = 1;
    for (i = 0; i < rows; i++) {
        const arr = [];
        for (j = 0; j < columns; j++) {
            arr.push(num++);
        }
        matrix.push(arr);
    }
    
    
    queries.forEach((query) => {
        const [x1, y1, x2, y2] = query;
        const arr = [];
        
        pushOrPop(query, arr, matrix, true);
        
        const newArr = arr.slice(arr.length-1).concat(arr.slice(0, arr.length-1));
        answer.push(Math.min(...newArr));
        newArr.reverse();
        
        pushOrPop(query, newArr, matrix, false);
    })
    
    return answer;
}

풀이 과정

rows, columns를 토대로 matrix라는 가변 배열을 만든다. 이후 query를 비구조할당해 구한 직사각형의 범위를 토대로 테두리에 있는 숫자를 배열에 모두 담고, 회전한 테두리의 숫자를 얻기 위해 배열의 마지막 요소를 추출해 맨 앞에 넣어준다.
움직인 숫자의 최솟값을 구해야 하므로 배열의 요소 중 가장 작읍 값을 구해 answer에 추가해주고 다음 회전으로 넘어가기전에 matrix 배열에 회전의 결과를 반영해준다.

기술면접 문제 풀어보기

18. 그래프(Graph)와 트리(Tree)를 설명하고, 둘의 차이점을 설명해주세요

그래프(Graph)

• 노드와 노드간을 연결하는 간선으로 구성된 자료구조. => 연결된 노드 간의 관계를 표현할 수 있음.
• 순환 혹은 비순환 구조를 이룸.
• 방향이 있는 그래프와 없는 그래프가 있음.
• 루트 노드의 개념이 없음. => 부모 - 자식 관계가 없음.
• 2개 이상의 경로가 가능.(무방향, 방향, 양방향 가능.)
• 네트워크 모델.

트리(Tree)

• 노드와 노드간을 연결하는 간선으로 구성된 자료구조. => 그래프와 같음.
• 그래프 중에서도 특수한 케이스에 해당하는 자료구조.
• 두 개의 노드 사이에 반드시 1개의 경로만을 가지고 사이클이 존재하지 않는 방향 그래프. => 최소 연결 트리
• 부모 - 자식 관계 성립 => 계층형 모델.
• 노드가 N개이면 간선은 N-1개, 각 레벨에 존재하는 노드는 2^k개.
• 방향성이 존재하고 사이클은 존재하지 않음.
• 전위순회, 중위순회, 후위순회 3가지 존재.

비교

	그래프	트리
방향성	방향, 무방향	방향
사이클	순환, 비순환, 자기순환	비순환
루트노드	루트 개념 x	한 개의 루트 존재
부모-자식	부모-자식 개념없음	1개의 부모노드(루트 제외)
모델	네트워크 모델	계층 모델
간선 수	자유	N-1개

최종 프로젝트

해결중인 부분

• 타워세션, 유저세션을 생성해 플레이어들을 타워 세션에 추가하고 클라이언트가 추가되면 해당 플레이어 정보를 spawn, despawn 핸들러를 이용해 기존 플레이어들에게 새로운 플레이어의 정보를 띄워줄 수 있게 구현을 했지만 정상작동을 하지 않았다.
  세션이 제대로 작동하지 않는 것 같아서 이부분을 고쳐보는 중이다.