🌀 소용돌이 예쁘게 출력하기
문제
크기가 무한인 정사각형 모눈종이가 있다. 모눈종이의 각 정사각형은 행과 열의 쌍으로 표현할 수 있다.
이 모눈종이 전체를 양의 정수의 소용돌이 모양으로 채울 것이다. 일단 숫자 1을 0행 0열에 쓴다. 그리고 나서 0행 1열에 숫자 2를 쓴다. 거기서 부터 소용돌이는 반시계 방향으로 시작된다. 다음 숫자는 다음과 같이 채우면 된다.
-3 -2 -1 0 1 2 3
--------------------
-3 |37 36 35 34 33 32 31
-2 |38 17 16 15 14 13 30
-1 |39 18 5 4 3 12 29
0 |40 19 6 1 2 11 28
1 |41 20 7 8 9 10 27
2 |42 21 22 23 24 25 26
3 |43 44 45 46 47 48 49이 문제는 위와 같이 채운 것을 예쁘게 출력하면 된다. r1, c1, r2, c2가 입력으로 주어진다. r1, c1은 가장 왼쪽 위 칸이고, r2, c2는 가장 오른쪽 아래 칸이다.
예쁘게 출력한다는 것은 다음과 같이 출력하는 것이다.
- 출력은 r1행부터 r2행까지 차례대로 출력한다.
- 각 원소는 공백으로 구분한다.
- 모든 행은 같은 길이를 가져야 한다.
- 공백의 길이는 최소로 해야 한다.
- 모든 숫자의 길이(앞에 붙는 공백을 포함)는 같아야 한다.
- 만약 수의 길이가 가장 길이가 긴 수보다 작다면, 왼쪽에서부터 공백을 삽입해 길이를 맞춘다.
입력
첫째 줄에 네 정수 r1, c1, r2, c2가 주어진다.
출력
r2 - r1 + 1개의 줄에 소용돌이를 예쁘게 출력한다
제한
- -5000 ≤ r1, c1, r2, c2 ≤ 5,000
- 0 ≤ r2 - r1 ≤ 49
- 0 ≤ c2 - c1 ≤ 4
예제 입력 1
-3 -3 2 0예제 출력 1
37 36 35 34
38 17 16 15
39 18 5 4
40 19 6 1
41 20 7 8
42 21 22 23예제 입력 2
-2 2 0 3예제 출력 2
13 30
12 29
11 28예제 입력 3
-1 -2 -1 1예제 출력 3
18 5 4 3예제 입력 4
0 0 0 0예제 출력 4
1📖 가져다 쓰기
사용 알고리즘 없음.
📐 과정 설계/관리 🔗
나를 상당히 괴롭혔던 문제... 메모리 초과와 시간 초과를 반복하다 솔루션 참고.
메모리 초과
규칙을 찾았다. 중심부 "1"을 기준으로 초록 형광펜이 Level1 붉은 형광펜이 Level2 하늘 형광펜이 Level3를 의미한다.
"n = Level"이라고 하면 n이 늘어날 때마다 아래의 규칙을 반복하면 된다.
- ➡️ 1번
- ⬆️ 2n-1번
- ⬅️⬇️➡️ 2n번
그렇게 전체 소용돌이 맵을 먼저 생성한 후, 조건에 맞는 부분 소용돌이를 출력하면 해결
그러나 문제의 조건에서 전체 소용돌이를 묻는 경우는 없기에 전체 소용돌이 배열을 먼저 만들고 시작하면 메모리 초과 발생
- -5000 ≤ r1, c1, r2, c2 ≤ 5,000
- 0 ≤ r2 - r1 ≤ 49
- 0 ≤ c2 - c1 ≤ 4
제한 조건을 보면 전체 소용돌이는 5000 Level까지 생성할 수 있지만 부분 소용돌이는 끽해봐야 범위가 50*5가 최대다.
따라서 메모리 초과를 방지하기 위해서는 (r,c)가 입력 조건에 부합할 때만 추가해주어야 한다.
시간 초과
초기 코드에 "r1≦x≦r2" "c1≦y≦c2" 조건일 때만 소용돌이 배열에 추가하도록 수정하였다.
하지만 시간 초과가 발생하였는데 이유는 메모리 초과와 똑같다고 예상한다.
전체 소용돌이를 순회하는 배열을 없애고 부분 소용돌이 배열로 줄인 점은 메모리를 아꼈지만
시간적인 측면에서 보았을 때, 전체 소용돌이를 여전히 순회하므로 이를 줄여야 할 것으로 보인다.
정답
이건 솔직히 억까라고 생각한다. 어려움을 위한 어려움이랄까.
r1~r2 , c1~c2 모든 좌표를 탐색하며 소용돌이[r][c]의 값이 무엇인지 수학적으로 판별해낸다.
-
우선 r과 c의 절댓값을 통해 어떤 Level에 속해있는지를 알아낸다.
-
해당 Level에서 우측하단의 값을 알아낸다.
-
우측하단 값을 기준으로 계산을 하여 (r,c)의 값을 알아낸다.
-
우측하단 = (2Level+1)^2
-
(r,c)가 Level의 아래 변에 속한다면 (r,c)의 값 = (우측하단 - (Level - c))
-
왼쪽변이라면 (우측하단 - 2Level - (Level - r))
-
윗변이라면 (우측하단 - 4Level - (Level + c))
-
오른쪽변이라면 (우측하단 - 6Level - (Level+r))
-
이해가 쉽도록 예시 그림을 보여주겠다.
+ Alpha 🔗
예쁘게 출력할 때 쓴 유용한 Python 내장 함수가 있어서 소개하려고 한다.
바로 zfill, ljust, rjust이다. 설명하기 귀찮으니 링크를 걸겠다.
👨🏻💻 CODE
메모리 초과
import sys
input = sys.stdin.readline
r1,c1,r2,c2 = map(int,input().split())
maximum = max(abs(r1),abs(c1),abs(r2),abs(c2))
tonado = [[1]*(2*maximum+1) for _ in range(2*maximum+1)]
x,y = maximum, maximum
for n in range(1,maximum+1):
# right
current = tonado[x][y]
y += 1
tonado[x][y] = current + 1
# up
for i in range(2*n-1):
current = tonado[x][y]
x -= 1
tonado[x][y] = current + 1
# left
for i in range(2*n):
current = tonado[x][y]
y -= 1
tonado[x][y] = current + 1
# down
for i in range(2*n):
current = tonado[x][y]
x += 1
tonado[x][y] = current + 1
# right
for i in range(2*n):
current = tonado[x][y]
y += 1
tonado[x][y] = current + 1
# 행(r1~r2), 열(c1~c2) 출력
answer = []
for row in range(r1+maximum,r2+maximum+1):
answer.append(tonado[row][c1+maximum:c2+maximum+1])
# 가장 큰 자릿수
digit = 0
for i in range(len(answer)):
digit = max(digit,max(answer[i]))
digit = len(str(digit))
# 정답 행렬 문자형으로 바꾸기
answer = [list(map(str,sub)) for sub in answer]
# 정답 행렬 예쁘게 바꾸기
for i in range(len(answer)):
for j in range(len(answer[i])):
if len(answer[i][j]) < digit:
answer[i][j] = answer[i][j].rjust(digit,' ')
# 최종 정답 행렬 예쁘게 출력
for i in range(len(answer)):
print(*answer[i])시간 초과
import sys
input = sys.stdin.readline
r1,c1,r2,c2 = map(int,input().split())
maximum = max(abs(r1),abs(c1),abs(r2),abs(c2))
tonado = [[1]*(c2-c1+1) for _ in range(r2-r1+1)]
# Base Case
x,y = 0,0
current = 1
if r1<=x<=r2 and c1<=y<=c2:
tonado[x-r1][y-c1] = str(current)
for n in range(1,maximum+1):
# right
y += 1
current += 1
if r1<=x<=r2 and c1<=y<=c2:
tonado[x-r1][y-c1] = str(current)
# up
for i in range(2*n-1):
x -= 1
current += 1
if r1<=x<=r2 and c1<=y<=c2:
tonado[x-r1][y-c1] = str(current)
# left
for i in range(2*n):
y -= 1
current += 1
if r1<=x<=r2 and c1<=y<=c2:
tonado[x-r1][y-c1] = str(current)
# down
for i in range(2*n):
x += 1
current += 1
if r1<=x<=r2 and c1<=y<=c2:
tonado[x-r1][y-c1] = str(current)
# right
for i in range(2*n):
y += 1
current += 1
if r1<=x<=r2 and c1<=y<=c2:
tonado[x-r1][y-c1] = str(current)
# 정답 행렬 예쁘게 바꾸기
digit = 0
for i in range(len(tonado)):
for j in range(len(tonado[i])):
digit = max(digit,len(tonado[i][j]))
if len(tonado[i][j]) < digit:
tonado[i][j] = tonado[i][j].rjust(digit,' ')
# 최종 정답 행렬 예쁘게 출력
for i in range(len(tonado)):
print(*tonado[i])정답
import sys
input = sys.stdin.readline
def getValue(r,c):
n=max(abs(r), abs(c))
last= (2*n+1)**2
if r==n:#아래 변
return last-(n-c)
elif c==-n:#왼쪽 변
return last-(2*n)-(n-r)
elif r==-n:#윗 변
return last-(4*n)-(n+c)
else: #오른쪽 변
return last-(6*n)-(n+r)
r1,c1,r2,c2 = map(int,input().split())
tonado = []
for x in range(r1,r2+1):
for y in range(c1,c2+1):
tonado.append(str(getValue(x,y)))
tonado.append('\n')
# 최대 자리수 찾기
digit = 0
for i in range(len(tonado)):
if tonado[i] == '\n':
continue
digit = max(digit,len(tonado[i]))
# 정답 행렬 예쁘게 바꾸기
for i in range(len(tonado)):
if tonado[i] == '\n':
continue
tonado[i] = tonado[i].rjust(digit,' ')
# 최종 정답 행렬 예쁘게 출력
for i in range(len(tonado)):
if tonado[i] == '\n':
print()
else:
print(tonado[i],end=' ')