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
'BAEKJOON > 그리디' 카테고리의 다른 글
백준 20365번 [블로그2](C++) -yes6686- 티스토리 (0) | 2024.09.10 |
---|---|
백준 20937번 [떡국](C++) -yes6686- 티스토리 (4) | 2024.09.04 |
백준 17521번 [Byte Coin](C++) -yes6686- 티스토리 (4) | 2024.09.02 |
백준 2891번 [카약과 강풍](C++) -yes6686- 티스토리 (2) | 2024.09.01 |
백준 29198번 [이번에는 C번이 문자열](C++) -yes6686- 티스토리 (1) | 2024.08.30 |