1. 풀이
이 문제를 처음보고 풀면 진짜 대단한 사람인것같다. (그냥 내가 바보인건가)
크게 두 가지 단계로 풀이하면된다.
- 2차원 배열에 저 모양 넣기
- 2차원 배열을 순회하며 return하는 벡터에 push_back 해주기
(1) 2차원 배열에 저 모양 넣기
(1) 우리가 쓰는 2차원 배열은 저런 피라미드 구조를 표현할 수 없다. -> 직각 삼각형으로 표현하자
-> 한쪽 끝을 배열의 0열에 붙여버린다. -> 결과적으로 피라미드 형태가 아니라 위의 사진 처럼 직각 삼각형 형태로 배열에 넣어준다.
(2) 삼각 달팽이 이동 유형은 3가지이다.
아래로 끝까지, 우로 끝까지, 좌상단 대각선으로 끝까지.
중요한 것은 항상 어느 방향이든 채워지지 않은 끝 까지 이동한다는 것이다.
그럼 어디 까지 이동하는지를 알아야한다.
끝을 알려 주기위해 4개의 변수
top : 채워져있지 않은 가장 윗 행
bottom : 채워져있지 않은 가장 아래 행
left : 채워져있지 않은 가장 왼쪽 열
right : 채워지지 않은 가장 오른쪽 열 (왼쪽 변을 벽에 붙인 직각삼각형 형태로 생각했을때)
를 두고, 각 이동에서 이 4개의 변수를 활용해, 행과 열의 범위를 지정해준다.
각 이동의 행, 열 범위를 파악 및 각 이동이 끝나고 top,bottom,left,right를 업데이트 해주면된다.
(3) 언제까지 이동?
삼각달팽이의 움직임을 관찰해보면, n=4인 경우 총 움직임이 4+3+2+1 번 발생한다. -
-> (n(n+1)) / 2 번.
(2) 2차원 배열을 순회하며 return하는 벡터에 push_back 해주기
0이 아닌 값들만 벡터에 넣어준다.
시간 복잡도는 O(n^2) 으로 매우 매우 널널하다.
2. 코드
#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define top t
#define bottom b
#define left l
#define right r
#define end e
int top,bottom,left,right,end,num,state;
int arr[1004][1004];
vector<int> solution(int n) { //O(n^2)
vector<int> answer;
end = (n*(n+1))/2; top = 0; bottom = n-1; left = 0; right = n-1; num = 1; state = 0;
while(num <= end) {
switch(state) {
case 0 : for(int i=top; i<=bottom; i++) arr[i][left] = num++;
left++; top++; state = 1; //left = 1, top = 1;
break;
case 1 : for(int i = left ; i<=right; i++) arr[bottom][i] = num++;
bottom--; right--; state = 2; // bottom = 4 , right = 4
break;
case 2 : for(int i = 0; i <= bottom-top; i++) arr[bottom-i][right-i] = num++;
top++; right--; state = 0; //top = 2, right = 3
break;
}
}
for(int i=0;i<1004;i++) {
for(int j=0;j<1004;j++) {
if(arr[i][j]) answer.push_back(arr[i][j]);
}
}
return answer;
}
3. 오답노트
(1) 시뮬레이션 문제 처음 접함
구현 유형중의 대표문제인 시뮬레이션 이다.
시뮬레이션 문제는 이처럼 문제에서 주어진대로 이동 시킨다.
이러한 시뮬레이션 문제를 처음 풀어봐서 어떤 유형인지 감도 못잡았다.
다음에 비슷한 유형있으면 이 문제처럼 top,bottom,left,right 두고 풀이하는거 적용해봐야겠다.
(2) 노력 부족 ?
구현 문제일수도 있겠다는 생각은 들었지만, 규칙이 너무 복잡해보여서 구현으로 풀이하는 시도를 안해봤다.....생각을 더욱 하는 습관을 들여야겠다.
