Programmers - n^2 배열 자르기

---

title: Programmers - n^2 배열 자르기
date: 2022-07-12
tags:

• Algorithm

---

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

문제 요약

n x n 배열을 규칙에 맞게 채운다. 이후 left index부터 right index까지의 1차원 배열을 vector에 넣어 return 한다.

문제 풀이

처음에는 조금 번거로운 방법을 사용하였다.
시작 위치와 끝나는 위치를 계산한 후, 첫 라인과 마지막 라인은 규칙에 맞는 구간만 vector에 넣는다.
중간 부분은 동일한 로직이므로, 앞에서 row 개수만큼 row값을 넣은 후, 1씩 더하며 넣었다.
로직은 처음, 중간, 끝 모두 같으나 예외 처리로 인하여 프로그램이 불필요하게 길어졌다.
첫 라인과 마지막 라인은 조건 비교가 계속하여 발생하는데, 이 라인은 최대 10M까지 가능하기에 조건문이 최대 20M만큼 수행되는 것이다.
과한 작업 시간으로 인하여, 몇 개의 테스트 케이스가 틀린 시점에서 바로 프로그램을 수정하였다.

1.1부터 n.n이라고 하자. 중간의 어느 a.b가 존재한다.
a 라인의 첫 a개는 a값이, 이후에는 1씩 더하면서 진행이 된다.
이는 다른 관점으로 바라볼 때, 전자는 더 큰 a값이 들어가고, 후자는 더 큰 column에 해당하는 b 값이 들어가는 것이다.
결국 a.b 위치의 값은 `std :: max ( a , b ) 이다.
left 값을 1씩 더하며 a.b 형태로 바꾸고, 이를 std :: max 함수를 이용하여 vector에 넣으면 되는 문제이다.
시간 초과가 발생하던 이전 프로그램과는 다르게 최대 약 38ms 시간안에 해결이 되는 것을 확인할 수 있었다.

프로그램

#include <vector>
#include <algorithm>

using std :: vector ;

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



    while ( left <= right )
    {
        answer.emplace_back ( std :: max ( left / n + 1 , left % n + 1 ) ) ;
        ++ left ;
    }


    return answer ;
}