[문제]
https://school.programmers.co.kr/learn/courses/30/lessons/68645
[풀이]
처음에는 규칙성을 찾고 인덱스를 하나씩 선형 탐색하면서 push_back을 하려다가(좀 오래 고민함), 이건 아닌거 같아서 다른 방법을 생각했다. 먼저 2차원 배열을 준비한 다음 아래, 오른쪽, 위-왼쪽(대각선) 방향으로 채워나가는 방식이다.
1. 2차원 테이블 생성
2. 각 인덱스 값에 접근할 요소들 선언
3. 탐색 시작, max값이 되면 종료한다.
3-1. 방문한 테이블 좌표값에 대해 num을 입력하고, 1 증가시켜준다.
3-2. 현재 방향에 대해 먼저 y를 1 증가, x는 그대로 탐색 시도, 이 값이 경계를 벗어났는지 확인함
3-2-1. 경계를 벗어난 경우(사이즈를 벗어나거나 값이 채워진 인덱스인 경우), 방향 전환을 시도
3-2-2. 시도 방식은 dir(방향 인덱스)를 재설정하고, 해당 방향 인덱스를 기준으로 탐색할 좌표값을 덮어써줌
3-3. 경계가 벗어나지 않았으면 좌표를 재설정
4. 3의 방식을 반복하여 값을 채워넣은 뒤, 2차원 배열을 answer에 담고 return
규칙성을 찾지 않고 그냥 채워넣었으면 금방 풀었을 것이다(아쉬운 부분). 아래는 구현 코드이다.
#include <vector>
using namespace std;
int dy[3] = { 1, 0, -1 };
int dx[3] = { 0, 1, -1 };
vector<int> solution(int n)
{
// 삼각형 구조를 표현할 2차원 벡터
vector<vector<int>> triangle(n, vector<int>(n, 0));
// 방향 벡터: 아래, 오른쪽, 왼쪽 위 대각선
int dy[3] = { 1, 0, -1 };
int dx[3] = { 0, 1, -1 };
int y = 0;
int x = 0;
int num = 1;
int dir = 0; // 방향 인덱스
int maxNum = n * (n + 1) / 2;
while (num <= maxNum)
{
triangle[y][x] = num++;
int ny = y + dy[dir];
int nx = x + dx[dir];
// 경계를 벗어나거나 이미 숫자가 채워져 있으면 방향 전환
if (ny >= n || nx >= n || ny < 0 || nx < 0 || triangle[ny][nx] != 0)
{
dir = (dir + 1) % 3;
ny = y + dy[dir];
nx = x + dx[dir];
}
y = ny;
x = nx;
}
// 결과를 1차원 벡터로 변환
vector<int> answer;
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= i; j++)
{
answer.push_back(triangle[i][j]);
}
}
return answer;
}
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스 Lv.2] 마법의 엘리베이터 (0) | 2025.05.21 |
---|---|
[프로그래머스 Lv.2] 연속된 부분 수열의 합 (0) | 2025.05.20 |
[프로그래머스 Lv.2] 큰 수 만들기 (0) | 2025.05.20 |
[프로그래머스 Lv.2] 쿼드압축 후 개수 세기 (0) | 2025.05.19 |
[프로그래머스 Lv.2] 다리를 지나는 트럭 (0) | 2025.05.19 |