[백준] 5875 오타

5875번: 오타

 

 

풀이 아이디어

어떻게 풀어야 되나 고민했지만, 아이디어를 떠올리지 못해

누적합이라는 태그를 봐버렸고, 누적합을 사용 할 수 있었다.

 

먼저 누적합이란 것을 알고나면

괄호를 수정했을 때 경우의수가 1개이상 나오는 데이터들은

누적합이 2나 혹은 -2라는 것을 알 수 있다.

(괄호의 갯수가 2개 차이나야 하니)

 

일단 이 이외에 모든 경우는 제외시키자.

 

그 다음

누적합을 통해 양쪽방향으로 각각 한번씩 누적합을 구해

괄호 갯수에 대한 갯수를 구한다.

 

그렇게하면

특정 지점까지의 

좌측 방향 누적합과 

우측 방향 누적합을 알 수 있고

괄호에 따라서 이 차이가 +- 2가 되는 경우에 

 

해당 지점을 수정했을 때 좌우 괄호의 균형이 맞는 다는 것을 알 수 있다.

일단 이 지점에 대해 구해야 한다.

 

그러나 중요한 건 좌우 갯수가 맞을지 언정

괄호가 올바른가인데

 

 

양쪽으로 누적합을 구하는 중에 누적합이 -1이 되는 경우가 존재한다면, 

그 지점까지 괄호가 잘못됐다 라는 뜻이고, 그 지점에서 괄호를 수정하지 못하는 상황이 존재하면

그건 한번의 괄호 수정으로는 해결이 불가능한 괄호식이라는 것을 알 수 있다.

 

즉 -1이 나오는 지점을 기준으로 이후 영역은 수정이 불가능 하다.

따라서 아래 처럼 그림으로 나타낼 수 있다.

 

(양쪽 배열에 -1이 동시에 겹치는경우는 없다. 서로 계산하는 괄호가 반대일테니

 

양쪽 누적합에 대해

[빈칸] + [빈칸] 혹은 [빈칸] + [-1]인 경우에만 괄호수정이 가능하다.

 

위 경우에 대해서 카운팅하면 정답을 얻을 수 있다.

 

시행착오

문자열를 string으로 받지 않고 char 배열로 받아서 불안정하게 길이를 측정하다 보니

문제를 진작에 풀어놓고서 오답처리로 시간을 낭비했다.

 

)))))(((에 대해서 오답이 나길래 이를 보완하기 위해서 생각을 많이 했는데

입력이 최대 한번의 오타만이 주어지기 때문에 다른 풀이법이 존재하는 것 같다.

역시 코딩문제는 문해력이 중요하다.

 

최적화 해보기

 

누적합은 O(N)이고 양쪽으로 돌려봐야 O(N)이다.

데이터 크기 N에 대해 O(N)보다 빨리 풀 순 없을 것 같다.