본문 바로가기

BAEKJOON/그리디

백준 20310번 [타노스](C++) -yes6686- 티스토리

728x90
SMALL

백준 문제 풀이: 20310 [타노스]


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

문제 설명:

주어진 이진 문자열에서 '1'의 개수와 '0'의 개수를 각각 절반씩 제거하여 가장 작은(사전 순으로 빠른) 문자열을 만드는 문제입니다. 입력된 문자열은 '0'과 '1'로만 이루어져 있으며, 항상 짝수 개의 '1'과 짝수 개의 '0'이 주어집니다. 문자열을 재구성할 때, 가능한 한 사전순으로 가장 작은 결과를 출력해야 합니다.


문제 해결 코드


// 타노스 문제 해결 코드
#include <iostream>
#include <algorithm>
using namespace std;

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

    string s;
    cin >> s;

    // '0'과 '1'의 개수를 세기
    int zeroCnt = count(s.begin(), s.end(), '0');
    int oneCnt = count(s.begin(), s.end(), '1');

    // 각 절반 개수를 제거할 필요가 있음
    zeroCnt /= 2;
    oneCnt /= 2;

    string ans = "";

    // '1' 제거 단계
    for (char c : s) {
        if (c == '1' && oneCnt > 0) {
            oneCnt--;
        } else {
            ans += c;
        }
    }

    s = ans;
    ans = "";

    // '0' 제거 단계 (뒤에서부터 제거)
    for (auto it = s.rbegin(); it != s.rend(); ++it) {
        if (*it == '0' && zeroCnt > 0) {
            zeroCnt--;
        } else {
            ans += *it;
        }
    }

    // 뒤집어 최종 결과 생성
    reverse(ans.begin(), ans.end());
    cout << ans;

    return 0;
}

코드 설명

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

  • 핵심 알고리즘: 문자열 탐색 및 두 개의 반복문을 사용해 사전 순으로 가장 작은 결과를 만듭니다. 먼저 '1'을 제거한 뒤, 남은 문자열에서 '0'을 제거하며 뒤에서부터 처리합니다.
  • 구현 세부사항:
    • 입력 문자열에서 '0'과 '1'의 개수를 카운트합니다.
    • 사전 순으로 작은 문자열을 만들기 위해, 먼저 문자열을 앞에서 탐색하여 '1'을 제거합니다.
    • 그 다음, 문자열을 뒤에서 탐색하며 '0'을 제거합니다.
    • 최종적으로 남은 문자열을 뒤집어 출력합니다.
  • 시간 복잡도 분석:
    • '0'과 '1'의 개수를 세는 과정: \(O(n)\)
    • '1' 제거와 '0' 제거 과정: 각각 \(O(n)\)
    • 최종 결과 뒤집기: \(O(n)\)
    • 전체 시간 복잡도: \(O(n)\)

결과

입력된 이진 문자열을 처리하여 사전순으로 가장 작은 결과를 출력합니다. 예를 들어:

  • 입력: 11011000
  • 출력: 100

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

728x90
LIST