문제를 다시 읽어보니
수의 길이가 333,334를 넘지 않는다는 것이었다.
나는 크기가 333,334를 넘지 않다는 줄 알고 그냥 int로 풀면
8^5 * 9를 해도 10자리를 넘기지 않으니 충분히 가능할 것이라고 예상
하지만 Inputmismatch가 떠서 다시 문제를 보니 크기가 아니라 길이였다.
따라서 BigInteger로 풀어보자 생각
하지만 BigInteger는 메모리를 많이 차지하기 때문에
import java.util.*;
import java.math.*;
class Main{
public static String solution(String N) {
BigInteger NN = new BigInteger(N);
BigInteger ship = new BigInteger("10");
String answer="";
int ten=0,i=0;
Stack<Integer> two = new Stack<>();
while(NN.compareTo(new BigInteger("0"))==1) {
ten+=NN.remainder(ship).intValue()*Math.pow(8,i);
NN=NN.divide(ship);
i++;
}
while(ten>=1) {
two.add(ten%2);
ten=ten/2;
}
while(two.size()>0) {
answer+=two.pop();
}
return answer;
}
public static void main(String[] args){
Scanner kb = new Scanner(System.in);
String N = kb.next();
System.out.println(solution(N));
}
}
위와 같이 풀었더니 아니나 다를까 시간초과가 발생하였다.
따라서 줄일 수 있는 방법을 다시 생각해본다.
import java.util.*;
class Main{
public static int solution(String N) {
String[] arr = {"000","001","010","011","100","101","110","111",};
String answer="";
for(char x : N.toCharArray())answer+=arr[x-'0'];
return Integer.valueOf(answer);
}
public static void main(String[] args){
Scanner kb = new Scanner(System.in);
String N = kb.next();
System.out.println(solution(N));
}
}
그 이유는 내가 String에 값을 붙일 때 +값 을 사용했기 때문이다.
String은 불변하기 때문에 값을 변경할 수 없어서 .concat이나 +를 이용하여 값을 변경한다. 이는 기존 String에 들어있던 값을 버리고 새로 값을 할당하는 것이기 때문에 이를 많이 사용할 경우 속도가 느려진다.
위 그래프를 보면 알 수 있듯이 StringBuffer나 StringBuilder를 사용해야 한다. 이 두 방법은 값이 변하기 때문에 .append()나 delete()를 사용해서 값을 변경시킬 수 있다.
이 중
StringBuffer는 공통 메소드가 동기화되므로 멀티쓰레드 환경
그 외에는 StringBuilder를 사용하는 것이 더 성능이 뛰어나다.
함수 | 용도 |
---|---|
sb.append(값) | StringBuffer, StringBuilder 뒤에 값을 붙인다. |
sb.insert(인덱스, 값) | 특정 인덱스부터 값을 삽입 |
sb.delete(인덱스, 인덱스) | 특정 인덱스부터 인덱스까지 값을 삭제 |
sb.indexOf(값) | 값이 어느 인덱스에 들어있는지 확인 |
sb.subString(인텍스, 인덱스) | 인덱스부터 인덱스까지 값을 자라옴 |
sb.length() | 길이 |
sb.reverse() | 글자 순서를 뒤집기 |
import java.util.*;
class Main{
public static StringBuilder solution(String N) {
if(N.equals("0"))
return new StringBuilder("0");
String[] arr = {"000","001","010","011","100","101","110","111"};
StringBuilder answer = new StringBuilder("");
for(char x : N.toCharArray())
answer.append(arr[x-'0']);
System.out.println(answer);
while(Character.compare(answer.charAt(0),'0')==0){
answer.delete(0,1);
System.out.println("a"+answer);//
}
return answer;
}
public static void main(String[] args){
Scanner kb = new Scanner(System.in);
String N = kb.next();
System.out.println(solution(N));
}
}
여기서 while(Character.compare(answer.charAt(0),'0')==0) 부분을 다시 한번 볼 필요가 있다.
만약에 N이 "0"인 경우 answer="000"이 된다. answer이 저 while문을 도는 경우 answer의 길이가 0이 되는 순간이 있는데 그 때 charAt(0)을 하면 StringIndexOutOfBoundsException이 발생한다.
따라서 처음에 애초에 N이 "0"인 경우에는 return값이 0이 되도록 설정했다.