알고리즘 문제 - 정수
시리즈 "알고리즘 문제풀기" 개요
- 1~2주 (최소) 1개 문제 풀기를 목표로 한다.
- JavaScript 로 푼다.
문제
Baekjoon Online Judge - 1040. 정수
자연수 N
과 K
가 주어질 때, N
보다 크면서 K
개의 서로 다른 숫자로 이루어진 수 중 가장 작은 수를 찾는 문제이다.
접근
가장 처음 든 생각은 "백트래킹으로 가능한 숫자를 찾으면 되지 않을까?" 였다. 높은 자릿수부터 숫자를 하나씩 채워가면서, 조건에 맞는 숫자를 만드는 방식이었다.
브루트포스 만큼은 아니라도 오래 걸릴 방법이라서 N
의 범위가 큰 게 조금 불안하긴 했지만 (N
은 1018보다 작거나 같은 자연수), 가능한지 아닌지 궁금하기도 했기 때문에 일단 시도해봤다.
시도
시도 결과
로컬에서는 문제 없이 동작하지만 채점 페이지에 제출하면 "시간 초과"로 통과하지 못한다.
아무래도 현재 코드에서는 어떻게 개선을 해봤자 "시간 초과"의 늪에서는 벗어나지 못할 것만 같은 느낌이 들었다. 역시 백트래킹은 정답이 아닌 것 같았다.
어떤 방법으로 풀어야할까 고민하다가 얼마전에 이 문제 관련해서 들었던 조언과 구글링을 토대로, "현재 숫자에서 낮은 자릿수부터 숫자를 하나씩 바꿔가며 답을 찾아보는" 방법을 쓰기로 결정했다.
풀이
후기
드디어 해결되었다.
물론 한 번에 채점을 통과하지는 못했다.
백준이 릿코드와 다른 점은 채점이 실패했을 경우 반례도 직접 찾아야 한다는 건데, 이게 다양하게 생각하게 해줘서 좋은 점도 있는가 하면 도저히 반례가 떠오르지 않을 경우 답답해서 미칠 것 같다는 나쁜 점도 있다. 특히 마지막에 발목 잡은 반례를 결국 직접 찾지 못해서 질문 게시판에서 반례를 찾았다.
문제를 푸는 방법도 스스로 생각해낸 것이라기 보다는 아니라 조언과 구글링을 통해 얻었으니, 스스로 풀었다고 하기에는 민망하다.
아무래도 많은 문제를 꾸준히 풀어봐야 겠다는 생각이 든다. 푸는 방법을 많이 아는 것도 중요하지만 역시 실전에서 겪어보는 게 최고인 것 같다. 실전에서 부딪혀 얻은 키워드는 맹목적인 공부를 통해 얻은 키워드보다 선명하게 기억에 남는다. 1~2주에 한 문제를 풀겠다는 목표도 제대로 못 지키고 있는데 좀 더 신경써서 최소 1주에 한 문제를 푸는 걸 목표로 해야겠다.