문제
십년이면 강산이 변한다.
강산이네 동네에 드디어 극장이 생겼고, 강산이는 극장에 놀러갔다. 매점에서 콜라를 산 뒤, 자리에 앉은 강산이는 큰 혼란에 빠졌다. 양쪽 컵홀더를 이미 옆 사람들이 차지했기 때문에 콜라를 꽂을 컵 홀더가 없었기 때문이다. 영화를 보는 내내 콜라를 손에 들고 있던 강산이는 극장에 다시 왔을 때는 꼭 콜라를 컵 홀더에 놓겠다는 다짐을 한 후 집에 돌아갔다.
극장의 한 줄에는 자리가 N개가 있다. 서로 인접한 좌석 사이에는 컵홀더가 하나씩 있고, 양 끝 좌석에는 컵홀더가 하나씩 더 있다. 또, 이 극장에는 커플석이 있다. 커플석 사이에는 컵홀더가 없다.
극장의 한 줄의 정보가 주어진다. 이때, 이 줄에 사람들이 모두 앉았을 때, 컵홀더에 컵을 꽂을 수 있는 최대 사람의 수를 구하는 프로그램을 작성하시오. 모든 사람은 컵을 한 개만 들고 있고, 자신의 좌석의 양 옆에 있는 컵홀더에만 컵을 꽂을 수 있다.
S는 일반 좌석, L은 커플석을 의미하며, L은 항상 두개씩 쌍으로 주어진다.
어떤 좌석의 배치가 SLLLLSSLL일때, 컵홀더를 *로 표시하면 아래와 같다.
SLLLLSSLL*
위의 예에서 적어도 두 명은 컵홀더를 사용할 수 없다.
입력
첫째 줄에 좌석의 수 N이 주어진다. (1 ≤ N ≤ 50) 둘째 줄에는 좌석의 정보가 주어진다.
출력
컵을 컵홀더에 놓을 수 있는 최대 사람의 수를 출력한다.
예제 입력 1
3
SSS예제 출력 1
3예제 입력 2
4
SLLS예제 출력 2
4예제 입력 3
9
SLLLLSSLL예제 출력 3
7문제접근
여러 경우의 수를 생각하다 보니, 커플석 (LL)의 수에 따라 출력이 변하는 걸 확인할 수 있다.
커플석 (LL)이 2자리 이상일 때, 커플석이 한 자리 많아질수록 한 명이 컵홀더를 사용할 수 없습니다.
먼저 N과 member를 입력 받습니다. 그리고 member에서 커플석(LL)이 몇 개인지 count해줍니다.
만약 LL이 1개 또는 0개라면 사람의 수를 그대로 출력합니다. (모두 컵홀더 사용 가능)
만약 LL이 2개 이상이라면 count를 빼주고 1을 더해줍니다. (LL이 2개면 -1, LL이 3개면 -2 이므로)
정답코
N = int(input())
member = input()
count = member.count('LL')
if (count <= 1):
print(len(member))
else:
print(len(member) - count + 1)시간복잡도
이 코드의 시간 복잡도는 문자열의 길이에 선형적으로 비례할 것이다.
따라서 시간 복잡도는 O(N) 여기서 N은 문자열 member의 길이
코드는 주어진 문자열에서 'LL'의 등장 횟수를 세고, 이를 기반으로 최종 결과를 계산한다.
이러한 연산들은 문자열을 한 번 훑는 것으로 이루어져 있으므로 전체적인 시간 복잡도는 입력 문자열의 길이에 선형적으로 비례한다.
