Informatica Online Judge

  OX 스템프 [2329 / 0919]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 46   Total Tried : 35


The Champion of this Problem (C++) : gs18031 - ms / 127byte
My Best Submission (C++) : N/A

[JOI2019예선]

Background

경곽이는 "O" 스템프, "X" 스템프, "OX" 스템프의 3가지 스템프를 각각 0개 이상 가지고 있다. 이들은 각각 종이에 해당 모양을 찍을 수 있다.

"O"스템프를 사용하면 "O"가 1개 찍히고, "X" 스템프를 사용하면 "X"가 1개 찍힌다.

그리고 "OX"스템프를 사용하면 "O"와 "X" 순서대로 하나씩 찍힌다. 하지만 이 스템프를 거꾸로 찍으면 "X"와 "O"가 순서대로 하나씩 찍힌다.

경곽이는 가지고 있는 스템프를 각각 정확히 1번씩 적당한 순서대로 사용한다. 그 결과 한 줄로 "O"와 "X"로 구성된 길이가 N인 문자열 S를 얻을 수 있다.

문자열 S의 i번째 문자를 S_i라고 한다.

경곽이가 가지고 있는 각각의 스템프의 개수는 모르지만 경곽이가 찍은 문자열 S를 알고 있다. 찍혀 있는 문자열로 부터 경곽이가 가지고 있는 "OX" 스템프의 개수로 유추할 수 있는 최댓값을 구하는 프로그램을 작성하시오.

Input

입력은 다음과 같은 형식으로 구성된다.

N
S

1 ≦ N ≦ 100000 (= 10^5)
S 는 길이가 N인 문자열이다.
S 의 각 문자는 "O", "X"로만 구성된다.

Output

경곽이가 가지고 있는 것으로 유추되는 "OX"스템프의 최댓값을 출력한다.

IO Example

입력1
5
OXXOX

출력1
2

경곽이가 찍은 문자열은 왼쪽으로부터 O, X, X, O, X이다.
경곽이는 "O"스템프, "X"스템프, "OX"스템프를 각각 0, 1, 2가지고 있다고 생각하면 다음과 같은 순서로 S를 만들 수 있다.

첫 번째 "OX"스템프를 쓰고, 다음으로 "X"스템프, 마지막으로 다시 " OX"스템프를 쓰면 문자열 S를 얻을 수 있다.

이 때 사용한 "OX" 스템프는 2개이고 이보다 더 많은 "OX"스템프를 가질 수는 없다. 따라서 답은 2이다.

입력2
14
OXOXOXOXXOXOXO

출력2
7

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]