[프로그래머스 lv2] n^2 배열 자르기

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

프로그래머스

 

문제설명

 

정수 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 함수를 완성해주세요.

 

 

문제 해결 방법

 

2차원 배열 특정 위치에 해당되는 첨자 같은 공식이라고 있었다. 

 

행첨자는 ([현 위치]) / (전체 열의 수 )

열 첨자는 ([현 위치]) % (전체 열의 수)  

 

이거랑 코드 구현의 아이디어랑 관련이 있다. 

 

왜냐하면 문제의 제한사항을 감안하고 구현하려면 left부터 right 까지의 값을 가진 배열을 바로 구해야(left이전의 값이나 right이후의 값을 계산하면 시간초과 이슈 발생)한다. 

 

해당 배열을 바로 구하기 위해서는 문제에서 제공한 행과 열에 대한 값의 관계를 생각해서 행첨자와 열첨자를 이용해 문제를 풀어야만 한다. 

 

행과 열 첨자를 구하면 두 값중 큰 값이 해당 위치의 원소의 값이 된다. 

 

코드 구현

 

def solution(n, left, right):
    answer = []
    for i in range(left,right+1):
        
        a = (i // n) +1# 몫 행첨자 
        b = (i % n) +1#나머지  열 첨자 
        print('a', a, 'b', b)
        if a < b :
            print('check')
            a, b = b, a
        answer.append(a)

    return answer

 

 

시간/공간 복잡도

 

최악의 경우 O(N)

 

 

최적화 및 개선 / 어려웠던 점

 

진짜 굉장히 어렵다고 생각하는 문제다.

 

처음에 2중 반복문으로 풀었는데 테스트케이스 대부분 시간초과 났따. 그래서 반복문을 하나로 줄였는데도 비슷했다. 

 

굉장히 어렵다고 생각한다. 내가 뭘 모르는건가?

 

그래서 진짜 끙끙 앓다가 힌트랑 남의 코드 봤다. 보고도 이해가 안갔다. 진짜 내가 뭘 모르는게 분명하다. 

 

찾아보니 2차원 배열 특정 위치에 해당되는 첨자 같은 공식을 참고해서 풀었다. 

 

확실히 나는 해당 개념을 몰랐다. 그래서 문제 풀때도 아이디어를 거의 없는걸 창조해서 풀듯이 했고, 남의 코드를 봐도 

 

이해를 잘 못했던 것 같다. 

 

글로 쓰고나니 별거아닌거 같은 이 느낌은 뭐지 ;;; 휴,, 거진 서너시간은 날린 것 같다. 

 

그래도 좋은 경험이였다.