1065_한 수
이제 부터 하루에 한문제씩 내가 풀었던 문제들을 설명을 덧붙여 올리려고한다.
문제를 다시 풀면서 나에게도 도움이 될 것이도 쌓아놓으면 나중에 쓰임새도 있을 것 같고 그리고..
알고리즘 공부를 하면서 나 스스로도 찾아볼만한 마땅한 자료가 없어서 힘들었다
비록 내 코드가 다른 분들에 비해 잘짜여진 코드도 아니지만 공부하시는 분들이 (이문제에 어려움을 겪고있는 분들이) 내 코드를 보고 아 이런 아이디어도 있구나! 할 수있었으면 좋겠다
그리고 내 코드를 보고 비판 해주실 분도 있으시면 더욱 좋을 것 같다
우선, 한수 문제는 등차수열을 이루는 수의 개수를 구하는 문제이다
N으로 자연수가 주어지고 우리는 N보다 작거나 같은 한수의 개수를 출력하면 된다.
이문제를 처음 풀 때에 궁금했던 것이 1 2 3 ... 9는 한수인가? 였는데 한수이다! 예제를 풀어보면 바로알 수 있다.
1) 1부터 99까지는 모든 수가 한수이기 때문에 우선 N이 99보다 작은 수가 들어오면 그냥 그대로 N을 출력해주었다.
2) 자, 그럼 99보다 큰, 즉 3자리 이상의 수가 들어오면?
100부터 한 개씩 n까지 돌면서 검사를 해주어야한다. cnt 라는 count용 변수를 사용한다.
0으로 설정해 놓은 다음 한 수가 나올 때 마다 더해주는것이 일차적인 개념이다.
자 그러면 그 한수는 어떻게 구할 수 있을까?
등차수열의 첫째 개념은 "공차"이다. (공차먹고싶다...ㅈㅅ...)
공차는 쉽게 0번째 수 와 1번째 수의 차이를 구하면되는데, 문제는 우리가 받은 입력이 int형이라는 것이다.
int형 변수로는 각 자리수에 쉽게 접근할 수 없기 때문에 string으로 전환해주는 과정이 필요하고 이를 도와주는 함수가 to_string함수이다. string.h 라이브러리에 존재하는 함수이다.
이것을 이용해서 공차를 구한 후 부터는 뒤로 쭉쭉 나아가며 앞뒤 수의 차이가 공차와 일치하는지를 판단하면 된다.
만약 공차와 일치하지 않는 시점이 나온다면 flag를 false로 설정해주면 된다.
포문을 나온 후 아직 flag가 true라면 공차가 틀린 적이 없는 것이므로 한수이다!
그렇다면 cnt에 값을 더해주면 된다.
시간복잡도는 O(n)으로 해결된다.
중간에 이중포문이 나오지만, 그래봤자 수의 자릿수만큼 돌아가는 것이기 때문에 N의 최대값이 들어와도 그리 큰 영향이 없다.
자세한 코드는 아래에...