[C++] 백준 1541번 잃어버린 괄호

문자열을 파싱하는 문제.

식을 해석하는 문제는 나같은 경우는 큐 자료구조를 이용해서 많이 푼다.

 

문제 접근 방식

우선 어떻게 해야 식의 값이 최소가 되는지를 알아보려고 했다.

식에 더하기와 빼기밖에 없으므로, 어떤 경우로 식을 처리를 해야 최소값이 될 수 있을지

혼자 식을 따로 적어서 생각해 보았다.

 

일단 식의 계산을 맨 앞에 숫자부터 해야된다고 가정할때,

10+20-10-20+30-20 -> 10+20-10-(20+30)-20

다음 식 같은 경우를 만들어서 살펴보았는데 다음과 같은 두 가지 경우를 고려하게 되었다.

1. +의 경우는 그냥 앞에서 계산한다.
2. -의 경우, 바로 뒤의 식이 +이면 +를 먼저 계산한다 (즉, 괄호를 씌워준다.) / 아니라면 그냥 앞에서 계산한다.

이렇게 고려해줄 경우 식의 값이 최소값이 되게 된다.

 

문제 풀이

먼저 식이 문자열의 형태로 주어지기 때문에 파이썬이 아닌 경우라면

문자열을 숫자와 연산자로 나누는 작업이 필요하다.

사실 이 부분만 할 줄알면 나머지는 쉬운 작업이라 생각한다.

 

사용한 STL과 변수

숫자를 담을 큐 q_num과 연산자를 담을 큐 q_oper를 사용했다.

그리고 문자열을 입력받을 input 문자열을 만들었다.

 

메인함수 - 1

문자열을 입력받은 후, 문자열을 순차적으로 살펴준다.

정수형 변수 tmp가 있는데, 이는 예를들어 12345라는 문자열을 숫자로 변경할 경우

1 -> 1*10 + 2 = 12 -> 12*10 + 3 = 123 -> 123*10 + 4 = 1234 -> 1234*10 = 12345

의 형태로 입력을 받게 했다.

그리고 문자열에 있는 문자에서 숫자 문자 '1'~'9'는 '0'을 빼면 정수 1~9를 가지게 된다.

(ASCII 코드를 빼주는 것이므로 이렇게 된다 !)

그리고 숫자를 입력할 때마다 tmp를 0으로 초기화 해줌으로써 현재 내가 보고있던 숫자가 없다는 것을

알려줘서 무조건적으로 처음에 접하는 숫자는 입력을 받도록 만들었다.

 

다시 돌아와서 반복문의 조건문을 살펴보자면

• 연산자의 입력이 아닐 경우

1. 만약 마지막 숫자라면 tmp에 10을 곱해준 후 현재 문자열에서 보고있는 마지막 자리 수를 더해주고 정수를 담는 큐에 넣는다.
2. 만약 tmp가 0이라면 현재 내가 아무 숫자도 보고있지 않다는 상황이므로(연산자를 담은 후 이므로) 무조건 현재 보고있는 숫자를 더해준다.
3. 둘 다아니라면 tmp에 10을 곱해준 후 현재 문자열에서 보고있는 수를 더해준다.

• 연산자의 입력일 경우

1. tmp에 저장된 수를 정수를 담는 큐에 넣고 tmp를 0으로 초기화 해줘서 다음 수는 무조건 입력을 받도록 만든다.
2. 연산자를 담는 큐에 연산자를 담는다.

메인함수 - 2

식의 경우 무조건 숫자가 연산자보다 1개 더 많게 된다.

따라서 정수 큐에 있는 숫자 한 개를 미리 빼두고 결과값을 담는 result변수에 담아둔다.

그리고 정수 큐가 비어있지 않을 때까지 반복문을 돌리게 되는데, 이 때 연산자 큐에서 꺼낸 연산자가

1. '+'라면 그냥 현재 보고있는 수와 결과값을 담을 변수 result를 더해준다.
2. '-'라면 연산자 큐의 front가 '+'가 나올때까지 현재 수를 더해주고 result에서 빼준다. (괄호처리)

이렇게 하고 result를 출력한다.

식을 문자열로 파싱해서 푸는 문제였다.

생각보다 조건을 짜는게 까다로웠지만

문자열에서 숫자를 어떻게 파싱하면 좋을지 생각해보게된 좋은 문제였던 것 같다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인이 가능하다.