문제
어느 퍼즐 책에 한 패턴의 처음 세 모양이 나와 있고, 그다음 모양들을 구하라고 합니다.
n = 1 n = 2 n = 3
A BBB CCCCC
BAB CBBBC
BBB CBABC
CBBBC
CCCCC아래를 읽기 전에 먼저 그림을 살펴보고 규칙을 직접 찾아보세요. 정확한 규칙은 다음과 같습니다. n번째 모양은 2n − 1개의 행으로 된 정사각형이고, 각 행은 공백 없이 2n − 1글자입니다. 행과 열 번호를 0부터 매기고 가운데 위치를 n − 1이라고 합시다. r행 c열의 칸에는 알파벳에서 A보다 d칸 뒤에 오는 글자가 들어갑니다. 여기서 d = max(|r − (n − 1)|, |c − (n − 1)|)는 그 칸이 가운데에서 몇 겹 바깥 고리에 있는지를 나타냅니다. 따라서 가운데는 A, 그 둘레의 고리는 B이고, 가장 바깥 테두리는 n번째 글자입니다.
decode_the_pattern(n) 함수를 구현하세요.
입력
n: 만들 모양의 번호입니다(최대 26이므로 글자가 Z를 넘지 않습니다).
출력
위에서 아래 순서로 2n − 1개의 행을 반환합니다. n이 0이면 빈 리스트를 반환합니다.
제약 조건
0 ≤ n ≤ 26
예시
입력:
n = 2
예상 출력:
expected = ["BBB", "BAB", "BBB"]
입력:
long long n = 2;
예상 출력:
std::vector<std::string> expected = {"BBB", "BAB", "BBB"};
입력:
long n = 2;
예상 출력:
string[] expected = new string[] {"BBB", "BAB", "BBB"};
설명
가운데 (1, 1)만 0겹이고 나머지 칸은 모두 1겹 바깥에 있습니다: ["BBB", "BAB", "BBB"].
입력:
n = 4
예상 출력:
expected = ["DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"]
입력:
long long n = 4;
예상 출력:
std::vector<std::string> expected = {"DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"};
입력:
long n = 4;
예상 출력:
string[] expected = new string[] {"DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"};
설명
테두리 칸은 3겹 바깥(D)이고, 3행이 가운데 행입니다: ["DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"].
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
각 예시 정사각형의 가운데를 표시하고, 가운데에서 멀어질수록 글자가 어떻게 바뀌는지 보세요.
힌트 2
같은 고리에 있는 칸은 글자가 같습니다. 고리 번호는 가운데까지의 행 거리와 열 거리 중 큰 값입니다.
힌트 3
아무 n에 대해 만들어 보기 전에 n = 3 예시로 규칙을 확인하세요.
예상 복잡도
시간 O(n^2), 추가 공간 O(n^2)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.