https://school.programmers.co.kr/learn/courses/30/lessons/87390
이 문제를 실제로 2차원 배열로 만들어서 일일이 1차원 배열로 바꾸고, 이를 자르는 구현을 한다면 뭐 당연히 시간초과나 메모리초과 둘중하나는 무조건 뜰 것이다. n의 최댓값이 10^7인데, n X n 크기의 2차원 배열을 만든다면, 10^14개의 int가 들어가고, 여기서 메모리 초과가 당연히 날 것. 결국 우리는 배열을 만드는 것이 아닌, i행 j열의 숫자를 i와 j를 통해 일반화하여, 그 숫자를 알아내야 한다.
위 문제의 예제 1을 보자(n = 3, left = 2, right = 5). 2차원 배열을 구성하면 다음과 같다.
1 | 2 | 3 |
2 | 2 | 3 |
3 | 3 | 3 |
그리고 행과 열을 같이 한번 적어본다.
(0, 0) 1 | (0, 1) 2 | (0, 2) 3 |
(1, 0) 2 | (1, 1) 2 | (1, 2) 3 |
(2, 0) 3 | (2, 1) 3 | (2, 2) 3 |
복잡한 일반화된 공식을 만들어야하나라고 생각하던 찰나, 행, 열 값에 1을 더하면, 반드시 두 숫자중 하나는 해당 칸의 숫자가 된다는 것을 발견했다. 예를 들면 (0, 0)칸의 행, 열에 1씩 더하면 1,1이 되고, 이 칸은 1이 된다. (0, 2) 칸은 1, 3이고, 이 칸은 3이다. 이 규칙에 착안하여, 1차원 배열로 변형한 인덱스값을 다시 2차원 배열의 행, 열값으로 바꾸고, 이 값에 1씩 더한 후, 더 큰 값이 해당 칸의 값이 된다.
[left, right] 구간을 모두 순차적으로 진행하기 때문에, 이 역시 시간초과가 날 것 같지만, 구간의 길이가 10^5를 넘지 않는다는 조건이 있기 때문에, 시간초과가 날 일은 없다.
#include <bits/stdc++.h>
using namespace std;
int slice_array_idx(long long idx, int n) {
int quotient = idx / n + 1; // 몫
int remainder = idx % n + 1; // 나머지
return quotient > remainder ? quotient : remainder;
}
vector<int> solution(int n, long long left, long long right) {
vector<int> answer;
for(auto i = left; i <= right; i++) answer.push_back(slice_array_idx(i, n));
return answer;
}
'coding_test > programmers' 카테고리의 다른 글
lv2 / 3 x n 타일링 / C++ (0) | 2022.10.06 |
---|---|
lv1 / 로또의 최고 순위와 최저 순위 / C++ (0) | 2022.09.15 |
lv2 / 피로도 / C++ (0) | 2022.09.13 |
lv1 / 성격 유형 검사 / 카카오 / C++ (2) | 2022.09.13 |
lv2 / 양궁대회 / 카카오 / C++ (0) | 2022.09.08 |