목록행복한 수열의 개수 (1)

화분

[코드트리]행복한 수열의 개수

완전탐색 문제이다. 이 문제를 어떻게 접근해야 할지 고민한 부분은 어떻게 시간복잡도를 최소한으로 줄일지였다. 결국 첫번째엔 행을 기준으로, 두번째엔 열을 기준으로 2중 for문을 2번 돌려서 풀기로 결정했다. 시간복잡도는 O(n^2)이다. 풀면서 고심한 부분은 변수 before와 current를 어떻게 설정할지였다. 처음 시도에서 통과하지 못했는데 행렬 크기가 1 x 1이고 M이 1인 경우에서 통과하지 못했다. 왜냐하면 처음엔 2중 for문의 조건식에 i와 j를 0이 아닌 1부터 시작하도록 했기 때문이다. 이 부분은 before와 current변수를 어떻게 설정할지와도 관련이 있다. 위의 코드는 그 부분까지 고려해서 코드를 짠 결과다. 전체 코드는 다음과 같다. import java.util.*; imp..
Study/CODINGTEST 2023. 9. 3. 15:54
이전 Prev 1 Next 다음