[프로그래머스] 2단계 - n^2 배열 자르기

문제 설명

정수 n, left, right가 주어졌을때 여러 과정을 거쳐 만들어진 1차원 배열을 return 

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

프로그래머스

 

문제 풀이법

입출력 예시를 보면서 처음에는 그냥 배열을 하나 다 만든다음에 left, right 범위만 잘라서 return 했다

그랬더니 시간초과가 나버렸기에 수식을 통해서 문제를 풀어야겠다고 생각했다

 

수식을 알아내기 위해 우선 해당 인덱스의 좌표 값을 알기 위해 이것저것 하며 알아낸 결과

해당 인덱스의 (y, x) 중에 큰 값에 + 1를 하면 원하는 값을 얻을 수 있다!

y는 i / n, x는 i % n로 나타낼 수 있다

 

따라서 for문을 돌며 해당 인덱스에서 값을 얻어낸 다음 answer에 넣어주었다

 

이때 left와 right가 long long 형이므로 for문에서 돌아가는 변수 i도 long long으로 맞춰주었다 

 

소스 코드

#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++) {
        long long y = i / n;
        long long x = i % n;
        
        if (y >= x)
            answer.push_back(y + 1);
        else
            answer.push_back(x + 1);
    }
    
    return answer;
}