99클럽 코테 스터디 1일차 TIL + n^2 배열 자르기

오늘의 학습 키워드: n^2 배열 자르기, 시간

그 이유는 오늘 문제의 풀이에 있습니다...

문제: n^2 배열 자르기

SQL에서 작성한 방법처럼 문제는 링크로 올리겠습니다.

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

프로그래머스

 

풀이

문제를 확인하면 아주 신이 납니다. 특히 입출력 예시를 보면 환장하죠. 하하 오늘 문제는 10분이면 풀겠다!

그렇게 저는 50분을 사용하고 말았습니다...

 

애니메이션과 문제 설명대로 코드를 구현하면 아주 간단합니다.

2차원 배열(반복문 사용)을 만들고 값을 부여하면 됩니다.

그게 싫으시다면 1차원 배열을 만들고 반복문을 두 번 돌려서 값을 집어넣는 방법도 편합니다.

그렇게 테스트케이스를 통과 하셨다면 이제 지옥을 볼 차례입니다.

아...

다시 문제로 돌아가 원인을 찾아보아야합니다.

제한 사항에서 약간의 힌트를 얻을 수 있습니다. 바로 n의 범위죠.

사악합니다.

n을 이렇게 크게 해 두면 2중 for문을 돌리는 순간 시간초과의 원인이 될 것임은 계산 없이도 알 수 있습니다.. O(n^2)

 

그럼 이제 해답지.. 아니 고민을 해볼 차례입니다.

대체 어떤 방법으로 이 값들을 도출해 낼 수 있을까요? (저는 50분을 고민하다 답지를 보고야 말았습니다...)

 

답은 의외로 간단합니다. (의.외.로.)

이걸 보고 답을 찾아내야 합니다.

• index: 0123 4567 891011
• value: 1234 2234 3334
• n = 4

 

정답은 i값을 n으로 나눈 나머지와 몫 중에 큰 값을 넣어주면 됩니다.

 

left = 0, right =10으로 보겠습니다.

INDEX	VALUE
0	max(0,0)+1 = 1
1	max(0,1)+1 = 2
...	...
9	max(2,1)+1 = 3
10	max(2,2)+1 = 3

 

전체 코드는 이렇습니다.

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

회고

네.. 수학이 제일 어려운 것 같습니다.

문제 설명에 낚이면 안 된다는 것을 깨닫게 되었습니다. 시간복잡도를 보고 풀이방식을 결정하는 것이 중요할듯합니다.

 

문제 및 시도

문제: 시간복잡도

시도: 결과 범위(left, right)에 맞추어 반복문 조기종료, 수학적 접근

 

새롭게 알게 된 점

문제에서 풀이 방식을 준다면 의심해 보자.

 

내일 학습할 것.

그냥 학습한것들 같이 나열해보려합니다. SQL, Python등등