[Baekjoon] 1262번 알파벳 다이아몬드 S1 <Short>

1262번 - 알파벳 다이아몬드

1. 문제

알파벳 다이아몬드는 정수 길이의 마름모가 여러 개 누적되는 모양이다. 각각의 마름모는 하나의 알파벳 소문자로 그리며, a로 시작해서 z로 끝난다. (가운데에서부터) 그리고, z 이후에는 다시 a로 시작한다.

알파벳 다이아몬드는 다음과 같이 생겼다.

a	.b. bab .b.	..c.. .cbc. cbabc .cbc. ..c..	...d... ..dcd.. .dcbcd. dcbabcd .dcbcd. ..dcd.. ...d...	....e.... ...ede... ..edcde.. .edcbcde. edcbabcde .edcbcde. ..edcde.. ...ede... ....e....	.....f..... ....fef.... ...fedef... ..fedcdef.. .fedcbcdef. fedcbabcdef .fedcbcdef. ..fedcdef.. ...fedef... ....fef.... .....f.....	......g...... .....gfg..... ....gfefg.... ...gfedefg... ..gfedcdefg.. .gfedcbcdefg. gfedcbabcdefg .gfedcbcdefg. ..gfedcdefg.. ...gfedefg... ....gfefg.... .....gfg..... ......g......
$N = 1$	$N = 2$	$N = 3$	$N = 4$	$N = 5$	$N = 6$	$N = 7$

동호는 이런 알파벳 다이아몬드를 타일로 만들어서, 방 바닥을 타일로 모두 채웠다. 예를 들어, $N = 5$ 인 아스키 다이아몬드를 세로 크기가 17, 가로 크기가 46인 방에 채운다면 다음과 같은 모양이 된다.

....e........e........e........e........e.....
...ede......ede......ede......ede......ede....
..edcde....edcde....edcde....edcde....edcde...
.edcbcde..edcbcde..edcbcde..edcbcde..edcbcde..
edcbabcdeedcbabcdeedcbabcdeedcbabcdeedcbabcdee
.edcbcde..edcbcde..edcbcde..edcbcde..edcbcde..
..edcde....edcde....edcde....edcde....edcde...
...ede......ede......ede......ede......ede....
....e........e........e........e........e.....
....e........e........e........e........e.....
...ede......ede......ede......ede......ede....
..edcde....edcde....edcde....edcde....edcde...
.edcbcde..edcbcde..edcbcde..edcbcde..edcbcde..
edcbabcdeedcbabcdeedcbabcdeedcbabcdeedcbabcdee
.edcbcde..edcbcde..edcbcde..edcbcde..edcbcde..
..edcde....edcde....edcde....edcde....edcde...
...ede......ede......ede......ede......ede....

타일 하나위 위치는 행과 열을 이용해 표현한다. 행은 위에서부터 0행, 1행 이고, 열은 왼쪽부터 0열, 1열이다.

동호는 자신의 방의 어떤 부분 직사각형에 쓰여 있는 알파벳이 궁금해졌다. $N$ 이 주어지고, 동호가 알고 싶어하는 직사각형의 왼쪽 위 좌표 $(R_1, C_1)$ 와 오른쪽 아래 좌표 $(R_2, C_2)$ 가 주어질 때, 그 직사각형에 쓰여 있는 알파벳을 출력하는 프로그램을 작성하시오. 동호의 방의 크기는 무한하다. $(x, y)$ 는 $x$ 행 $y$ 열을 의미한다.

• Input

첫째 줄에 5개의 정수 $N$, $R_1$, $C_1$, $R_2$, $C_2$ 가 주어진다.

• Output

$(R_2 - R_1 + 1)$ 줄에 $(C_2 - C_1 + 1)$ 개의 문자를 출력한다.

• Constraints

• $1 \le N \le 20 \ 000$
• $0 \le R_1 \le R_2 \le 20 \ 000$
• $0 \le C_1 \le C_2 \le 20 \ 000$
• $0 \le (R_2 - R_1 + 1) \times (C_2 - C_1 + 1) \le 40 \ 000$

