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

문제 설명

 

제한 사항 및 입출력 예제

 

알고리즘 개념

알고리즘(1)

　정해진 규칙에 의해 생성되는 배열의 일부분을 출력하는 문제다. 제한사항을 보면 n과 left, right의 값이 상당히 크므로 시간 초과를 주의해야 한다. 즉, 배열을 초기화하려면 시간 복잡도가 O(n^2)이 될 텐데, O(n)으로 줄이는 것을 목표로 하자.

 

　그렇다면 우리는 배열의 규칙성을 찾아 left와 right 사이의 인덱스 값을 통해 바로 배열의 값을 구해야 한다. 이를 구하기 위해 예제에 나와 있는 n = 3의 배열을 시각화해 보자.  

 

 

 

　어떤 규칙성이 보이는가? 먼저 확인할 수 있는 것은 다음과 같다. 행이 바뀔 때마다 첫 번째 행을 기준으로 일련의 규칙에 따라 값이 바뀐다. 다음 사진에서 기준인 값은 1, 2, 3이다. 이 값을 기준으로 다음과 같이 된다.

 

 

　즉, 1부터 n까지 수를 기준으로 하여 행이 바뀔 때마다 바뀐 수만큼의 값 증가가 있다. 이러한 규칙성을 갖고 풀어보았을 때 시간 초과 문제로 해결에 성공하지 못하였다(...)

　그래도 풀이 방법은 올려 놓을태니 혹시 수정 사항이 있으면 필자가 추후에 수정을 하도록 하겠다. 

 

알고리즘(2)

　이번에는 배열에 (x,y) 값과 함께 나타내보겠다.

 

 

　보시다시피 배열의 값은 (x,y)에서 x와 y 중 큰 값이 된다는 것을 쉽게 확인할 수 있다. 이러한 알고리즘에 착안하여 문제를 풀어보자.

 

풀이

성공한 풀이

#include <vector>
using namespace std;

vector<int> solution(int n, long long left, long long right)
{
    vector<int> ans;
    long long int x, y;

　먼저 좌표 값 x, y와 답을 초기화할 배열 ans를 선언한다. 여기서 많은 사람들이 간과하는 점은 자료형을 int로 하면 시간 초과가 날 가능성이 크다는 것이다. 캐스팅하는데 시간이 많이 소요되므로 자료형을 문제에서 제시하는 것과 같이 long long으로 초기화해 주자. 

 

    for (long long int i = left; i <= right; ++i)
    {
        y = i % n + 1;
        x = i / n + 1;
        long long int value = x > y ? x : y;

        ans.push_back(value);
    }
    
    return ans;
}

　그리고 left부터 right까지 반복을 돌리며 배열을 초기화하는데, x와 y의 값은 다음 조건에 의해 결정된다.

• x의 값은 i / n
• y의 값은 i % n

　우리는 배열을 (1,1)부터 시작하기 때문에 x와 y에 1을 더해주어야 한다. 마지막으로 둘 중 큰 값을 ans에 넣어주면 된다.

 

실패한 풀이

#include <vector>
using namespace std;

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

    for (int i = 1; i <= n; i++)
        standard.emplace_back(i);

    answer = standard;

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j <= i; ++j)
        {
            standard[j]++;
        }

        for (int j = 0; j < n; ++j)
            answer.emplace_back(standard[j]);
    }

    vector<int> ans;

    for (long long int i = left; i <= right; ++i)
        ans.emplace_back(answer[i]);

    return ans;
}