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

 

n^2 배열 자르기

 

https://school.programmers.co.kr/learn/courses/30/lessons/87390

프로그래머스

---

 

해결전략

 

동적계획법, Dynamic Programming, DP

구현

---

 

첫번째 시도 코드 - 시간초과

 

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

vector<int> solution(int n, long long left, long long right) {
    vector<int> result(n*n);
    vector<int> answer(right - left + 1);

    vector<vector<int>> v(n, vector<int>(n));
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < n; x++) {
            if (y > x) v[y][x] = y+1;
            else       v[y][x] = x+1;
        }
    }

    int j = 0;
    for (int i = 0; i < n * n; i++) 
    {        
        if (i > 0 && i % n == 0) j++;
        
        result[i] = v[j][i%n];
    }

    for (long long i = left, j = 0; i <= right; i++, j++) 
    {   // 범위가 long long 타입이므로 반복문 변수도 맞춰줌.
        answer[j] = result[i];
    }

    return answer;
}

 

---

 

두 번째 시도 - 시간초과

 

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

vector<int> solution(int n, long long left, long long right) {
    vector<int> result(n*n);
    vector<int> answer(right - left + 1);

    int i = 0;
    int j = 0;
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < n; x++, i++) {
            if (y > x) result[i] = y+1;
            else       result[i] = x+1;

            if (left <= i && i <= right)
                answer[j++] = result[i];
        }
    }

    return answer;
}

 

 

 

---

 

정답 코드

 

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

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer(right - left + 1);
    int j = 0;

    for (long long i = left; i <= right; i++) 
    {
        // y x x 2차원 배열이라 상상하면 
        int y = i / n; // y(세로)값은 i/n이다.
        int x = i % n; // x(가로)값은 i%n이다.  

        // answer 1차원 배열에는 left~right 사이의 값만 담아주어야 하기 때문에
        // 변수 j를 0부터 증가시키며 answer[0], answer[1], answer[2],...순서로 담는다.
        // 문제 설정 상 시작값이 0이 아닌 1이기 때문에 +1을 해준다.
        if (y > x) answer[j++] = y+1;
        else    answer[j++] = x+1;
    }

    return answer;
}

 

 

 

---