나는 알고리즘 공부를 할 때 BOJ 만큼 자주 이용하는 사이트가 프로그래머스 이다. 좀 투박한 감이 있는 BOJ 와는 다르게 상당히 세련되게 만들어놓은 IDE 덕에 뭔가 더 부드러운 코드가 작성되는듯 한 착각이 들기도 한다.
오늘은 알고리즘 공부중에 나왔던 문제 중 조금 기억에 남기면 좋을 듯 한 문제가 있어서 풀어낸 절차를 기록하고자 가지고 왔다.
코딩테스트 연습 Level 2 (Dev-Matching : 웹 백엔드 개발자(상반기)) 문제 의 "행렬 테두리 회전하기"이다.
주어진 조건은 다음과 같다.
- Given
- rows * columns 크기의 행렬이 존재하며 행렬 안에는 숫자가 한칸마다 증가하게 적혀있다.
- 행렬에서 직사각형 모양의 범위를 선택해 해당 범위의 테두리에 위치한 숫자들을 시계방향으로 회전시키고자 한다.
- Input
- 행렬의 세로길이 ( 행 개수 ) rows , 가로 길이 ( 열 개수 ) columns , 회전시키고자 하는 범위의 목록 queries 가 주어진다.
- ( 2 <= rows,columns <= 100 ) and ( 1<= queries <= 10,000 )
- queries 의 각 행은 4개의 정수로 [ x1, y1, x2, y2 ] 이다.
- 이는 첫번째 점 [ x1,y1 ] 에서 [ x2,y2 ] 까지의 직사각형 영역의 테두리가 회전한다는 의미이다.
- Output
- 각 회전마다 이동된 원소 중 가장 작은 원소를 result 에 담아서 반환하라.
위에 보여지는 행렬은 rows = 6, columns = 6 의 행렬이며 회전시키고자 하는 영역의 queries 는 [ 2,2,5,4 ] 이다.
이는 [ 2,2 ] 원소인 8 과 [ 5,4 ] 의 원소인 28 까지의 영역을 직사각형으로 만들고 그 테두리에 위치한 원소들을 회전시키고자 한다는 의미이다.
한 번. 즉, 한 칸 회전시킨 후의 행렬 매트릭스는 위와 같다. 직사각형의 테두리가 아닌 중앙에 위치한 15,21 은 그대로 위치하며 그 테두리 부분의 원소들만 한칸씩 움직이게 된다. 그렇다면 이러한 움직임을 어떻게 구현할 것인가?
각자의 방법이 있겠지만, 나는 각 직사각형의 모서리의 값들을 받아오고 한칸씩 교환하는 방법을 통해 구현하고자 했다.
테두리에 위치한 각 모서리를 그림과 같이 행렬 네 개로 구분한다.
그 행렬 중에서 결국 사용되는것은 회전하는 방향의 마지막 원소를 제외한 나머지 원소들이다. 그리고 길이가 1 짧아진 각 행렬의 가장 꼬리가 되는 자리에 그 직전 모서리의 머리 원소를 넣어준다.
그리고 회전하고자 하는 모서리의 행렬에서 최소값을 result 에 반환해주면 한 번의 회전이 완료된다.
나는 이 문제에서 각 기능들을 모듈화 하여 함수로 작성 후 solution 함수에서 실행시키도록 구현했다.
우선적으로 각 모서리의 값 행렬이 입력으로 주어질 때 회전 후의 행렬이 반환되는 turn 함수를 구현해보자
# temp = [[8,9,10],[10,16,22,28],[26,27,28],[8,14,20,26]]
def turn(temp):
alp = []
for x in temp[:2]:
alp.append(x[:-1])
for x in temp[2:]:
alp.append(x[1:])
tmp = alp[:]
alp[0] = [tmp[-1][0]] + tmp[0]
alp[1] = [tmp[0][-1]] + tmp[1]
alp[2] = tmp[2] + [tmp[1][-1]]
alp[3] = tmp[3] + [tmp[2][0]]
# alp = [[14,8,9],[9,10,16,22],[27,28,22],[14,20,26,27]]
return alp해설을 조금 하자면, 앞서 생각했던 대로 입력에서 사용하고자 하는 회전하는 방향의 머리를 제외한 부분만을 슬라이싱해서 새로운 행렬 alp 에 추가하고 추가된 alp 행렬에서 각 모서리에 필요한 부분을 전 모서리에서 가져와서 합치는 방식을 사용했다.
특이한 부분이라 할 수 있는 점은 alp[:2] 와 alp[2:4] 의 방식이 다른 점인데, 입력되는 temp 가 벡터 데이터가 아닌 스칼라 데이터 이므로, 반환되는 alp 또한 데이터 매트릭스에 직관적으로 사용 가능한 스칼라 데이터를 반환해야하기 때문이었다.
다음으로 회전시킨 alp 데이터를 가지고 현재 만들어진 데이터 매트릭스를 갱신시킬 roll 함수를 구현해보자.
# temp = turn(temp)
# data = [[i+(columns*j) for i in range(1,1+columns)] for j in range(rows)]
# xy = [ i for i in qeries ]
def roll(data,temp,xy):
ax,ay,bx,by = xy
data[ax-1][ay-1:by] = temp[0]
data[bx-1][ay-1:by] = temp[2]
for v,i in enumerate(range(ax-1,bx)):
data[i][by-1] = temp[1][v]
data[i][ay-1] = temp[3][v]
return data사실 roll 함수는 특별할 게 없다. 지금 다시 리뷰를 하기위해 돌아보니 굳이 모듈화 시킬 필요가 있었을까 싶긴 하다.
앞선 turn 함수에서 스칼라 데이터를 반환해주었기 때문에 갱신에서는 방향의 구분이 필요 없이 주어진 temp의 가로 데이터 리스트 값을 바로 넣어주고, for 문을 통해서 세로 데이터도 갱신 해 주었다.
마지막으로 solution 함수이다. 프로그래머스 IDE에서는 solution 함수에 결과값을 return 할 수 있도록 작성해서 실행시켜야만 한다. 또한, 현재까지 반환해주어야 할 각 회전 데이터에서의 최솟값이 정리되지 않았으므로, 결과값 또한 정제해야 한다.
def solution(rows, columns, queries):
r,c = rows,columns
data = [[i+(c*j) for i in range(1,1+c)] for j in range(r)]
answer = []
for xy in queries:
m = 1e9
ax,ay,bx,by = xy
temp = [data[ax-1][ay-1:by],[i[by-1] for i in data[ax-1:bx]],data[bx-1][ay-1:by],[i[ay-1] for i in data[ax-1:bx]]]
temp = turn(temp)
for i in temp:
for j in i:
m = min(m,j)
data = roll(data,temp,xy)
answer.append(m)
return answer데이터 매트릭스를 생성할 때 가장 오류가 많이 발생한다. 그냥 간단하게 정사각 매트릭스를 생성한다면 문제가 없지만, 직사각 매트릭스를 생성해야한다면, 문제를 잘 읽어보아야 문제에서 제시하는 입력데이터를 사용해서 올바른 데이터매트릭스를 생성할 수 있다.
수학에서의 행렬 표기는 가끔 코딩에서 주어지는 행렬. 즉, 2차원 리스트 표기와 배반되는 경우가 종종 발생한다. 그렇기에 2차원 리스트를 생성해야하는 문제에서는 특히나 더 주의를 기울여 데이터 매트릭스를 생성하자.
이 문제에서의 rows 는 세로길이 즉, 행 개수이며 columns 는 가로길이 즉, 열 개수 임을 유의하라.
queries 를 for 문으로 분해하여 각 회전마다 이동하는 원소의 최소값을 answer 리스트에 추가하고자 한다. 여기서 turn 함수를 사용하고 반환된 temp 의 모든 원소를 순회하여 가장 작은 값이 m 이 되고 m 은 answer 에 추가된다.
[[ 마무리 ]]
각각의 함수에 사용된 스킬들은 사실 그렇게 복잡한 과정이 필요하진 않았다. 슬라이싱하고, 합치고, 인덱싱하고 그게 전부인 문제였다. 하지만 그 간단한 스킬들을 적재적소에 그리고 가볍게 만들어야해서 코드리뷰를 통해 다시한번 정리를 할 필요가 있겠다고 생각했다.
최근댓글