[백준 1022] 소용돌이 예쁘게 출력하기 ❗️
🥚문제
https://www.acmicpc.net/problem/1022
- 구현
https://www.acmicpc.net/problem/1022
- 구현
🥚입력/출력
🍳코드
import sys
input = sys.stdin.readline
r1, c1, r2, c2 = map(int, input().split())
n = r2 - r1 + 1
m = c2 - c1 + 1
# (r1, c1) ~ (r2, c2)까지의 모눈종이
arr = [[0]*m for _ in range(n)]
# r1, c1, r2, c2 중 절대값이 가장 큰 것을 찾는다
biggest = max(map(abs, [r1, c1, r2, c2]))
# 좌표 (r, c)를 반시계방향으로 움직이며 값을 +1씩 해준다.
# step 0:(0,0)~(0,0)에서부터 step "biggest"(biggest-1, biggest) ~ (biggest, biggest)단계까지 값을 조작하되,
# 메모리 초과 방지를 위해 (r1, c1) ~(r2, c2) 영역 내에 좌표 (r, c)가 있을 때만 arr[r][c]에 그 값ㅇ르 기록한다.
# 반시계방향
dr = [-1, 0, 1, 0]
dc = [0, -1, 0, 1]
# 단계를 나타내는 step 및 좌표 (r, c)의 초기값 설정
step = 0
r = c = step
val = 1
while step <= biggest:
if step == 0:
# 범위 확인
if r1 <= r <= r2 and c1 <= c <= c2:
arr[r-r1][c-c1] = val
else:
r, c = step-1, step
val += 1
for i in range(4):
while -step <= r + dr[i] <= step and -step <= c + dc[i] <= step:
# 범위 확인
if r1 <= r <= r2 and c1 <= c <= c2:
arr[r-r1][c-c1] = val
# update
r += dr[i]
c += dc[i]
val += 1
# (step, step) 채워주기
if r1 <= step <= r2 and c1 <= step <= c2:
arr[step-r1][step-c1] = val
step += 1
# 출력
# 가장 큰 숫자의 길이
max_val = max(arr[0][0], arr[0][m-1], arr[n-1][0], arr[n-1][m-1])
max_len = len(str(max_val))
for i in range(n):
for j in range(m):
print(str(arr[i][j]).rjust(max_len), end = ' ')
print()
🧂아이디어
구현
소용돌이 모양 들여다보기
- step x일 때, 좌측 상단 좌표 (-x, -x), 우측 하단 좌표 (x,x)의 영역을 소용돌이 모양으로 채워간다. (이미 채워진 내부 영역(-x+1, -x+1), (x-1, x-1)은 제외)
- (x-1, x)에서부터 반시계방향 ↑←↓→ 으로, 값을 1씩 늘려가며 숫자를 채워간다.
메모리초과
-
(r1, c1), (r2, c2)가 주어졌을 때, 위의 규칙을 사용하여 이 좌표들을 모두 포함하는 가장 큰 step까지의 영역을 채운 뒤, (r1, c1) ~ (r2, c2)에 해당하는 좌표들만 출력하면 될 것이라고 생각하기 쉽다.
-
하지만, 그렇게 되면 step0부터 step5000까지 채워야하기 때문에 메모리 초과가 발생한다.
입력값 제한: -5 000 ≤ r1, c1, r2, c2 ≤ 5,000
-
이를 해결하기 위해 딱 (r1, c1) ~ (r2, c2)를 포함하는 크기만큼의 배열(
r2-r1+1 * c2-c1+1
)을 채워 메모리 초과가 발생하지 않도록 한다.
입력값 제한: 0 ≤ r2 - r1 ≤ 49 0 ≤ c2 - c1 ≤ 4
풀이
- (r2 - r1 + 1) * (c2 - c1 + 1) 크기의 배열 arr을 만든다.
- step0부터 몇번째 step까지 채워야하는지 알기 위해, r1, c1, r2, c2 중 절대값이 가장 큰 것을 찾는다. (
biggest
) - step 0부터 step biggest까지의 값을 조작해준다. (반시계방향으로 움직이며 값을 +1씩 증가)
- 만약 어떤 좌표 (r,c)가 (r1, c1) ~ (r2, c2) 범위 내에 들어올 수 있다면 arr[r-r1][c-c1] = (r,c)의 값을 넣어준다.
- 출력은 조건에 맞게 arr에서 가장 큰 숫자의 길이를 구해 rjust로 우측 정렬한다.
Author And Source
이 문제에 관하여([백준 1022] 소용돌이 예쁘게 출력하기 ❗️), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@eastgloss0330/백준-1022-소용돌이-예쁘게-출력하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)