[SWEA/Java] 4366. 정식이의 은행 업무

[SWEA/Java] 4366. 정식이의 은행 업무

SW Expert Academy

---

문제 해석

이 문제는 정식이가 잘못 기억하는 2진수와 3진수 표현으로부터 원래의 송금 금액을 추측해내는 것이다. 정식이는 각 숫자 표현에서 한 자리씩 오류를 범했다는 것을 알고 있다. 문제 해결을 위해 2진수의 각 자리를 바꿔 가며 해당 값을 10진수로 계산하고, 이를 3진수의 각 자리를 변형시켜 얻은 값들과 비교하여 일치하는 순간을 찾아야 한다.

풀이 과정

1. 입력 처리: 각 테스트 케이스 별로 2진수와 3진수를 입력 받는다. 이들을 정수 배열로 변환하여 저장한다.
2. 2진수 변형 및 계산: 2진수의 각 자리를 바꿔가며 10진수로 변환한다.
3. 3진수 변형 및 계산: 3진수의 각 자리를 바꿔가며 10진수로 변환한다. 이 때, 2진수에서 변환된 10진수 값과 일치하는지 검사한다.
4. 일치 검사: 일치하는 값이 발견되면 해당 값을 결과로 설정하고, 검색을 종료한다.

코드

package edu.ssafy.im.SWEA.D4.No4366;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Solution {
    int[] n, m;  // n은 2진수, m은 3진수를 저장하는 배열
    int ans;  // 추측된 송금 금액

    public static void main(String[] args) throws NumberFormatException, IOException {
        new Solution().io();
    }

    private void io() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int testCase = Integer.parseInt(br.readLine());

        for (int t = 1; t <= testCase; t++) {
            String s = br.readLine();
            n = new int[s.length()];
            for (int i = s.length() - 1; i >= 0; i--) {
                n[s.length() - 1 - i] = s.charAt(i) - '0';  // 2진수 역순으로 저장
            }

            s = br.readLine();
            m = new int[s.length()];
            for (int i = s.length() - 1; i >= 0; i--) {
                m[s.length() - 1 - i] = s.charAt(i) - '0';  // 3진수 역순으로 저장
            }

            sol();

            sb.append("#").append(t).append(" ").append(ans).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private void sol() {
        for (int i = 0; i < n.length; i++) {
            n[i] = n[i] == 1 ? 0 : 1;  // 2진수 자리 바꾸기
            int binarySum = binaryToNum();  // 변형된 2진수를 10진수로 변환
            for (int j = 0; j < m.length; j++) {
                int tmp = m[j];
                for (int k = 0; k < 3; k++) {
                    if (k != tmp) {
                        m[j] = k;  // 3진수 자리 바꾸기
                        int trinarySum = trinaryToNum();  // 변형된 3진수를 10진수로 변환
                        if (binarySum == trinarySum) {  // 10진수 값이 일치하면
                            ans = binarySum;  // 정답 저장
                            return;  // 반복 종료
                        }
                    }
                }
                m[j] = tmp;  // 원래 3진수 값 복원
            }
            n[i] = n[i] == 1 ? 0 : 1;  // 원래 2진수 값 복원
        }
    }
    
    private int binaryToNum() {
        int sum = n[0];  // 가장 낮은 자리 값
        for (int i = 1; i < n.length; i++) {
            sum += n[i] * Math.pow(2, i);  // 2진수를 10진수로 계산
        }
        return sum;
    }

    private int trinaryToNum() {
        int sum = m[0];  // 가장 낮은 자리 값
        for (int i = 1; i < m.length; i++) {
            sum += m[i] * Math.pow(3, i);  // 3진수를 10진수로 계산
        }
        return sum;
    }
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(n * m)이다. 여기서 n은 2진수의 길이, m은 3진수의 길이를 나타낸다. 각 2진수 자리마다 모든 3진수 자리를 변경하며 검사한다.

느낀점

이 문제는 복잡한 숫자 변환과 조건 검사를 통해 문제를 해결해야 하므로, 시스템적인 접근과 철저한 디버깅이 필요하다. 다양한 진법 사이의 변환과 조건 검사를 통해, 복잡한 문제를 해결하는 데 있어서 프로그래밍 능력을 강화하는 좋은 기회가 되었다.