코딩 테스트 연습/백준
[C++] Baekjoon 1541번: 잃어버린 괄호
jaeheon0520
2023. 12. 18. 02:47
1. 문제
https://www.acmicpc.net/problem/1541
1541번: 잃어버린 괄호
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다
www.acmicpc.net
숫자와 부호들이 번갈아 가면서 등장하는데, 적절하게 괄호를 쳐서 만들 수 있는 최솟값을 구하면 된다.
가장 처음과 마지막은 숫자이고, 연속해서 두 개 이상의 연산자가 나타나지는 않는다.
예외처리는 고려하지 않아도 될 것 같다.
2. 풀이
마이너스가 한 번이라도 등장하면 그 뒤는 괄호 쳐서 다 마이너스 처리하면 되는 거 아닌가? 라고 생각했다.
여기까지는 쉽게 생각했는데 문제는 문자열로 입력받은 것을 어떻게 숫자와 기호로 구분할 수 있는가였다.
처음 든 생각은 숫자형 문자에 - '0'을 해주는 것이었다.
0의 ASCII 값이 48이기 때문에 어떤 숫자형 문자에 - '0'을 해주면 해당 숫자가 된다.
옛날에 42서울을 하면서 이런 식으로 풀이하는 것이 익숙해져서인지 이 방법이 먼저 떠올랐는데,
이 방법은 자릿수도 고려해줘야 할 것 같아서 어지러웠다. 그래서 그냥 편하게 stoi를 이용하기로 했다.
마이너스가 한 번이라도 등장하면, 마이너스 뒤의 숫자들은 다 빼주면 된다!
3. 코드
#include <iostream>
#include <string>
using namespace std;
int main() {
string str; // 입력 받은 문자열(식)
string num = ""; // 문자열 중에 숫자 부분을 따로 저장
bool flag = false; // 마이너스가 한번이라도 등장했는지 판단
int res = 0; // 결과값(최소값)
cin >> str;
for (int i = 0; i <= str.size(); i++) {
if (flag == false) { // 한 번도 마이너스가 나온 적 없을때
if (str[i] == '+' || str[i] == '-' || i == str.size()) { // 부호 혹은 문자열 끝을 만났을떄
if (str[i] == '+') {
res += stoi(num); //stoi 를 사용해서 문자열을 해당하는 숫자로 변환
num = ""; // 숫자 문자열 초기화
}
else if (str[i] == '-') { // 마이너스가 한번이라도 등장했다면
res += stoi(num); // 지금까지 나온건 일단 더해주고 (마이너스 앞 부분)
flag = true; // flag 를 true로 변경 (이 뒤에 나오는건 다 마이너스 연산하기 위함)
num = ""; // 숫자 문자열 초기화
}
else if (i == str.size()) { // 종료조건
res += stoi(num); // 마지막 숫자까지 계산
}
}
else {
num += str[i]; // 부호나 문자열의 끝이 아니라면 숫자이므로 숫자 문자열에 저장
}
}
else { // 음수가 한번이라도 등장해서 flag가 true가 된 경우
if (str[i] == '+' || str[i] == '-' || i == str.size()) {
if (i == str.size()) { // 끝이면 마지막 숫자 빼기
res -= stoi(num);
}
else { // 끝이 아닌 모든 경우 마이너스 연산 수행 해주면 됨
res -= stoi(num);
num = "";
}
}
else
num += str[i];
}
}
cout << res;
return 0;
}
4. 느낀점
알고리즘 분류에 그리디 알고리즘이라고 되어있었는데
음... 사실 그리디 알고리즘을 활용해서 풀었는지는 잘 모르겠다.
지금 상황에서 최선의 선택을 하다 보니 해답을 찾을 수 있는 문제긴 했는데
사실 그리디 알고리즘보다는 문자열 파싱과 간단한 수학적 사고가 더 중요했던 문제였다.
stoi를 활용할 수 있었고, C++에서는 문자열의 끝을 '\0' 이 아니라 str.size()와 같은 값으로 판단해야 한다는 것을 알게 되었다.
std::string 클래스를 잘 활용하자!
오늘 하루도 쌓였다!