문제
작성한 코드
import java.util.Scanner;
public class commonFactor {
public static void main(String[] args) {
Scanner kb = new Scanner(System.in);
String num = kb.nextLine();
String inputs = kb.nextLine();
int min = 100000000;
String[] strArr = inputs.split(" ");
int len = strArr.length;
for(int i =0; i<len; i++) {
if(Integer.parseInt(strArr[i]) <min) {
min = Integer.parseInt(strArr[i]) ;
}
}
switch(len) {
case 2:
for(int n=1; n<=min; n++) {
if(Integer.parseInt(strArr[0]) % n == 0 && Integer.parseInt(strArr[1]) %n == 0) {
System.out.println(n);
}
}
break;
case 3:
for(int n=1; n<=min; n++) {
if(Integer.parseInt(strArr[0]) % n == 0 && Integer.parseInt(strArr[1]) %n == 0 && Integer.parseInt(strArr[2]) %n == 0) {
System.out.println(n);
}
}
break;
}
}
}헤맸던 부분과 해결방법 및 느낀점
-
테스트 케이스를 보고, 처음 입력에 2를 넣어주자 Exception in thread "main" java.lang.NumberFormatException: For input string: "" 라는 에러가 났다.
-> 원인 : 단순하게는 주석처리해둔int num = kb.nextInt();때문인것같았다.
-> 해결방법 : 단순하게는 int로 받는 형식문제같아서 String으로 받아서 해결하였다.
-> 근본적인 에러의 원인 : 숫자가 아닌것을 숫자로 변환하려고해서 일어나는 문제. -
처음에 테스트케이스를 다 입력했는데도, 결과가 뜨지않고 또 다른 입력을 기다리는 상태에 놓여있는 문제가있었다.
-> 원인 : 첫번째 if문에서 입력받은 수와 초기화해둔 min을 비교해서 입력받은 숫자에서 최소값을 구하는데, 처음에 min을 0으로 설정해두어서 일어난 문제였다. min=0으로 해두면, 결국 min값은 바뀌지않을텐데 로직에서 생각을 잘못한것같다.
-> 해결방법 : 최대입력값이 100000000이므로 min의 초기화값을 100000000로 수정하였다. -
공약수를 구해야하는 숫자가 2개 혹은 3개가 들어오는데, 공약수를 구하는 로직에서 입력되는 숫자의 개수가 달라질 수 있는부분을 어떻게 처리해야할지 고민이었다. 입력되는 개수 상관없이 하나의 로직으로 해결하고싶었는데 방법이 생각이나지않았다. 또한 같은결로 만약 입력되는 숫자의 개수가 정해지지않는다면 이를 어떻게 해결해야할지도 문제이다.
-> 해결방법 : switch문을 사용해서 입력받은 숫자의 개수가 2개일때와 3개일때의 케이스를 나누어주었다.
-> 입력 개수 상관없이 가능한 로직 : 이중 for문으로 외부for문에는 나머지연산을 해줄 자연수(n)을 변수로, 내부 for문에는 입력된 숫자배열의 인덱스를 변수로해서 돌리고, 내부 for문에서 연산의 결과가 0이되면, 0으로 초기화되어있던 count변수를 ++해준다. 그리고 내부 for문이 끝난 후 count변수의 결과가 주어진 숫자의 개수와 같으면, 모두 0으로 나누어떨어졌다는말이기때문에 해당 n은 공약수로 출력한다. -
공약수를 구하는 로직을 어떻게 구현해야할지 고민이었다.
-> 결론 : 각 숫자의 약수구하는 로직에서 각각을 &&로 묶어서 조건을 형성해준다. 여기서 공약수는 가장 작은수보다 클 수 없으므로, 1부터 구하려는 숫자들 중 가장작은수까지만 %연산으로 검사한다. -
아, 갑자기 생각난건데 strArr의 길이를 구해서 len변수를 따로 생성하는것보다, len대신 처음에 입력받은 num을 사용하면 자원낭비를 줄일수있을것같다.
-> 수정결과 : 2048ms(수정 전, len변수 사용) -> 2384ms(수정 후, 처음 입력받은 num사용)
-> 의문점 : 변수를 하나 덜 사용했는데, 예상과 달리 왜 시간이 증가하였을까?int num = Integer.parseInt(kb.nextLine());이렇게 num을 String으로 받은 후, Int로 형변환해주었던것이 문제인걸까?
->
몰라서 찾아본 지식
-
약수구하는 로직 : 약수를 구하고싶은 수가 x라면, 1 <= n <=x를 for문으로 x%n==0이 되는 n을 구한다. 이 n이 약수이다.
-
공백 포함해서 입력받은것을 공백을 기준으로 문자열배열에 저장하기 : String[] strArr = new String[]로 객체생성을 먼저해주고, 여기에 값을 삽입하려고했는데, 이전에 이런 과정을했던 기억이나서 찾아보니, String[] strArr 선언과 동시에 inputs.split(" ")로 초기화해줄 수 있었다.
생각한 알고리즘
입력받을수의 개수를 입력받고, 공백을 포함하여 숫자들을 한 번에 String으로 입력받는다.
입력받은 숫자들은 공백을 기준으로 나누어서 배열에 저장한 후 배열원소들 중 최소값을 찾는다.
입력받은 숫자의 개수가 2개일때와 3개일때를 나누어서 생각하되, 1부터 최소값까지 n으로 for문을 돌면서 입력받은 숫자에 나머지연산(%n)을 한다. 이 연산의 결과가 모두 0이되는 n을 공약수로 출력한다.
시간복잡도
예상
num을 받아서 저장 1번, 숫자들을 받아서 inputs에 저장 1번, min 초기화 1번, strArr에 배열저장 1번, len길이 저장 1번, i=0 1번, min 업데이트 len번, n=1 1번, %n연산 2min번, n=1 1번, %n연산 3min번
-> 총 8 + len + 5min = min = O(N)
최대 입력값이 100000000이하이므로 1초이하로 가능할것같다.
결과
2048ms
-> 의문점 : 1000ms가 1초인데, 2048ms면 2초를 넘은것아닌가? 1초시간제한인 문제인데 시간초과가 뜨지않고 왜 정답입니다가 떴을까?
-> 해결:
