occidere   4년 전

문제는 long 자료형으로 고쳐서 AC 받기는 했는데, 기존에 시간초과를 받았던 BigInteger 사용 코드에 대해서 궁금한 점이 있어서 질문 남깁니다.

숫자들을 String형으로 입력받은 뒤, char[] 배열로 변환하여 2중for문으로 자릿수마다 계산하였습니다.

(그냥 String에 .charAt(i)를 사용해도 시간초과가 발생하였습니다.)

시간초과가 의심되는 부분이

  1. char numA[] = line[0].toCharArray(), numB[] = line[1].toCharArray();과 같이 String을 char 배열로 변환하는 과정
  2. String.valueOf((numA[i]-48)*(numB[j]-48))과 같이 연산 후 String으로 변환하는 과정
  3. res = res.add(new BigInteger((String.valueOf((numA[i]-48)*(numB[j]-48))))); 에서 BigInteger 객체 연산 및 재생성 부분
정도입니다.

변환비용이 그리 클것이라 생각되지는 않는데 생각보다 이것들이 시간을 오래 잡아먹는것인가요??
어느 부분에서 시간초과가 발생하는것인지 잘 모르겠습니다 ㅠㅠ

chogahui05   4년 전

1번 부분

: 시간 복잡도가 O(n)이므로 그렇게 오래 걸리진 않습니다. 공간 복잡도도 O(n)쯤 되겠네요.


2번 ~ 3번

: String의 ValueOf 코드를 보세요.

jdk 8에서는 어떻게 변했을지는 모르겠습니다만.. grepcode에서 본 걸로는..

내부적으로 Integer.toString()을 호출합니다. 이 함수는 10진수라면, toString()을 호출합니다.

 이게 아래 코드와 같은 식으로 되어 있습니다.


char형 배열을 i의 자릿수 (음수라면 1까지 더합니다.) 만치 생성한 후에, String을 새로 생성합니다.

이게 계속 반복된다면 쓸모없는 가비지가 많이 쌓일텐데요. 이걸 n^2번 반복하니.

시간 복잡도도 O(n^2), 공간 복잡도도 O(n^2)쯤 되겠네요.


물론, 가비지가 어마어마하게 쌓이면 major gc가 돌아갈 거고요.

이 비용도 사실 무시 못합니다..

실제로 제가 5600자리 x 5600자리 숫자를 ideone에서 돌려본 결과 2.347초가 걸리네요.


chogahui05   4년 전

의외로 이 주제에 대해서 질문이 포럼에 많이 올라오는 편인데요.

http://stackoverflow.com/quest...

참고해 보시면 좋을 듯 싶네요.

occidere   4년 전

와... 상세한 분석 정말 감사드립니다!!

확실히 여태까지 코드 짜면서 GC 부분은 생각을 자세히 해본 적이 없었던 것 같네요.

시스템적 부분과 더불어 API도 좀 더 꼼꼼히 읽어보는 습관을 가져아겠습니다.

덕분에 좋은 정보 많이 얻어갑니다. 감사합니다!

댓글을 작성하려면 로그인해야 합니다.