코딩테스트 연습 - n^2 배열 자르기 | 프로그래머스 (programmers.co.kr)
코딩테스트 연습 - n^2 배열 자르기
정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다. n행 n열 크기의 비어있는 2차원 배열을 만듭니다. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다. 1행 1열부
programmers.co.kr
풀이)
문제에서 주어진 2차원 배열의 좌표를 표현했을 때 다음과 같은데
1,1 1,2 1,3 1,4
2,1 2,2 2,3 2,4
3,1 3,2 3,3 3,4
4,1 4,2 4,3 4,4
문제에서 주어진 대로 값을 넣으려면 좌표 중 큰값을 넣으면 된다.
1 2 3 4
2 2 3 4
3 3 3 4
4 4 4 4
요렇게 된다. 이대로 행별로 새로운 리스트를 만들고 슬라이싱 하는 방법을 이용했었는데 시간초과가 떴다.
10^7이면 10000000 * 10000000이라서 그런것 같다.
위와 같은 이유로 크기대로 배열을 만드는 방법은 시간초과가 나버리기 때문에
left, right 이 변수를 이용해야 하는데 위에서 구한 2차원 배열의 좌표들을 가로로 이어 붙이면
좌표 : 1,1 1,2 1,3 1,4 | 2,1 2,2 2,3 2,4 | 3,1 3,2 3,3 3,4 | 4,1 4,2 4,3 4,4
index : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
n의 크기마다 y좌표는 반복되고 x좌표만 1증가한다.
x = (index // n) + 1
y = (index % n) + 1
와 같은 식을 이용하면 인덱스로 좌표를 구해낼 수 있다.
left부터 right까지만 탐색하며 result리스트를 만들어내고 리턴한다.
def solution(n, left, right):
answer = []
x = 0
y = 1
for i in range(left, right+1):
x = (i // n) + 1
y = (i % n) + 1
value = max(x,y)
answer.append(value)
return answer