문제 설명
정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.
1. n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
2. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
2-1. 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
3. 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
4. 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.
정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.
- 1 ≤ n ≤ 107
- 0 ≤ left ≤ right < n2
- right - left < 105
| n | left | right | result |
| 3 | 2 | 5 | [3,2,2,3] |
| 4 | 7 | 14 | [4,3,3,3,4,4,4,4] |
입출력 예 #1
다음 애니메이션은 주어진 과정대로 1차원 배열을 만드는 과정을 나타낸 것입니다.
입출력 예 #2
다음 애니메이션은 주어진 과정대로 1차원 배열을 만드는 과정을 나타낸 것입니다.
출처: https://programmers.co.kr/learn/courses/30/lessons/87390
나의 풀이:
#include <iostream>
#include <vector>
using namespace std;
vector<int> solution(int n, long long left, long long right) {
vector<int>answer;
long index = left;
while ( index <= right)
{
int a = index / n;
int b = index % n;
if ( a >= b) answer.push_back(a + 1);
else answer.push_back(b +1);
index++;
}
return answer;
}
풀이 설명:
본 문제는 시간초과가 나지 않도록 하는 것이 관건이었다.
입력의 범위가 1 ≤ n ≤ 107 로, 굉장히 큰 범위이기 때문에
n*n 크기의 배열을 모두 계산하면 반드시 시간 초과가 발생하여,
left부터 right 범위 사이의 배열만 계산해야했다.
index만으로 어떤 숫자를 push해야하며, 코드로 어떻게 표현할지가 중요했던 것 같다.
나는 index 변수를 while문을 통해 left부터 right까지 참조하여
[ index / n ]와 [ index % n ] 중 큰 값을 answer에 푸시했다.
이해를 돕기 위해 예시2를 표로 나타내면 다음과 같다.
굵은 글씨가 더 큰 값(이상)이고, 각각에 1을 더해서 생각하면 된다.
|
index
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
|
index/n
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
2
|
2
|
2
|
2
|
3
|
3
|
3
|
3
|
|
index %n
|
0
|
1
|
2
|
3
|
0
|
1
|
2
|
3
|
0
|
1
|
2
|
3
|
0
|
1
|
2
|
3
|