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

문제

프로그래머스

---

풀이

이 문제는 n * n으로 이루어진 2차원 배열을 1차원 배열로 바꾼 뒤, left ~ right 위치에 있는 요소들을 반환하는 문제이다.

 

 

틀린 접근

2차원 배열을 만든 뒤, 1차원 배열로 바꾸고 left ~ right 범위의 요소를 반환하는 방법으로 풀이했다.

O(n^2)으로 풀이했더니 당연히 시간초과가 나왔다.

#include <iostream>
#include <vector>

using namespace std;

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;
    vector<vector<int>> map;

    for(int i = 1; i <=n; i++){
        
        vector<int> vec;
        for(int j = 0; j < i; j++){
            vec.push_back(i);
        }
        
        for(int j = i + 1; j <= n; j++){
             vec.push_back(j);
        }
        
        map.push_back(vec);
    }
    
    for(int i = 0; i < map.size(); i++){
        for(int j = 0; j < map[i].size(); j++){
            answer.push_back(map[i][j]);
        }
    }
    
    answer.erase(answer.begin() + right + 1, answer.end());
    answer.erase(answer.begin(), answer.begin() + left );

    return answer;
}

 

제한 사항이 1 <= n <= 10^7 이기 때문에 2차원 배열로 만든다면  arr[10000000][10000000]이다. (100조)

1차원 배열도 마찬가지로 최대 100조 크기가 나온다.

 

그렇기 때문에 left ~ right에 해당하는 요소들을 바로 구해야한다.

 

 

n이 4라고 가정할 때 아래와 같이 2차원 배열이 나온다.

 

1 2 3 4 
2 2 3 4 
3 3 3 4 
4 4 4 4 

 

row = i % n + 1 , column = i / n + 1

(1를 더하는 이유는 숫자가 1부터 시작하기 때문)

 

left가 7이라면, row == 4, column == 2  => 4가 선택된다.

 

그렇기 때문에 row가 column보다 크다면 row가 선택되고, 작다면 column이 선택된다.

#include <vector>

using namespace std;

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;

    for(long long i = n; i < n; i++){
       int row = i % n + 1;
       int column = i / n + 1;
                    
       answer.push_back(row <= column ? column : row);
    }

    return answer;
}