Life Engineering
[프로그래머스] n^2 배열 자르기 (Java) 본문
https://programmers.co.kr/learn/courses/30/lessons/87390
import java.util.*;
class Solution {
public int[] solution(int n, long left, long right) {
int cnt=0;
int[] answer=new int[(int)(right-left+1)];
for (long i=left; i<=right; i++){
int r=(int)(i/n);
int c=(int)(i%n);
if (r+1>=c+1){
answer[cnt++]=r+1;
}
else{
answer[cnt++]=c+1;
}
}
return answer;
}
}
그대로 구현한다면 시간초과가 뜰 것이다. n^2가 10^14 라서 그렇다.
이 문제의 포인트는 배열의 n번째 수가 2차원 배열의 몇번째에 해당하고, 그 법칙을 찾아내는 것이다.
i번째 수를 구한다고 하면, i/n하면 행 번호, i%n하면 열 번호가 나오는데 이 문제의 규칙은
행 번호>=열 번호일 경우 행 번호를 따라가고, 행 번호<열 번호일 경우 열 번호를 따라간다는 점이다.
이를 이용해서 answer에 넣어준다.
'Problem Solving' 카테고리의 다른 글
[프로그래머스] 등굣길 (Java) (0) | 2022.03.13 |
---|---|
[BOJ 17136] 색종이 붙이기 (Java) (0) | 2022.03.10 |
[프로그래머스] 배달 (Java) (0) | 2022.03.09 |
[BOJ 1107] 리모컨 (Java) (0) | 2022.03.08 |
[BOJ 11054] 가장 긴 바이토닉 부분 수열 (Java) (0) | 2022.03.08 |