n^2 배열 자르기 [프로그래머스]

문제 풀이 정리

문제 이미지 복붙

 

문제를 머리속에 집어넣어놓고 풀진 않고 언젠간~ 하면서 지내다가

회사에서 점심 먹고 쉬는와중에 끄적이다 풀었다. (진짜 아무 생각없이 써보다가!)

문제 움짤을 보면 좀더 이해하기 쉽지만 다시 써보자면

1. 입력으로 주어지는 n 숫자 ⇒ n * n 행렬을 만든다.
2. 숫자를 채워넣는다. (위 움짤처럼)
3. 행렬을 1*n^2의 배열로 재배치한다.(한줄로 쭈르륵 줄세운다고 보면 된다.)
4. 입력으로 주어지는 left ~ right 까지의 index에 써진 숫자를 반환한다.

얼핏 생각하면 1~4 단계를 구성해 숫자를 채워넣은뒤, 행렬을 차례대로 지나면서 써져있는 숫자를 반환하면 될 것 같지만 문제에서 주어지는 n의 숫자가 매우 컸다.

(n이 커지면 n*n행렬을 만든뒤 숫자를 쓰는 것도 시간이 오래걸릴것...)

"그렇다면 1~4단계를 통해 구성하는 방법이 아니고 다른 트릭이 있을것이다. "

까지가 맨 처음 문제를 보고 난 뒤 생각이였다.

풀이를 써보자면,

끄적이면서 알아낸 것은 규칙은 두가지 이다.

1. 행렬을 좌표로 나타낸 뒤, row 와 column의 숫자를 비교해 같거나 큰쪽의 좌표값 + 1이 해당 칸에 써지는 숫자라는 규칙을 발견했다.

   

   1번째 규칙 그림 설명

2. 재배열시 칸의 차례를 n진수로 변환하면 그대로 행렬의 좌표로 표현 될 수 있다.

   

   2번째 규칙 그림 설명

위 두가지 규칙은 무엇을 의미하고 앞서 문제 푸는 방법의 단계와 어떻게 다른지 보자.

2번째 규칙을 통해 우리는 left~right 값으로 들어오는 숫자는 행렬의 어디 칸에 위치하는지 단번에 찾을 수 있다.

(ex. 4 → 10(3진수로 표현) → 말그대로 행렬의 1,0 위치)

1번째 규칙을 통해 우리는 좌표값이 특정되면 해당 자리의 어떤 숫자가 들어가는지 단번에 알 수 있게 된다.

(ex. 1,0 위치 → 1 > 0 → 1+1 = 2 라는 숫자가 써지게 됌)

로직을 정리해서 써보자면

1. left → right 숫자를 차례대로 돌면서 (ex. left=2, right=5 라고 할때 2,3,4,5 를 살펴본다)
2. 해당 숫자가 n진수로 표현될 때 어떤지 본다 (ex. n=3 일때, 2,3,4,5 → 02, 10, 11, 12 )
3. 표현된 숫자는 배열의 위치와 동일하므로 row/column 비교를 통해 숫자를 반환한다.
4. (ex. 10 →1,0 → (1+1)=2)

오랜만에 뿌듯한 문제다. 한번에 짜잔하고 규칙을 찾았기 때문에!

 

아래는 코드

def returnCoordinate(n, num):
    if n == 1:
        return 1
    
    num_list = []
    while num != 0:
        num_list.append(num % n)
        num = num // n
    if num == 0:
        num_list.append(0)
        
    if len(num_list) < 2:
        num_list.append(0)
    
    column = num_list[0]
    row = num_list[1]
    
    if column > row:
        return column+1
    else:
        return row+1


def solution(n, left, right):
    answer = []
    
    for num in range(left, right+1):
        answer.append(returnCoordinate(n,num))
    
    return answer

 

아래는 문제 주소

https://programmers.co.kr/learn/courses/30/lessons/87390#

코딩테스트 연습 - n^2 배열 자르기