반응형
https://school.programmers.co.kr/learn/courses/30/lessons/87390
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제풀이
[[1,2,3], [2,2,3], [3,3,3]] 해당 테스트 케이스는 각 행의 요소 i가 해당 행의 인덱스의 크기 보다 크거나 같은 값을 가지는 성질을 가지고 있다. 따라서 수식을 프로그래밍으로 표현 하면 아래와 같다.
def solution(n, left, right):
answer = []
for i in range(left, right + 1):
row = i // n
col = i % n
answer.append(max(row + 1, col + 1))
return answer
만약 문제 설명 그대로 옮겨적어서 풀이를 하면 어떻게 될까? 제한 조건 부터가 말도 안되는 조건이다. step1 ~ step3 까지 전부 O(n^2)이라는 시간복잡도가 발생한다. 따라서 최대 10^42라는 시간복잡도를 가지게 된다.
분명 프로그래밍 능력과 수학적인 능력은 서로 상호적인 관계이지만 알고리즘 문제를 풀 떄 알고리즘을 응용하는게 아닌 수식으로만 푸는게 주류가 되는 문제는 별로 좋지 않다고 생각한다. 특히 저레벨의 쉽게 풀 수 있는 대부분의 문제가 이렇다.
def solution(n, left, right):
step1 = [[max(j + 1, i + 1) for j in range(n)] for i in range(n)]
step2 = [b for a in step1 for b in a]
answer = step2[left : right + 1]
return answer
