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

프로그래머스

N * N 크기의 배열이 있습니다. 배열의 left 에서 right까지 포함되는 수를 모두 출력해주세요

N이 3인 경우 배열은 아래와 같습니다.

[1, 2, 3] 
[2, 2, 3]
[3, 3, 3]

각 index에 번호를 부여하면 아래와 같습니다.

[0, 1, 2]
[3, 4, 5]
[6, 7, 8]

left가 2고 right가 5라면 [3, 2, 2, 3]을 출력합니다.

 

풀이 방법

배열을 미리 만들어놓고 left~right 까지 찾으면 안됩니다. 그렇게 하면 시간초과에 의해서 실패합니다.

그렇기 때문에 해당 번호에 무슨 숫자가 들어있는지 한번에 찾을 필요가 있습니다.

[1, 2, 3] 
[2, 2, 3]
[3, 3, 3]

위 패턴에서 규칙을 찾아야합니다.

규칙은 각 위치의 y,x 값 중에 가장 큰 값 + 1이 수로 들어갑니다. 

y=1, x = 2라면 3이 들어가게되고

y=2, x =1이라면 3이 들어갑니다.

 

즉 N = 3이고 찾으려는 수가 5번째에 있다면

y = 5 / 3 (1)

x = 5 % 2 (1)

들어가는 수는 2가 됩니다.

 

정답 코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, long long left, long long right) 
{
    vector<int> answer;
    while (left <= right)
    {
        int y = left / n;
        int x = left % n;
        answer.push_back(max(y, x)+1);
        left++;
    }
    
    return answer;
}