99클럽 코테 스터디 1일차 TIL N^2 배열자르기

 

가장 먼저 떠오른 풀이 방법은 2차원 배열의 원소들을 조건에 맞게 채우고,

주어진 n, left, right 을 이용하면 return의 대상이 되는 2차원 배열의 첫 좌표와 마지막 좌표를 알 수 있다.

2차원 배열의 첫 좌표와 마지막 좌표를 loop를 돌아 1차원 배열을 만드는 방법을 생각하였다.

 

제한사항을 고려하면 NxN의 2차원 배열을 만들어야 하는데, n의 크기가 10의 7제곱이다.

가로 세로의 크기가 10의 7제곱이고 전체 loop를 돈다면 10의 14제곱만큼 loop를 돌며 시간초과 에러가 날 것이라고 생각했다.

 

다른 방법을 찾아보니 i행과 i열의 모든 빈 칸을 숫자 i로 채운다고 한다.

생각해보면 좌표의 값은 행과 열 중 더 큰 숫자가 해당 좌표의 값이 된다고 생각했다.

그럼 O(NxN) 이었던 시간 복잡도가 O(right-left)가 된다 ( 제한사항을 보면 10의 5제곱이다 )

이 정도 시간 복잡도면 통과할 수 있다고 생각하여 코드를 작성하였고 잘 동작하였다.