https://school.programmers.co.kr/learn/courses/30/lessons/87390
문제 해결 과정
착안
$n \times n$ 크기의 행렬 matrix[][]는 한 행에 $n$ 개의 요소를 가지므로, 각각의 행을 이어붙여 1차원 배열로 만들었을 때의 $k$ $(1 \le k \le n^2)$ 번째 요소는 $k$ 를 $n$으로 나눈 몫을 $q$, 나머지를 $r$ 이라고 했을 때 matrix[$q$][$r$] 이다.
한편, 문제에서 주어진 규칙에 따라 $n \times n$ 크기의 행렬을 초기화하면
- $i \ge j$ 인 경우: matrix[$i$][$j$] $= i + 1$
- $i < j$ 인 경우: matrix[$i$][$j$] $= j + 1$
이다. 위의 두 사실을 활용하면 행렬을 만들지 않고 left 번째부터 right 번째까지 요소에 해당하는 값들을 구할 수 있다.
구현
left 번째의 요소가 $n \times n$ 행렬 내에서 몇 번째 행, 열에 위치하는지를 구한 다음, 반복문을 통해 열을 가리키는 인덱스를 1 씩 증가시키면서 $k$ 번째 요소의 값을 구한다. 열을 나타내는 인덱스가 $n$이 되면 행을 가리키는 인덱스를 1 증가시키고 열을 가리키는 인덱스를 0 부터 다시 시작한다.
[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~
더보기
#include <vector>
using namespace std;
vector<int> solution(int n, long long left, long long right)
{
vector<int> answer;
long long row = left / n, col = left % n;
for (long long i = left; i <= right; i++)
{
answer.push_back(row < col ? col + 1 : row + 1);
if (++col == n)
{
row++;
col = 0;
}
}
return answer;
}
실행 결과
'C++ 코딩 문제 풀이 > 프로그래머스' 카테고리의 다른 글
[Programmers] 의상 (0) | 2024.01.02 |
---|---|
[Programmers] 행렬의 곱셈 (0) | 2024.01.02 |
[Programmers] 할인 행사 (0) | 2024.01.01 |
[Programmers] 연속 부분 수열 합의 개수 (0) | 2023.12.31 |
[Programmers] 짝지어 제거하기 (0) | 2023.12.28 |
댓글