2. 사용 알고리즘

2.1. 알고리즘

• 수학 (Math)

3. 풀이

해당 풀이는 가능한 한 코드의 길이를 줄이고자 하는 숏코딩 방식으로 구현되었다.

3.1. 최소 단위 구역 (패턴)

일단 문제에서 언급되었다시피 동호의 방의 크기는 무한이다. 하지만 정사각형 모양의 패턴은 계속해서 반복된다. 이때 $N$ 의 값이 결정되면 정사각형 패턴의 크기도 $2N - 1 \times 2N - 1$ 으로 결정되며 변하지 않는다.

3.2. 패턴 함수?

가장 처음 든 생각은 $N$ 값에 따른 패턴을 출력하는 함수를 만든 후, 이를 이중 for 문 내에서 호출하는 방식이었다.

def print_pattern(n):
  # 구현

for r in range(r1, c2 + 1):
  for c in range(r2, c2 + 1):
    print_pattern(n)

후술하겠지만 위 방식은 치명적인 결점이 있어 사용할 수 없다. 하지만 위 print_pattern() 함수를 구현하는 것 자체는 문제를 해결하는데 필요하기 때문에 해당 함수를 구현하고자 한다.

3.2.1. 마름모 모양

문제에서 제시된 패턴을 보면 중앙의 a 를 시작으로 그 다음 알파벳들이 마름모 모양을 따라 차례대로 감싸며 확장되는 형태를 가진다.

구현의 편의를 위해 각 알파벳을 숫자로 변경하면 다음과 같다.

a - 0
b - 1
c - 2
...

위 2차원수열의 일반항을 구하면 아래와 같다.

$$
a_{r, c} = | r - n + 1 | + | c - n + 1 |
$$

이때 $a_{r, c} \ge n$ 인 경우에 대하여 '.' 로 대체하면 된다.

3.2.2. 아스키 코드

숫자로 치환한 알파벳은 아스키 코드를 활용하여 되돌릴 수 있다.

$$
\text{chr} (97 + a_{r, c})
$$

3.2.3. 함수 구현

위에서 다룬 내용을 활용하여 print_pattern() 함수를 구현할 수 있다.

• 구현

def print_pattern(n):
  for r in range(2 * n - 1):
    for c in range(2 * n - 1):
      a = abs(r - n + 1) + abs(c - n + 1)
      print(chr(97 + a) if a > n else '.', end='')
    print()

print_pattern(1)
print()
print_pattern(3)
print()
print_pattern(5)

• 출력

a

..c..
.cbc.
cbabc
.cbc.
..c..

....e....
...ede...
..edcde..
.edcbcde.
edcbabcde
.edcbcde.
..edcde..
...ede...
....e....

3.2.4. 한계

하지만 위 함수는 하나의 패턴을 단일 블록으로 출력한다. 이는 문제에서 요구하는 방 전체의 특정 부분을 출력할 때 부적합하다. 패턴이 반복되는 구조를 고려해 하나의 패턴이 아니라 여러 패턴이 이어져 나올 때, 함수가 이미 줄바꿈을 포함하므로 가로로 연달아 등장하는 패턴을 처리하는데 한계가 있다.

3.3. 구역 나누기

각 패턴은 좌표에 따라 반복되고, 특정 좌표가 속한 패턴 내에서의 상대적 위치를 계산해 그에 해당하는 문자를 출력해야 한다. 이를 위해 패턴의 반복성을 고려해 나머지 연산을 활용하고자 한다.

즉, $(r, c)$ 좌표가 주어졌을 때, $\left( r \ \% \ (2N - 1), c \ \% \ (2N - 1) \right)$ 로 해당 좌표가 속하는 패턴 내에서의 상대 위치를 계산할 수 있다.

4. 구현

위에서 풀이한 내용을 바탕으로 코드를 작성하면 다음과 같다.

제출 코드 #2

n, r1, c1, r2, c2 = map(int, input().split())
r = 2 * n - 1

