프로그래머스. n^2 배열 자르기

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

코딩테스트 연습 - n^2 배열 자르기

 

행,열의 크기인 n의 최댓값이 1000만이다. 

배열을 직접 만들고 숫자를 채워넣는다면 배열을 만드는데만 O(n^2)로 엄청나게 오랜 시간이 걸린다. 

문제에서 주어진 조건 중 right - left < 10^5  가 있는데 이 뜻은 최종적으로 리턴할 answer 벡터의 최대 크기가 100000라는 것이다.

따라서 이 문제는 배열을 직접 만드는게 아니고 

 

1) 주어진 left와 right가 배열의 몇행 몇열인지 판단하고, 

2) 배열의 r행 c열에 숫자 몇이 들어있는지를 판단할수 있어야 한다.

 

1)번은 left,right의 나눈 몫과 나머지로 알 수 있다.

left의 행을 left_r, 열을 left_c라고 하면 

left_r = left / n 

left_c = left % n 이다. 

 

2)번은 그림을 그려보면 알 수 있는데 n = 4라고 하면 다음과 같은 배열일 것이다.

1	2	3	4	5
2	2	3	4	5
3	3	3	4	5
4	4	4	4	5
5	5	5	5	5

각 행을 보면, 행과 열이 같은 지점까지는 열번호가 들어가고,

그 이후부터는 열번호가 들어간다.

예를들어 3행을 보면 3열까지는 3이고, 

그 이후 부터, 즉 4열은 4, 5열은 5 ... 

 

 

 

 

// 추가 

다른 분들의 코드를 보니 2번은 그냥 행과 열 중 큰값에 +1한 것으로 판단할수 있다.