문제
작성한 코드
import java.util.*;
import java.lang.*;
public class Main {
public static void main(String[] args) {
Scanner kb = new Scanner(System.in);
String input = kb.next();
int numcopy = Integer.parseInt(input);
int clap =0;
while(numcopy>0) {
int i = String.valueOf(numcopy).length();
if(i==1) {
if(numcopy%3 ==0) clap ++;
}else {
int num = numcopy;
while(i>0) {
double k = Math.pow(10, i-1);
int n = num / (int)k;
if(n%3 == 0 && n != 0) {
clap ++;
}
num = num - n*(int)k;
i--;
}
}
numcopy--;
}
System.out.println(clap);
}
}헤맸던 부분과 해결방법 및 느낀점
- 입력을 받으면, 첫번째 while문이 반복되지않는다. 즉, 입력된 수 자체만 검사하고 프로그램이 종료되는 문제.
-> 원인 : 처음에는 입력받은 수에대한 변수를 num하나로만 사용해서 while문 밖의 변수와 while문 안의 변수가 하나로 사용되었기때문에 while문이 처음 돌아간 이후에는 첫번째 while문의 조건에 충족되지않아 종료되었음.
-> 해결방법 : numcopy라는 변수를 하나 더 만들어서 while문 안과 밖의 변수가 독립적으로 돌아갈 수 있도록 해주었다. 또한 if-else문의 else의 처음에 num=numcopy로 num을 초기화해주었다. - 출력되는 숫자가 정답보다 큰 문제.
-> 원인 : 각 자리에 3,6,9가 들어가는지 알아보기위해 'n%3 ==0'인지 확인하였는데, '0%3 == 0' 인것을 놓쳤다.
-> 해결방법 : 3,6,9가 들어가있는지 검사하는 if문에 'n!=0'을 && 조건으로 추가해주었다. - 느낀점
계산이 많아지면, 변수 사용의 중첩이 일어나지 않는지 잘 체크하기.
수학적 알고리즘에서는 중학생 수학 서술형문제풀듯 변수의 범위를 먼저 나누어보고 생각하기.
몰라서 찾아본 지식
- Math.pow(밑, 지수) : 거듭제곱. -> import java.lang.Math; 필요.
직접 그린 순서도
생각한 알고리즘
사용한 알고리즘
입력된 숫자의 자릿수를 구한 후, 한 자리수와 두 자리수 이상일 때로 구분.
한 자리수일때, %3 == 0 이면 clap++
두 자리수 이상일때, 제일 큰 자릿수부터 구함 : 각 자리수에 해당하는 10의 거듭제곱수로 입력된 숫자를 나누어줌.(예를들어, 375를 입력받을 경우, 100의자리수인 3을 구하기위해 375/100)
이렇게 구해진 수가 0이아니면서 %3의 결과가 0이면 clap++.
그 다음 숫자는 '(처음 입력받은 수 - 앞에서 구했던 자리수 해당자리수의 10의 거듭제곱)/구할자릿수의 10의거듭제곱수'로 파악. (예를들어, (375-3100)/10)
...
이런식으로 입력받은 수의 파악이 끝나면, -1을 해준 후 while문을 1까지 반복.
마지막에 clap 출력.
보통 사용되는 다른 방법
수에서 10을 나누어준 후 나머지로 자릿수를 파악. 몫은 그 다음절차에 이용.
예를들어 375일경우, 375%10 == 5로 1의자리수 파악. -> 375/10 ==37 몫을 구해 다음단계에 사용 -> 37%10 ==7로 10의 자리수 파악 -> ...
시간복잡도
예상
입력받은 수를 저장하는 것 1번, 이를 numcopy에 저장하는 것 1번, clap초기화 1번, numcopy의 길이 저장 N번, numcopy%3 연산 N번, clap++ N번, numcopy-- N번, num변수 초기화 N번, Math.pow() N번, k에 대입 N번, num/k N번, n에 대입 N번, clap++ N번, nk N번, num-(nk) N번, num에 대입 N번, i-- N번
-> O(14N +3) = O(N)
최대 입력수가 1,000,000이므로 1억이 넘지않아서 1초안에 가능할것으로 판단.
결과
528ms
