백준 26122 - 가장 긴 막대 자석

문제

문제 링크

문자열 s가 주어지며 S는 오직 문자 ‘N’과 ‘S’로만 구성되어 있다.
이 문자열에서 막대 자석 문자열이 될 수 있는 조건은 다음과 같다.

• N과 S의 개수가 같다.
• 문자열의 앞쪽 절반을 구성하는 문자는 모두 N이거나 모두 S이다.
• 연속된 문자열이다.

이 문자열의 부분 문자열 중에서 찾을 수 있는 가장 긴 막대 자석 문자열의 길이를 구하여라.

풀이

문자열에서 연결된 N과 S의 개수를 각각 세어 배열에 저장한다.
그 후 인접한 N과 S의 개수 값을 이용하여 만들 수 있는 막대 자석 문자열의 길이를 구한다.

N과 S의 개수가 다르면 그 중 더 작은 값을 두 배한 것이 그 결과이고
N과 S의 값이 같다면 그 수에 두 배한 것이 결과이다.

예를 들어 문자열 S가 “NSSSNNSN” 일 경우 연속된 N과 S의 개수를 세면 다음과 같다.

“1 3 2 1 1”

1, 3 -> 1 * 2 = 2
3, 2 -> 2 * 2 = 4
2, 1 -> 1 * 2 = 2
1, 1 -> 1 * 2 = 2

따라서 문자열 “NSSSNNSN” 의 부분 문자열 중 가장 큰 막대 자석 문자열의 길이는 4 이다.

코드

내 제출

시간 복잡도

문자열을 한 번 순회하여 구간을 나눈다.
구간 벡터를 한 번만 순회하여 최댓값을 구한다.
중첨 반복문이 없고 모든 연산은 상수 시간이기 때문에
시간복잡도는 O(N)

후기

반복문 하나로 어떻게든 해결하고 싶었다.
그 생각에 사로잡혀서 그리 깔끔하지 않은 방법으로 풀이를 하려다 보니 풀이가 계속 꼬였었다.
풀이가 금방 떠오르지 않는다면 당장에 떠오르는 풀이 말고 다른 풀이 방법도 생각해보는 것이 좋을 것 같다.