[PROGRAMMERS] 삼각 달팽이(Level2)

yamkim·2020년 11월 12일
0

PROGRAMMERS

목록 보기
10/13

삼각 달팽이(Level2)

  • 문제 링크: 코딩테스트 연습 > 월간 코드 챌린지 시즌1 > 삼각 달팽이

  • 문제 이해

    1. 주어진 예시를 보시면 바로 알 수 있을 것 같습니다.
    2. 수를 증가시키되, 젤 윗 꼭짓점을 기준으로 아래, 오른쪽, 왼쪽 대각 위(삼각형 모양)로
      수를 증가시킵니다.
    3. 결과적으로 만들어야 할 vector는 순서대로 씁니다.
  • 알고리즘 구현

    1. 문제 이해의 글자 그대로 구현했습니다.
    2. 만약 n이 6이라고 한다면, 6번 아래로, 5번 오른쪽으로, 4번 대각선으로, 3번 아래로...
      와 같은 과정을 반복하기 때문에 [아래,오른쪽,대각선]으로 가는 함수를 각각 만듭니다.
    3. yx라는 변수를 만들어, 한 방향에 대한 수를 넣은 후 y와 x가 현재 어디있나 가르쳐주도록
      했기 때문에, 이를 시작으로 다음 방향에서 수를 채워 넣도록 합니다.
    4. 이 때, 주의해야할 점은, 처음 시작을 y=-1, x=0으로 하는 것입니다.
    5. 삼각형은 2차원 array를 채우지만, 결과값은 1차원 array가 되어야 하기 때문에, 저는
      이를 mapping 시키는 함수를 작성하였습니다.
    6. 규칙을 잘 보면, y번째 행의 첫 원소는 y번째까지 자연수의 합과 같습니다. (첫 항이 0인
      계차수열) 또한, x번째 열이 증가하면, y번째 행의 첫 원소에 x만큼 더하여집니다.
  • 알고리즘

#include <string>
#include <vector>

using namespace std;

vector<int> answer;
int num;

int mapping(int y, int x) {
    return ((y + 1) * y / 2 + x);
}

pair<int, int> fillDown(int y, int x, int turn) {
    pair<int, int> yx = make_pair(y, x);
    int dy = 0;
    while (dy < turn) {
        yx.first = y + dy; 
        answer[mapping(yx.first, yx.second)] = num++; 
        ++dy;
    }
    return (yx);
}

pair<int, int> fillRight(int y, int x, int turn) {
    pair<int, int> yx = make_pair(y, x);
    int dx = 0;
    while (dx < turn) {
        yx.second = x + dx;
        answer[mapping(yx.first, yx.second)] = num++; 
        ++dx;
    }
    return (yx);
}

pair<int, int> fillCross(int y, int x, int turn) {
    pair<int, int> yx = make_pair(y, x);
    int dc = 0;
    while (dc < turn) {
        yx.first = y - dc;
        yx.second = x - dc;
        answer[mapping(yx.first, yx.second)] = num++; 
        ++dc;
    }
    return (yx);
}


vector<int> solution(int n) {
    int totNum = (n + 1) * n / 2;
    answer.resize(totNum);
    num = 1;
    pair<int, int> yx = make_pair(-1, 0);
    int turn = n;
    while (1) {
        yx = fillDown(yx.first + 1, yx.second, turn--);
        if (turn == 0) break;
        yx = fillRight(yx.first, yx.second + 1, turn--);
        if (turn == 0) break;
        yx = fillCross(yx.first - 1, yx.second - 1, turn--);
        if (turn == 0) break;
    }
    return answer;
}

0개의 댓글