Programers : 삼각 달팽이
23501 단어 level2PROGRAMERSPROGRAMERS
삼각 달팽이
코드
[ 나의 풀이 ] - 직관적인 풀이
#include <string>
#include <vector>
// 01:07 시작 ~ 02:53 종료
using namespace std;
vector<int> solution(int n) {
vector<int> answer;
vector<vector<int>> set(n);
vector<pair<int,int>> ht(n); // head-tail
int untill = (n*(n+1))/2;
/* head-tail 값 지정 & 해당 배열 크기 생성 - 그냥 resize()로 공간만 했어도 됬네요ㅎㅎ */
for(int j=1,i=0,idx=0;j<=n;j++)
{
int cnt=0;
ht[idx] = {0,0};
while(j != cnt)
{
// 들어가는 값은 사실 상관 없음
set[idx].push_back(i++);
cnt++;
}
ht[idx++].second = cnt-1;
}
int order = 1;
int set_idx = n-1;
/* 넣는 숫자가 untill보다 크면 out! */
while(order <= untill)
{
// 패턴 (1) 왼쪽 아래 방향 : head 1개씩 처리
for(int i=0;i<set.size();i++)
{
int head = ht[i].first;
int tail = ht[i].second;
if(head <= tail) {
set[i][head] = order++;
ht[i].first++;
}
}
// 패턴 (2) 왼쪽에서 오른쪽 방향 : 묶음 전체 처리
for(int i=ht[set_idx].first;i<set[set_idx].size();i++)
{
int head = ht[set_idx].first;
int tail = ht[set_idx].second;
// head <= tail
if(head <= tail){
set[set_idx][i] = order++;
ht[set_idx].first++;
}
}
set_idx--;
// 패턴 (3) 오른쪽 아래에서 위 방향 : tail 1개씩 처리
for(int i=set_idx;i>=0;i--)
{
int head = ht[i].first;
int tail = ht[i].second;
if(head <= tail) {
set[i][tail] = order++;
ht[i].second--;
}
}
}
/* answer에 답 쌓기 */
for(int i=0;i<set.size();i++)
{
for(int j=0;j<set[i].size();j++)
{
answer.push_back(set[i][j]);
}
}
return answer;
}
1) 각 수들을 묶음별로 2차원 배열 형태의 vector에 저장함
2) 각 층마다 head / tail 이라는 변수를 두고 증 / 감 해가면서 특징을 찾아서 해결함
[ 최적 코드 ] - 특징을 찾아서 해결
#include <string>
#include <vector>
using namespace std;
vector<int> solution(int n) {
vector<int> answer;
vector<vector<int>> arr(n);
int order=1;
int x=0, y=-1;
int resize=1;
int state = 0;
for(int i=0;i<arr.size();i++) arr[i].resize(resize++);
/* 3개의 패턴들 에서 일어나는 연산 수가 n -> n-1 ... 1 까지 규칙이 있음 */
for(int i=n;i>0;i--)
{
/* 패턴 (1) : 왼쪽 아래로 이동 */
if(state == 0){
for(int j=0;j<i;j++) arr[++y][x] = order++;
state=1;
}else if(state == 1){
/* 패턴 (2) : 오른쪽으로 이동 */
for(int j=0;j<i;j++) arr[y][++x] = order++;
state=2;
}else if(state == 2){
/* 패턴 (3) : 오른쪽 위로 이동 */
for(int j=0;j<i;j++) arr[--y][--x] = order++;
state=0;
}
}
/* answer에 답 쌓기 */
for(int i=0;i<arr.size();i++)
for(int j=0;j<arr[i].size();j++)
answer.push_back(arr[i][j]);
return answer;
}
- key point !
1) 3개의 패턴을 state라는 변수로 관리
2) 각 패턴 내부에서 일어나는 연산 수에 패턴이 있다
(n -> n-1 -> n-2 ... -> 1)
3) x와 y좌표를 이용해서 패턴을 수행함
Author And Source
이 문제에 관하여(Programers : 삼각 달팽이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/Programers-삼각-달팽이
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
[ 나의 풀이 ] - 직관적인 풀이
#include <string> #include <vector> // 01:07 시작 ~ 02:53 종료 using namespace std; vector<int> solution(int n) { vector<int> answer; vector<vector<int>> set(n); vector<pair<int,int>> ht(n); // head-tail int untill = (n*(n+1))/2; /* head-tail 값 지정 & 해당 배열 크기 생성 - 그냥 resize()로 공간만 했어도 됬네요ㅎㅎ */ for(int j=1,i=0,idx=0;j<=n;j++) { int cnt=0; ht[idx] = {0,0}; while(j != cnt) { // 들어가는 값은 사실 상관 없음 set[idx].push_back(i++); cnt++; } ht[idx++].second = cnt-1; } int order = 1; int set_idx = n-1; /* 넣는 숫자가 untill보다 크면 out! */ while(order <= untill) { // 패턴 (1) 왼쪽 아래 방향 : head 1개씩 처리 for(int i=0;i<set.size();i++) { int head = ht[i].first; int tail = ht[i].second; if(head <= tail) { set[i][head] = order++; ht[i].first++; } } // 패턴 (2) 왼쪽에서 오른쪽 방향 : 묶음 전체 처리 for(int i=ht[set_idx].first;i<set[set_idx].size();i++) { int head = ht[set_idx].first; int tail = ht[set_idx].second; // head <= tail if(head <= tail){ set[set_idx][i] = order++; ht[set_idx].first++; } } set_idx--; // 패턴 (3) 오른쪽 아래에서 위 방향 : tail 1개씩 처리 for(int i=set_idx;i>=0;i--) { int head = ht[i].first; int tail = ht[i].second; if(head <= tail) { set[i][tail] = order++; ht[i].second--; } } } /* answer에 답 쌓기 */ for(int i=0;i<set.size();i++) { for(int j=0;j<set[i].size();j++) { answer.push_back(set[i][j]); } } return answer; }
1) 각 수들을 묶음별로 2차원 배열 형태의 vector에 저장함
2) 각 층마다 head / tail 이라는 변수를 두고 증 / 감 해가면서 특징을 찾아서 해결함
[ 최적 코드 ] - 특징을 찾아서 해결
#include <string> #include <vector> using namespace std; vector<int> solution(int n) { vector<int> answer; vector<vector<int>> arr(n); int order=1; int x=0, y=-1; int resize=1; int state = 0; for(int i=0;i<arr.size();i++) arr[i].resize(resize++); /* 3개의 패턴들 에서 일어나는 연산 수가 n -> n-1 ... 1 까지 규칙이 있음 */ for(int i=n;i>0;i--) { /* 패턴 (1) : 왼쪽 아래로 이동 */ if(state == 0){ for(int j=0;j<i;j++) arr[++y][x] = order++; state=1; }else if(state == 1){ /* 패턴 (2) : 오른쪽으로 이동 */ for(int j=0;j<i;j++) arr[y][++x] = order++; state=2; }else if(state == 2){ /* 패턴 (3) : 오른쪽 위로 이동 */ for(int j=0;j<i;j++) arr[--y][--x] = order++; state=0; } } /* answer에 답 쌓기 */ for(int i=0;i<arr.size();i++) for(int j=0;j<arr[i].size();j++) answer.push_back(arr[i][j]); return answer; }
- key point !
1) 3개의 패턴을 state라는 변수로 관리
2) 각 패턴 내부에서 일어나는 연산 수에 패턴이 있다
(n -> n-1 -> n-2 ... -> 1)
3) x와 y좌표를 이용해서 패턴을 수행함
Author And Source
이 문제에 관하여(Programers : 삼각 달팽이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/Programers-삼각-달팽이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)