[프로그래머스] Lv2. 행렬 테두리 회전하기

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

프로그래머스

 

문제

일단, 위 문제 설명만을 읽었을 때 한번에 이해되지 않았다.
아래의 예시를 통해 쉽게 이해할 수 있었다.

 

예시

 

위의 왼쪽 예시는 rows와 columns가 각각 6, 6으로 주어졌을 때의 초기 행렬의 모습이다.

이때, queries도 함께 주어지는데, queries의 첫 번째 요소인 [2, 2, 5, 4] 리스트를 적용했을 때의 예시이다.

[2, 2, 5, 4] 리스트의 의미는 직사각형의 범위를 지정할 때 왼쪽 위의 꼭짓점을 (2,2)로 정하고 오른쪽 아래의 꼭짓점을 (5,4)로 정한다는 의미이다.

이렇게 정해진 직사각형 범위 내에서 테두리에 있는 숫자들을 시계 방향으로 회전 시켜주고, 테두리 숫자들 중 가장 최솟값들을 포함하는 리스트를 결과값으로 반환하는 문제이다.

 

제한 사항

알고리즘 문제를 풀 때, 제한사항을 자세히 읽는 것이 중요하다는 것을 느꼈다. 제한 사항에는 푸는 사람들이 고민할 수 있는 부분을 해소시켜주는 범위나 공식 등이 제공될 수 있기 때문이다.

• 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입니다.
  • 모든 회전은 순서대로 이루어집니다.
  • 예를 들어, 두 번째 회전에 대한 답은 첫 번째 회전을 실행한 다음, 그 상태에서 두 번째 회전을 실행했을 때 이동한 숫자 중 최솟값을 구하면 됩니다.

여기서는 i 행 j 열에 있는 숫자의 공식을 알려주거나, 모든 회전은 순서대로 이루어진다는 전제 등을 통해 문제를 좀 더 쉽게 해결할 수 있었다.

 

 

슈도 코드

문제를 이해하면서 어떻게 코드를 작성해야 할 지 슈도 코드를 작성해 보았다.

1. 일단 rows와 columns를 바탕으로 1씩 증가하는 행렬을 만든다.

2. queries의 요소들을 순회한다.

3. 반복문 내에서 요소를 바탕으로 시계 방향으로 회전한다.

3-1. 이전 값을 이후 값에 대입한다.

3-2. 최소값을 구하기 위해 회전한 값들을 넣는다.

4. 최소값을 반환한다.

 

해결

 

1씩 증가하는 2차원 배열 만들기

먼저 rows와 columns를 통해 1씩 증가하는 2차원 배열을 만들고자 하였다.

 

시계 방향으로 회전하기

값을 옮기는 부분과 시계 방향으로 회전하는 부분은 동시에 일어나야 하지만 일단 시계 방향으로 회전하는 방식을 설계하기 위해 구분해서 생각하였다.

for x1,y1,x2,y2 in queries:

    min_x = x1-1
    min_y = y1-1
    
    max_x = x2-1
    max_y = y2-1
    
    
    curr_x = min_x
    curr_y = min_y

    while 1:
        if curr_x == min_x and curr_y < max_y:
            # 오른쪽으로 이동
            curr_y += 1
        elif curr_x < max_x and curr_y == max_y:
            # 아래로 이동
            curr_x += 1
        elif curr_x == max_x and curr_y > min_y:
            # 왼쪽으로 이동
            curr_y -= 1
        elif curr_x > min_x and curr_y == min_y:
            # 위로 이동
            curr_x -= 1
        
        if curr_x == min_x and curr_y == min_y:
            break

현재 좌표 curr_x, curr_y가 처음 min_x, min_y 값을 시작으로 오른쪽, 아래쪽, 왼쪽, 위쪽 순서로 이동하도록 분기 처리를 하였고, curr_x, curr_y가 처음 min_x, min_y 값으로 되돌아 갈 때, while문이 끝나도록 하였다.

 

값 옮기기

값을 옮기는 메커니즘을 생각하는 것에 생각보다 시간이 걸렸다. 일반적으로 두 변수의 값을 변경하기 위해 사용하는 방법에는 두 변수 사이에 temp 변수를 하나 두어 값을 넘길 때 임시로 temp에 저장해두는 방식이 있다. 이를 사용해 보았다.

while 1:
        temp = arr[curr_x][curr_y]
        if curr_x == min_x and curr_y < max_y:
            # 오른쪽으로 이동
            curr_y += 1
        elif curr_x < max_x and curr_y == max_y:
            # 아래로 이동
            curr_x += 1
        elif curr_x == max_x and curr_y > min_y:
            # 왼쪽으로 이동
            curr_y -= 1
        elif curr_x > min_x and curr_y == min_y:
            # 위로 이동
            curr_x -= 1
        
       	arr[curr_x][curr_y] = temp
        
        if curr_x == min_x and curr_y == min_y:
            break

현재 좌표는 시계 방향으로 이동하고, 이전의 값을 담아 좌표가 변경되었을 때, 이전의 값을 넣으면 될거라고 직관적으로 적은 코드이다. 이렇게 넣어봤더니 당연히 실패한다. 처음 시작된 좌표의 값으로 전부 채워질 것을 예상할 수 있을 것이다. 이를 해결하기 위해 하나의 변수를 추가로 두어서 생각해보았다.

    before = 0
    after = arr[curr_x][curr_y]
    
    while 1:
        before = after  # 이 값을 다음 값에 넣어야 함.
        if curr_x == min_x and curr_y < max_y:
            # 오른쪽으로 이동
            curr_y += 1
        elif curr_x < max_x and curr_y == max_y:
            # 아래로 이동
            curr_x += 1
        elif curr_x == max_x and curr_y > min_y:
            # 왼쪽으로 이동
            curr_y -= 1
        elif curr_x > min_x and curr_y == min_y:
            # 위로 이동
            curr_x -= 1
        
        after = arr[curr_x][curr_y]
        arr[curr_x][curr_y] = before
        
        trace.append(before) 

        if curr_x == min_x and curr_y == min_y:
            break

처음 before 변수에 시작 좌표를 넣어야 하기 때문에 before 변수에 arr[curr_x][curr_y]를 넣고 시작해야한다고 생각할 수 있지만, 해당 반복문을 보면 처음에 before에 after 값을 대입하는 부분이 있다. 이를 통해 시작 좌표부터 시작할 수 있다.

또한, after는 좌표가 변경된 후의 값을 얻고, before를 변경된 좌표에 이전 값을 넣게 되므로 정상적으로 값들이 들어가는 것을 알 수 있다.

2개의 변수를 사용하는 방식이외에도 값을 넣는 순서를 다르게 하여 이를 해결하는 방법도 있다. 이는 다른 블로그를 참조하여 소개하겠다.