[프로그래머스][C++] n^2 배열 자르기

n^2 배열 자르기

문제 링크

n^2 배열 자르기

분석

n, left, right 값이 크므로, 2차원 배열을 직접 만들어서 풀 경우 시간 초과가 발생합니다.

배열의 값은 2차원 배열의 인덱스인 (x, y)에서 x와 y 중 큰 값이 됩니다.

n이 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 된 값인걸 알 수 있습니다.

풀이

#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;
    
    // left부터 right까지 반복
    for (long long index = left; index <= right; ++index)
    {
        long long x = index / n; // 행
        long long y = index % n; // 열
        
        answer.push_back(max(x, y) + 1);
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n)$입니다.

• left부터 right까지 순회하는 반복문 %O(n)$

공간 복잡도는 $O(n)$입니다.

• left부터 right에 해당하는 배열의 값을 저장하는 answer $O(n)$

테스트 1 〉 통과 (42.51ms, 22.2MB)
테스트 2 〉 통과 (28.53ms, 24.3MB)
테스트 3 〉 통과 (28.88ms, 24.4MB)
테스트 4 〉 통과 (0.03ms, 4.21MB)
테스트 5 〉 통과 (0.03ms, 3.67MB)
테스트 6 〉 통과 (28.11ms, 22.9MB)
테스트 7 〉 통과 (28.24ms, 24.2MB)
테스트 8 〉 통과 (26.40ms, 22.3MB)
테스트 9 〉 통과 (29.72ms, 23.7MB)
테스트 10 〉 통과 (27.97ms, 23.3MB)
테스트 11 〉 통과 (28.93ms, 23MB)
테스트 12 〉 통과 (24.19ms, 20.3MB)
테스트 13 〉 통과 (25.11ms, 22.3MB)
테스트 14 〉 통과 (26.09ms, 21.3MB)
테스트 15 〉 통과 (25.91ms, 21.1MB)
테스트 16 〉 통과 (26.51ms, 21.9MB)
테스트 17 〉 통과 (25.60ms, 22.1MB)
테스트 18 〉 통과 (27.88ms, 24.1MB)
테스트 19 〉 통과 (27.45ms, 22.5MB)
테스트 20 〉 통과 (25.33ms, 20.5MB)