TIL
오늘 한 일
- 휴식
- leetcode
- 2 Keys Keyboard. (medium)
문제 풀이
2 Keys Keyboard. (medium)
화면에 보이는 문자열 모두를 (일부 불가) 복사하는 버튼과 복사한것을 붙이는 버튼 두개만 있는경우 주어진 숫자만큼 화면에 보이는 문자의 길이를 늘리되 버튼 조작 횟수를 최소로 하는 문제이다.
해당 문제를 풀기위해 가장 먼저 생각한 것은 2배수와 아닌것을 부류 하는 부분이다. 2의 배수의 경우 현재 화면것을 복사하고 붙이는 두 과정만 필요하지만, 그외의 경우 적절한 크기의 값과 적절한 횟수를 구분하여 적용해야하기 때문이다. 또한 1부터 차근 차근 올라가는것이 아닌 최종 갯수에서 부터 1로 내려가는 방식이 이행하기 편했기에 그렇게 진행하였다.
우선 while 구문으로 주어진 숫자 1보다 클때 루프를 돌게 하였다. 그리고 현재 주어진 수가 2의 배수인지 아닌지 구분하였고 2배수인 경우 결과에 시행횟수 2를 추가하고 현재 숫자 n을 반으로 나누었다.
그외의 경우 해당숫자가 몇의 배수인지 파악하는 과정을 필요로 하였다. 우선 가장 큰수를 주어진 숫자의 제곱근으로 정의하였는데 이후 이부분에서 문제가 발생하였다. 27을 대상으로 보면 9로 나누로 3회, 3으로 나누고 3회, 1에서 3회, 총9회만 필요하지만 제곱근의 경우 9를 제외하고 3부터 시작하여 3 에서 9회, 1에서 3회, 총 12회를 필요로 하였다. 해서 해당 부분을 제곱근이 아닌 반으로 나눈 값을 올림처리한수를 가장 큰수로 정의 하였다.
반으로 나눈 값부터 1까지 차근 차근 나누어 떨어지는 가장 큰 수를 찾는다. 그리고 그 가장 큰수로 나누어 떨어지는 수를 시행횟수로 삼고 가장 큰수를 다음 계산할 n으로 정의하였다.
이 과정을 반복하면 문제에서 요구하는 최소 조작 횟수를 찾을수 있었다.
오늘은...
휴식
