코딩테스트 | leetcode 75 (334번 문제) JAVA
문제
문제조건
- nums라는 배열을 준다.
- return은 boolean으로 준다.
- (i,j,k) 라는 3쌍의 인덱스가 있다.
- i < j < k 인덱스 순서대로 nums[i] < nums[j] < nums[k] 순서대로 크다는 것을 판별
- ★인덱스는 연속적일 필요가 없고 세 개의 요소가 오름차순인지 확인★
- 인덱스 순서라는 의미는 연속된 인덱스가 아니다.
- nums = [2,1,5,0,4,2,8]
- (0,4,8) 3개의 요소가 오름차순이기 때문에 true
- follow up : 시간복잡도 O(n), 공간복잡도 O(1)
어떻게 해결할 것인가?
- 항상 시작은 결과값을 반환해줄 변수부터 생성하고 return문도 만들자.
-
일단 boolean이기 때문에 return만 적어줘도 테스트케이스는 반은 먹고 들어간다.
벌써 문제의 절반을 맞췄다
그렇다면 부족한 부분을 채워보도록 하자 -
연속되지 않은 인덱스에서 3개의 요소가 오름차순인지 확인하는 것이 가장 키 포인트다.
일단 주어진 예제는 문제를 푸는 데 별로 도움이 되지 않는다
이 문제에서 가장 까다롭다고 할만한 테스트 케이스가 무엇일까?nums = [1,0,4,2,5,1,2,0,4,2,2,1,9]
나만의 테스트 케이스를 산정해보았다.
이 케이스가 통과한다면 나머지 케이스도 충분히 통과할 수 있을 거라 본다.
- 지금 기적적인 코드를 생각하는 건 어려우니 시간복잡도를 배제한 코드부터 작성해보자
이중 for문으로 작성하던 도중 아이디어가 떠올랐다.
nums[i]를 기준으로 nums[j]보다 2번만 크면 되는 것이다.
그래서 int count = 0 추가
그리고 nums[i]가 nums[j] 보다 크다면 count++ 해주는 코드를 작성하였다.
- 하.. 다음과 같이 코드를 작성하여서 돌려봤다.
계속 ArrayIndexOutOfBoundsException이 떠서 뭐가 잘못되었나 계속 봤다.
그랬더니 원인은 for문 j를 i++로 적어놔서 그랬다
하...... 이럴때는 가끔 현타가 온다.
일단 i++로 한 부분은 j++로 수정하였다.
기본적인 요구사항도 못 지킨 못난이 코드가 나왔다
- for문을 시작할 때 count를 초기화해줄 코드 하나를 작성하고
true을 반환하는 부분에서 return 부분을 추가해주었다.
return을 추가하지 않아서 기본적인 요구사항을 계속 fail 했던 것이다...
멍충멍충...
물론 case2가 터졌지만 말이다.
다시 생각해보니 이 구조에는 결정적인 문제가 있었다.
자기보다 큰 숫자가 있는 것만 비교하니 무조건 true를 반환할 수 밖에 없었던 것이다.
- 그런데 이건 아닌 거 같다
문제를 더 쪼개서 다른 해결방법을 찾아보자
내가 문제를 해결 못하는 이유는 주어진 조건 안에서만 답을 찾으려하기 때문이다.
좀 더 자세하게 고찰해보자면 다양한 툴을 이용할 수 있음에도 불구하고 한정된 툴로만 문제를 해결하려고 하니 해결이 되지 않았던 것이다.
이 사고방식을 내던지고 더 자유롭게 사고 할 수 있어야한다.
- 나에게 부족한 사고방식이 무엇인가를 생각해보았다.
문제를 쪼개서 이해하는 능력이 많이 부족한 거 같다.
분석은 나름대로 좀 한다고 생각했는데 이해가 안된다면 더 잘개 쪼개어서
더 작은 단위로 분석을 해봐야한다.
좀 더 작은 단위로 분석한다고 함은
1) 처음 나온 숫자를 어떻게 처리할 것인가?
2) 결국엔 그전 숫자보다 크냐 작냐를 비교하는 것이다.
3) 맨 처음엔 가장 큰 숫자와 비교해보자
4) 여기서 또 막힌다 더 쪼개서 생각해보자
5) 5가 들어오면 first는 5가 되고 다음 num이 4라면 first는 4가 된다
6) 이 경우에는 false가 될 것이다.
7) 이번엔 맞는 true인 케이스를 쪼개서 생각해보자
8) 1,2,3,4,5를 기준으로 num이 1이라면 first는 MAX_VALUE를 유지할 것이다.
9) 2,3,4,5를 돌아도 first는 MAX_VALUE를 유지할 것이다.
10) 그렇다면 true는 어디에 위치해야할까
11) num이 계속 MAX_VALUE보다 작다는 것은 무엇을 의미하는가?
12) 내 생각의 틀린 점을 찾아냈다
13) 8번은 틀린 생각이다.
14) num이 1이라면 first는 1이 되는 것이다.
15) num이 2라면 first라면 2가 될 것이다.
16) num이 3이라면 first가 3이 될 것이다.
17) 그렇다면 true다
18) 그렇다면 어떻게 비연속적인 인덱스가 true인지 판별할 수 있는가?
19) 비연속적이다. 라는 건 올 수도 있고 안 올 수도 있다.
20) 일단 답에서는 한번 더 비교를 해본다.
21) 그런데 이 부분에서 내가 else if로 비교를 떠올릴 재료가 없다.
22) 난 왜 한번 더 비교를 한다는 부분을 왜 떠올리지 못하는 것일까?
23) GPT4의 도움을 받았다. first는 가장 작은 수 second는 두번째로 작은 수이다.
24) 다시 여기서부터 떠올려보자
25) 가장 작은 수와 두번째로 작은 수를 구해야하는 이유는 무엇인가?
26) 그 이유는 두번째로 작은 수보다 계속 크다면 true 이기 때문이다.
27) 그래서 else문으로 true를 반환하는 것이다.
느낀점
내가 생각이 많긴 한 거 같다.
생각을 많이 하긴 하는데 결정적인 한방이 없어서 맴도는 거에 가깝다고 볼 수 있다.
26번 같은 결정적인 한방을 잘 떠올리는 사람이 재능이란 걸까?
그렇다면 난 100% 재능이 없는 쪽인 거 같긴 하다
26번의 생각을 거치고 GPT에게 몇번이나 도움을 받아야 도달할 수 있었다.
이제 내 생각의 알고리즘이 아주 거지 같다는 것을 알게 되었다.
아마 그동안 노력을 많이 했음에도 성과가 좋지 않았다는 것은
내 생각의 알고리즘이 매우 구렸던 탓이겠지?
26번과 같은 사실을 깨닫지 못했기 때문이다.
나에게 26번 같은 생각은 왜 어려운 것인가?
왜 깨닫는데 이렇게 오래 걸리는 것인가?
뭔지는 모르겠다 아무튼 나에게 어려운 문제는
최소 30~50번 정도 맴도는 생각을 해야하고 GPT 같은 도움을 받아야
풀어낼 수 있는 사고력을 가졌다는 사실이다.
이게 내 현실인 것이다.
현재 나에게 가장 부족한 건 사고력
이라고 일단 결론을 내리고 이 사고력을 어떻게 보완할지는 또다시 생각해보자
