백준 23082번 [균형 삼진법](C++) -yes6686- 티스토리

백준 문제 풀이: 23082 (균형 삼진법)

---

문제 링크: https://www.acmicpc.net/problem/23082

문제 설명:

주어진 정수를 균형 삼진법(Balanced Ternary)으로 변환하는 문제입니다. 균형 삼진법은 {-1, 0, 1}로 이루어진 삼진법으로, 음수를 'T'(Ten)를 사용해 표현합니다. 예를 들어, 숫자 -4는 균형 삼진법으로 'T1'로 표현됩니다.

---

문제 해결 코드

#include <iostream>
#include <string>
#include <stack>
#include <cmath>
using namespace std;

string s = ""; // 균형 삼진법 변환 과정에서 사용될 문자열
stack st; // 결과 출력용 스택

// 균형 삼진법 변환을 위한 DFS
void dfs(int n) {
    if (n == 0) return;
    dfs(n / 3);
    s += to_string(abs(n % 3)); // 3으로 나눈 나머지를 추가
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // 입력 값이 0인 경우 처리
    if (n == 0) {
        cout << 0;
        return 0;
    }

    // 절댓값으로 DFS 호출
    dfs(abs(n));

    // 균형 삼진법 변환
    for (int i = s.size() - 1; i >= 0; i--) {
        if (s[i] == '2') { // 나머지가 2인 경우
            if (i == 0) {
                st.push("T");
                st.push("1");
            } else {
                // 자릿수 보정
                s[i - 1] = (s[i - 1] == '1') ? '2' : (s[i - 1] == '2') ? '3' : '1';
                st.push("T");
            }
        } else if (s[i] == '3') { // 나머지가 3인 경우
            if (i == 0) {
                st.push("0");
                st.push("1");
            } else {
                s[i - 1] = (s[i - 1] == '1') ? '2' : (s[i - 1] == '2') ? '3' : '1';
                st.push("0");
            }
        } else if (s[i] == '1') {
            st.push("1");
        } else {
            st.push("0");
        }
    }

    // 출력 처리
    while (!st.empty()) {
        if (n < 0) { // 음수인 경우 처리
            if (st.top() == "T") {
                cout << "1";
            } else if (st.top() == "1") {
                cout << "T";
            } else {
                cout << "0";
            }
        } else {
            cout << st.top();
        }
        st.pop();
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘: 주어진 정수를 3진법으로 변환한 뒤, 균형 삼진법 규칙에 따라 각 자리의 값을 조정합니다.
• 구현 세부사항:
  • dfs(): 정수를 3진법으로 변환하여 문자열로 저장합니다.
  • 균형 삼진법 변환: 3진법 변환 후, 나머지 값이 2 또는 3인 경우 다음 자리로 올림하며 'T' 또는 '0'으로 조정합니다.
  • 음수 처리: 음수 입력 시 'T'와 '1'의 역할을 반대로 출력합니다.
• 시간 복잡도 분석:
  • 3진법 변환의 반복 횟수는 O(log₃ n)입니다.
  • 변환 후 자릿수 처리와 출력은 O(log₃ n)입니다.
  • 전체 시간 복잡도는 O(log n)입니다.

---

결과

주어진 정수를 균형 삼진법으로 정확히 변환하여 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!