정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.
제한사항
n은 1 이상 1,000 이하입니다.
풀이
입출력 예시
풀이
생각이 조금 필요한 문제인 것 같다. 우선, 2차원 벡터에 저장되었다고 생각해보자. 그러면 아래와 같은 그림이 나오게 된다.
(i, 0) 순으로 1, 2, ..., 5로 추가되다가, (n-1, 0)부터 (n-1, 4)까지 추가된다. 그리고, 대각선으로 x, y가 각각 1씩 줄어들면서 다시 값이 커지고 다시 처음과 같은 규칙으로 값이 증가한다. 그러니까, 세로 -> 가로 -> 대각선 순으로 수를 계속 증가시켜주면 된다.
#include <string>
#include <vector>
using namespace std;
vector<int> solution(int n) {
vector<int> answer;
vector<vector<int>> tri_snail;
vector<int> tmp;
int number = 1;
for (int i = 1; i <= n; i++) {
tmp.resize(i, 0);
tri_snail.push_back(tmp);
}
return answer;
}
2차원 벡터를 선언해서 위의 그림처럼 벡터를 초기화해줬다. 그럼 우선 세로로 숫자를 추가해 나가는 과정을 표현해보자. 세로로 추가하는 것은, 처음에는 (0, 0), (1, 0), ... ,(n-1, 0)의 과정을 거치고, 다음번에는 (2, 1), (3, 1), ..., (2n-2, 1)에 값을 추가하게 된다. 즉, 1번 루프가 돌 때 마다 (2배, +1)만큼 바뀐 위치에서 부터 숫자가 이어져 나간다. 가로의 경우에는 마지막으로 숫자가 기록된 곳에서 옆으로 수를 추가해주는 작업일 뿐이다. j < i - h인 이유는, 대각선을 그을 때 겹치지 않게 하기 위해서다.
...
...
for (int h = 0; h < n; h++) {
for (int i = 2 * h; i < n - h; i++) {
tri_snail[i][h] = number;
number++;
if (i == n - h - 1) {
for (int j = 1 * h + 1; j < i - h; j++) {
tri_snail[i][j] = number;
number++;
}
}
}
}
...
...
이제 대각선을 그어보자. 대각선은 가로로 수를 추가한 후, 그 다음지점에서 부터 대각선으로 수를 추가해 나간다. 처음에는 (n-1, n-1), ... , (1, 1) 이었다가 다음에는 (n - 2, n - 3) 부터 (3, 2)까지 그어나간다. 이를 조금 바꾸면 대각선은 결국 (n - h - 1, n - 2h - 1) 지점에서부터 수를 추가하는 것이다.
...
...
...
for (int i = n - h - 1; i > 2 * h; i--) {
tri_snail[i][i - h] = number;
number++;
}
}
for (const auto& an : tri_snail) { // 삼각 달팽이가 만들어지면 답에 저장
for (const auto& b : an) {
answer.push_back(b);
}
}
...
전체 코드
#include <string>
#include <vector>
using namespace std;
vector<int> solution(int n) {
vector<int> answer;
vector<vector<int>> tri_snail;
vector<int> tmp;
int number = 1;
for (int i = 1; i <= n; i++) {
tmp.resize(i, 0);
tri_snail.push_back(tmp);
}
for (int h = 0; h < n; h++) {
for (int i = 2 * h; i < n - h; i++) {
tri_snail[i][h] = number;
number++;
if (i == n - h - 1) {
for (int j = 1 * h + 1; j < i - h; j++) {
tri_snail[i][j] = number;
number++;
}
}
}
for (int i = n - h - 1; i > 2 * h; i--) {
tri_snail[i][i - h] = number;
number++;
}
}
for (const auto& an : tri_snail) {
for (const auto& b : an) {
answer.push_back(b);
}
}
return answer;
}
결과
3중 for문이라 값이 커지면 실행 시간이 오래 걸린다. 생각해보니, 가로에 수를 추가하는 작업을 굳이 3중 for문으로 돌릴 필요가 없었다.
#include <string>
#include <vector>
using namespace std;
vector<int> solution(int n) {
vector<int> answer;
vector<vector<int>> tri_snail;
vector<int> tmp;
int number = 1;
for (int i = 1; i <= n; i++) {
tmp.resize(i, 0);
tri_snail.push_back(tmp);
}
for (int h = 0; h < n; h++) {
for (int i = 2 * h; i < n - h; i++) {
tri_snail[i][h] = number;
number++;
/*if (i == n - h - 1) {
for (int j = 1 * h + 1; j < i - h; j++) {
tri_snail[i][j] = number;
number++;
}
}*/
}
for (int j = 1 * h + 1; j < n - 2 * h - 1; j++) {
tri_snail[n - h - 1][j] = number;
number++;
}
}
for (const auto& an : tri_snail) {
for (const auto& b : an) {
answer.push_back(b);
}
}
return answer;
}
