99클럽 코테 스터디 3기 1일차 TIL - 154539 뒤에 있는 큰 수 찾기

154539. 뒤에 있는 큰 수 찾기 / c++ / level2 / 31분

문제 및 코드 (링크)

접근 방식

동적계획법

1. 배열의 각 수에 대한 뒤큰수 (자기 자신보다 뒤에 있고 큰 수 중, 가장 가까이 있는 수)를 배열에 넣어 반환하는 문제
2. 처음엔 단순히 2중 for 문으로 뒤에서 부터 순회하여 뒤큰수를 찾았었다.
3. 당연히 시간초과
4. 효율적으로 뒤큰수를 찾는 방법을 생각해봤다. (사실 전에 풀어봤던 문제여서 풀다가 생각이 나버렸다)
   1. 만약 현재 바로 뒤 원소가 현재 원소보다 크면 뒤큰수
   2. 그렇지 않다면 while로 돌면서 뒤큰수를 찾는다. (이걸 위해서 이제까지 뒤큰수를 찾을 때, 값이 아닌 위치를 저장했다.)
   3. 우선은 바로 뒤 원소의 뒤큰 수 위치를 current에 담고,
   4. current != -1 인 동안 while을 돌면서 반복
      1. 만약 numbers[current]가 현재 원소보다 크다면 answer[i]에 current를 저장
      2. 아니라면 current 에 answer[current]를 저장 후 while 조건 검사
5. 위의 과정을 다 마치고 나서 answer를 다시 순회하면서 저장된 위치를 참조하여 값으로 변환해준다.
   (answer[i] = nubmers[answer[i]])
6. answer을 반환
7. 해결

생각해 볼 점

1. 99클럽 3기가 시작됐다. 다시 꾸준히 해서 이번엔 꼭 올 출석을 노려야겠다!

해시태그

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL