[2024.06.14] 프로그래머스_다음 큰 숫자

알고리즘 심화반 타임어택 문제로 선택된 문제. 확실히 한 주 동안 풀어본 유형을 내주셔서 생각보다 빠르게 풀 수 있었다.

 

프로그래머스_다음 큰 숫자

다음 큰 숫자

내가 제출한 다변

처음에는 재귀로 풀어야 할까? 생각하다가 좀 더 단순하게 생각했다. 

NumberOfOne이라는 함수를 만들어 1의 개수를 세었고, 이 함수에서 toString()과 match()는 모두 O(log n)의 시간 복잡도를 가진다. 따라서 solution 함수에서는 targetNumber의 초기값을 선언하고 while문의 조건문을 실행할 때 O(log n), while 루프를 돌 때 O(n)의 시간복잡도를 가짐으로 최종적으로 O(n)으로 계산하였다.

 

이것보다 비트 연산을 통해 더 빠르고, 시간 복잡도도 줄이는 방법이 있었는데 많이 난해하여 실제 적용하긴 어려울 듯하다. 알고리즘은 더 효율적으로 문제를 해결하기 위함인데, 오히려 해당 코드를 사용하여 해석하는데 더 자원이 많이 들 것 같았다.