Programmers / n^2 배열 자르기 / C++

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: n^2 배열 자르기 (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/87390

프로그래머스

 

문제 설명

 

---

 

나의 풀이

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

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

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            part.push_back(i);
        }
        for (int k = i + 1; k <= n; k++) {
            part.push_back(k);
        }
        if (part.size() > right) break;
    }

    answer.insert(answer.begin(), part.begin() + left, part.begin() + right + 1);

    return answer;
}

 

처음에 보자마자 바로 풀었지만 뭔가 시간이 초과될 것 같다는 생각이 들었는 데 진짜 시간이 초과되었다. n이 커질 수록 시간 복잡도가 더욱 오래 걸리는 것 같았다. 

내가 필요한 부분은 left부터 right 사이에 있는 배열인데 위 풀이는 left이전의 배열까지 모두 저장을 해야해서 시간이 오래 걸린 것 같다.

 

#include <string>
#include <vector>
using namespace std;

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

    for (long long i = left; i <= right; i++) {
        int row = i / n;
        int col = i % n;
        if (row < col) answer.push_back(col + 1);
        else answer.push_back(row + 1);
    }

    return answer;
}

 

위의 문제를 해결하기 위해서 i/n을 row(행), i%n을 col(열)로 잡아서 내가 필요한 부분의 배열만 잘라내서 풀었다.

---

※ 알아야 할 것

 

필요없는 부분을 잘라내고 필요한 부분만 사용하는 방법을 익혀야하는 방법을 배워야 할 것 같다.