99클럽 코테 스터디 1/99일차 TIL # n^2 배열 자르기(미들러)

 

문제 출처: 프로그래머스

문제: n^2 배열 자르기

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

1. 문제 설명

정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.

n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.
정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.

제한사항

제한사항
1 ≤ n ≤ 10^7
0 ≤ left ≤ right < n^2
right - left < 10^5

 

 

풀이(1)

처음에 문제를 이해한 뒤 작성한 로직은 다음과 같다.

1. nxn 배열 생성

2. 해당 배열에 인덱스 값 (i, j )중 큰 값을 해당 배열에 삽입

정확히는 max+1 값 삽입

for i in range(n) / for j in range(n)

3. 2D -> 1D 배열로 flatten

4. 배열이 완성되면 left, right 값에 해당하는 값을 answer 배열에 append

하지만 해당 풀이를 생각하면서 문제를 다시 보니 굳이 배열을 생성해서 넣을 필요가 없었던게 flatten 하는게 결국 1D

배열에 값들을 넣고 해당 배열에서 cut을 하면 되는 상황이라 판단하였다.

풀이(2) : 30/100 시간초과

1. for을 2번 돌면서 인덱스 값 (i, j )중 큰 값을 tmp 배열에 차례로 삽입
- 정확히는 max+1 값 삽입
2. 배열이 완성되면 left, right 값 구간에 따라 answer로 잘라서 return

해당 로직으로 작성한 코드는 다음과 같다.

def solution(n, left, right):
    
    answer = []
    
    tmp = []
    for i in range(n):
        for j in range(n):
            
            tmp.append(max(i, j)+1)
        
    answer = tmp[left:right+1]
        
    
    return answer

실행 결과

기본 테스트 케이스는 통과.

시간초과로 30/100.

2중 for문으로 시간초과가 발생. 

여기서 줄일 수 있는 방법이라고 생각한 것은 우선 for문을 다 도는게 아니라 right 까지 갈 필요가 없으니 제약 조건으로 for문을 벗어나는 방법 추가.

풀이(3): 45/100. 시간초과

def solution(n, left, right):
    
    cnt = 0
    tmp_arr = []
    answer = []
    for i in range(n):
        for j in range(n):
            max_val = max(i, j)+1
            
            if cnt >= left and cnt <= right:
                answer.append(max_val)
            
            cnt +=1
            
            if cnt > right:
                break
    
    return answer

cnt 라는 변수를 이용하여 왼쪽부터 하나씩 cnt 값이 올라가게 되고 right 값보다 크게 되면 break로 탈출하여 for문 나머지 영역 실행을 줄였다.

30점에서 45점으로 약간은 올라갔지만 left 까지 자르지 않아서 제한적인 방법이다.

결국 근본적으로 for문에서 left, right를 어떻게 활용해야하는지 이해가 필요했다.

 

풀이(4): 100/100

처음에는 타이핑만 하면서 어떻게 할지 고민을 했다가 종이에 작성하니 생가보다 쉽게 해결 방식이 떠올랐다.

4x4 배열을 그려보면 1,2,3,4가 채워지는 것이 보인다. 채우는 조건은 i, j index 비교로 채우는 것이니 문제가 없다.

다만 left부터 right 까지의 인덱스 값만 가져오기 위해 예를 들어 7, 9 를 left, right로 설정했다.

그렇게 되면 4, 3, 3 값을 포함한 배열이 answer가 된다.

이 4 값은 left 값인 7이라는 숫자를 n =4 인 배열의 행 길이로 나누게 되면 7 =  4 * 1(몫) + 3(나머지) 로 분해 가능하다.

그러면 몫인 1이 행의 인덱스가, 나머지인 3이 열의 인덱스가 된다.(아하)

이를 정리하면 다음과 같다.

for i / for j 이 방식의 이중 for 문을 사용하는 것 대신에 index 값을 하나의 반복문 변수로 설정하고,

이를 배열의 크기인 n을 이용하는 방식을 적용한다.

nxn 배열이기 때문에 index 값을 1~n*n 까지로 본다면

실제로 우리가 필요한 index 값은 left 부터 right 까지가 된다.

그리고 이 index 값을 n으로 나누게 되면 몫은 행의 값이, 나머지는 열 값을 얻을 수 있다.

여기에 앞에서 썼던 max(i, j) + 1을 적용하고 answer에 append 하면 2중 for문을 단일 for문으로 해결된다.

def solution(n, left, right):
    
    answer = []
    for idx in range(left, right+1):
        i = idx // n
        j = idx % n
        answer.append(max(i, j)+1)
        
    
    return answer

 

회고

2중 for문으로 우선 문제를 풀어보는 것도 방법이지만 손으로 문제를 easy case를 하나 만들어보면 생각보다 풀이 방법이 쉽게 보인다.