문제 해결 전략_260309
-
문제를 읽어보면, 어떤 미지의 수를 구하는 건데
-
미지의 수를 주인공으로 해서 진행하게 되면, 불합리하다고 생각함.
-
예를 들어 4값이 아닌 미지의 수 18로 하고 진행하면, 최소값을 구하는 것이 아니고, 18은 아니니 -- 하면서 4로 갔을때
1,2,3,4 를 처리할 수 있다.
-> 굉장히 비효율적이어서 다른 방법을 생각해봄.
문제의 입력을 기준으로 생각해볼까?
- 문제는 1부터 n까지 이므로, num은 1이 초기값이다.
- 1) 인덱스 0번인 1을 처리하므로, num은 2로 증가하고,
- 2) 인덱스 1번인 2를 처리해보자. num은 2 동일하므로, 3으로 증가.
-> 이런식으로 진행하면 될듯 하다.
이렇게 해도 시간복잡도는 들어온다. 선형으로 진행하니까.
그리고 생각해보면, 문자열 s의 원소를 처리하고 나면, 다음 원소는 처리된 원소에 영향을 끼치지 않으므로, 그리디 문제다.
=> 아이디어
문제 풀때 실시간 나의 주석
주의사항
- 그런데 num의 길이가 2자리 이상일 수 있으므로, 이거를 염두하고 작성하자.
코드
🔥🔥🔥