🥚문제

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

풀이

1. (r2 - r1 + 1) * (c2 - c1 + 1) 크기의 배열 arr을 만든다.
2. step0부터 몇번째 step까지 채워야하는지 알기 위해, r1, c1, r2, c2 중 절대값이 가장 큰 것을 찾는다. (biggest)
3. step 0부터 step biggest까지의 값을 조작해준다. (반시계방향으로 움직이며 값을 +1씩 증가)
4. 만약 어떤 좌표 (r,c)가 (r1, c1) ~ (r2, c2) 범위 내에 들어올 수 있다면 arr[r-r1][c-c1] = (r,c)의 값을 넣어준다.
5. 출력은 조건에 맞게 arr에서 가장 큰 숫자의 길이를 구해 rjust로 우측 정렬한다.