for i in range(r1, r2 + 1):
  for j in range(c1, c2 + 1):
    x, y = i % r, j % r
    c = abs(x - n + 1) + abs(y - n + 1)
    c = chr(c % 26 + 97) if c < n else '.'
    print(c, end='')
  print()

5. 숏코딩

다음은 위 코드를 어떻게든 줄여보려 애쓴 흔적이다.

• #1

n,a,b,c,d=map(int,input().split());r=2*n-1
for i in range(a,c+1):print(''.join(chr(e%26+97)if(e:=abs(i%r-n+1)+abs(j%r-n+1))<n else'.'for j in range(b,d+1)))

• #2

n,a,b,c,d=map(int,input().split())
for i in range(a,c+1):print(''.join(chr(46+((e:=abs(i%(r:=2*n-1)+1-n)+abs(j%r+1-n))%26+51)*(e<n))for j in range(b,d+1)))

• #3

n,a,b,c,d=map(int,input().split());r=2*n-1
for i in range(a,c+1):print(''.join(f'.{chr((e:=abs(i%r+1-n)+abs(j%r+1-n))%26+97)}'[e<n]for j in range(b,d+1)))

• #4

n,a,b,c,d=map(int,input().split());r=2*n-1
for i in range(a,c+1):print(''.join(('.'+chr((e:=abs(i%r+1-n)+abs(j%r+1-n))%26+97))[e<n]for j in range(b,d+1)))

• #5

n,a,b,c,d=map(int,input().split());r=2*n-1
for i in range(a,c+1):print(''.join(['.',chr((e:=abs(i%r+1-n)+abs(j%r+1-n))%26+97)][e<n]for j in range(b,d+1)))

• #6 제출 코드 #1

n,a,b,c,d=map(int,input().split());r=2*n-1
for i in range(a,c+1):print(''.join(chr([46,(e:=abs(i%r+1-n)+abs(j%r+1-n))%26+97][e<n])for j in range(b,d+1)))

6. 제출 코드

1차

맞았습니다!!

n,a,b,c,d=map(int,input().split());r=2*n-1
for i in range(a,c+1):print(''.join(chr([46,(e:=abs(i%r+1-n)+abs(j%r+1-n))%26+97][e<n])for j in range(b,d+1)))

2024년 9월 22일 13:01:09 제출시간 기준, 백준 1262번 모든 언어 카테고리 1등 코드가 되었다.

2차

맞았습니다!!

n, r1, c1, r2, c2 = map(int, input().split())
r = 2 * n - 1

for i in range(r1, r2 + 1):
  for j in range(c1, c2 + 1):
    x, y = i % r, j % r
    c = abs(x - n + 1) + abs(y - n + 1)
    c = chr(c % 26 + 97) if c < n else '.'
    print(c, end='')
  print()

7. 반례모음

다음으로 풀이에 도움이 될만한 반례를 기술한다.

반례1

출력문자 오류 (알파벳 이외의 문자)

• 입력

20000 0 19980 10 20010

• 정답

...................f...........
..................fef..........
.................fedef.........
................fedcdef........
...............fedcbcdef.......
..............fedcbabcdef......
.............fedcbazabcdef.....
............fedcbazyzabcdef....
...........fedcbazyxyzabcdef...
..........fedcbazyxwxyzabcdef..
.........fedcbazyxwvwxyzabcdef.

반례2

출력문자 오류 (알파벳 이외의 문자)

• 입력

20000 19980 19940 19990 19980

• 정답

azyxwvutsrqponmlkjihgfedcbazyxwvutsrqponm
zyxwvutsrqponmlkjihgfedcbazyxwvutsrqponml
yxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlk
xwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkj
wvutsrqponmlkjihgfedcbazyxwvutsrqponmlkji
vutsrqponmlkjihgfedcbazyxwvutsrqponmlkjih
utsrqponmlkjihgfedcbazyxwvutsrqponmlkjihg
tsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgf
srqponmlkjihgfedcbazyxwvutsrqponmlkjihgfe
rqponmlkjihgfedcbazyxwvutsrqponmlkjihgfed
qponmlkjihgfedcbazyxwvutsrqponmlkjihgfedc