📌 https://www.acmicpc.net/problem/3460
백준 3460번 문제, "이진수 변환" 문제를 풀면서 겪었던 다양한 이슈와 최적화 방법에 대해 이야기해보려고 합니다.
저처럼 25%에서 에러가 발생해서 머리를 쥐어뜯었던 분들이라면 꼭 끝까지 읽어보세요!
⭐ 이슈 해결 방법
1️⃣ 첫 번째 이슈 : 25%에 틀렸습니다. 발생 >> 잘못된 입력 방식
코드에 문제가 없는데 25%에서 ArrayIndexOutOfBoundsException이 발생했습니다.
아무리 눈을 갈아 끼고 찾아봐도 에러가 안 보여서 질문 게시판을 찾아보니 아래와 같은 답변을 찾았습니다.
이 문제가 입력 예제가 단 하나만 주어져 있어서 제 멋대로 해석해서 테스트 케이스를 한줄에 입력받고 그다음 각 테스트케이스를 한 줄에 띄어쓰기로 입력받아버려서 발생한 에러였습니다.
이 문제는 저 답변 내용처럼 입력을 테스트 케이스를 한 줄에 입력받고 그다음 각 테스트 케이스마다 한 줄씩 입력받아야 했습니다..
사실 위 사진처럼 입력, 출력 방식을 글로 설명하고 있긴 했지만,, 평소에 입력, 출력 방식을 글로 읽어 이해하지 않고 예제를 보고 이해해 오던 제 잘못입니다..🥲
다음부터는 최대한 입력, 출력 글을 읽고 이해한 후에 입출력 예제를 보고 제가 이해한 방식이 맞는지 확인하는 방식으로 해야 할 거 같습니다! 절대 예제를 보고 이해하지 마!!
왕자는 저처럼 25%에 NoSuchElementException이라는 에러가 발생해서 다른 에러일 줄 알았는데 저와 같은 입력 처리의 문제였습니다. 에러 메시지가 "25%에서 실패합니다"라고만 나온다면 입력 오류일 수 있으니, 입력 방식을 다시 한번 점검해 보는 것이 좋을 거 같습니다!
어떻게 둘 다 이렇게 똑같이 잘못 이해했지?
2️⃣ 두 번째 이슈 : 10진수 → 2진수 변환에서 발생한 혼동 💦
이건 소개하기 전에 해명부터 하자면, 첫 번째 이슈를 해결할 때 전두엽과 후두엽의 위치가 바뀌어버려서 사고가 정지했습니다.
게다가 이 문제가 2진수를 반대로 출력해야 해서 사고를 정지시키다 못해 그냥 꼬여버렸는데요?
어떤 이슈인지 소개해드리도록 하겠습니다..
일반적으로 10진수를 2진수로 변환할 때, 큰 자릿수부터 채워나가는 방식(역순)을 사용합니다.
예를 들어, 13이라는 숫자는 2진수로 변환하면 1101이죠. 여기서 2의 제곱수 자리(8, 4, 2, 1)를 기준으로 8, 4, 1 자리만 1로 채우는 방식입니다.
하지만 이 문제에서는 작은 자릿수부터 출력해야 했기 때문에, 13의 2진수 값인 1101이 아닌 1011로 출력해야 했습니다..!
여기까진 괜찮아서 그냥 제가 생각하는 대로 코드를 만들어서 정답이긴 했는데요.
왕자 코드가 더 좋아 보여서 왕자 코드를 이해하면 리팩터링 할 때 이 순서 차이 때문에 순간적으로 혼동을 겪었습니다.
왕자는 이러한 역순 출력 방식을 이용해서 배열이나 리스트를 사용하여 나머지를 저장하지 않고, 바로 나머지를 계산하면서 출력하는 방법을 사용했습니다. 쏘지니어스.. 계략왕...
이게 무슨 말이냐 하면,
10진수를 2진수로 변환할 때, 10진수 값을 2로 나누어 떨어지지 않을 때까지 나누어 가며 나온 몫을 시작으로 그 역순으로 올라가며 나머지를 순서대로 쓰면 2진수 값이 나오잖아요?!
근데 저는 이 방식을 그대로 사용해서 나누어 떨어지지 않을 때까지 나누어 가며 나온 나머지들을 배열에 저장해 갔고, 마지막으로 나누어 떨어지지 않을 때까지 나누며 나온 몫까지 저장했습니다. 그리고 원래 진정한 2진수는 위 사진처럼 반대로 출력해야 하기 때문에 이 배열을 역순으로 출력해야 했지만, 이 문제에서는 인덱스가 낮은 것부터 출력해야 했기에 결국엔 배열 순서대로 출력했습니다.
그렇기 때문에 결국엔 나머지가 나올 때마다 출력을 했으면 되는 건데 굳이 배열을 통해 마지막 몫까지 저장한 후에 구한 순서대로 출력하고 있던 거죠..
사실 이때 바로 어? 배열 안 쓰고 나머지를 구할 때마다 출력해야겠다!라는 사실을 깨달았어야 했지만, 위에서 말했듯이 사고가 멈춰버렸습니다.
이 정도 되면 왕자의 코드 구현 방식이 궁금하실 거 같으니 보여드리겠습니다.
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
// int[] a = new int[n];
for (int i = 0; i<n; i++){
// ArrayList<Integer> aa = new ArrayList<>();
// a[i]=Integer.parseInt(br.readLine());
int a = Integer.parseInt(br.readLine());
int index = 0;
while(a>0){
if(a % 2 != 0){
sb.append(index + " ");
}
a/=2;
index++;
}
sb.append("\n");
}
System.out.println(sb);
}
}이 코드를 보면, a를 2로 나눌 때 나머지가 1인 경우 즉시 인덱스를 출력하고, 그 이후에는 몫을 계속해서 2로 나눠나갑니다. 이렇게 하면 역순으로 배열에 저장할 필요 없이 인덱스가 작은 것부터 바로 출력할 수 있어서 시간과 공간 복잡도를 모두 줄일 수 있었습니다.
왕자랑 저는 이후에도 멈추지 않고, 어떻게 하면 여기서 더 시간복잡도와 공간복잡도를 줄일 수 있을지 고민했습니다!
이 문제는 입력값에 따라 출력을 엄청 많이 할 수도 있기 때문에 아래에 보이듯 수많은 출력 방식을 시도해 봤는데요!
이 문제는 특히 StringBuilder를 사용했을 때 가장 빠르고 공간 복잡도도 적은 것을 확인할 수 있었습니다.
저희는 이러한 노력 끝에
이 문제의 1,2등을 할 수 있었습니다!
🙏🏻 최고의 효율 코드를 보여준 왕자에게 😘
ps. 이 글을 마무리하며 이 문제를 풀면서 고난의 필기 노트.. 사진 첨부
