[python/백준] 2810. 컵홀더(B1)

📌 문제 탐색하기

👉 문제바로가기
N: 좌석의 수(1 ≤ N ≤ 50)
seat: 좌석의 정보

커플석이 없는 경우를 생각해보면 *S*S*S*S*S*S*S*S*와 같이 좌석이 구성됩니다. 모든 사람들이 본인 좌석의 오른쪽 컵홀더를 사용한다고 가정하면 가장 왼쪽의 컵 홀더가 남게됩니다. 컵 홀더가 남는 경우는 모든 좌석이 일반좌석인 경우이고, 이 때 컵홀더는 N+1개 만큼 있지만 사람이 N명이므로 컵을 컵 홀더에 놓을 수 있는 최대 사람의 수는 N명이 됩니다.

커플석이 1개인 경우를 보면 *S*LL*S*S*S*S*S*와 같이 구성이 되는데 커플석이 하나 생길 때는 일반 좌석과 다르게 L과 L사이에 컵홀더가 없으므로 N+1개에서 커플석의 갯수 1개만큼을 제외해야 합니다.

커플석이 여러개인 경우도 마찬가지로 커플석 사이에 컵홀더가 없는 건 같으니까 결국 커플석의 갯수만큼 제외하면 됩니다.

📌 알고리즘 선택

모든 사람이 순서대로 자신이 꽂을 수 있다면 컵을 꽂는다면 결국 최대한 많은 사람이 컵을 꽂을 수 있습니다. 각 단계의 최적해가 전체 문제의 최적해가 되므로 그리디를 떠올릴 수 있겠네요.

가능한 시간복잡도

좌석의 정보에서 커플석(LL)의 갯수를 확인하기 위해서는 해당 문자열을 처음부터 끝까지 한 번 탐색해야 합니다. 따라서 시간복잡도는 O(N)이고 N의 최댓값은 50이기 때문에 최대 약 50회의 연산이 필요합니다.

📌 코드 설계하기

1. 좌석의 수와 좌석 정보를 Input받습니다.
2. 커플석의 갯수(couple)를 count함수를 활용해 구합니다.
3. 커플석의 갯수에 따라 경우를 나누어 컵을 컵홀더에 놓을 수 있는 최대 사람의 수를 출력합니다.

📌 정답 코드

import sys

N = int(sys.stdin.readline())   #좌석의 수
seat =  sys.stdin.readline()  #좌석 정보

couple = seat.count('LL')

if couple==0:
  print(N)
else:
  print(N+1-couple)

📌 멘토 해설

import sys

# 1. 문제의 input을 받습니다.
N = int(sys.stdin.readline())
str = sys.stdin.readline()

# 2. 좌석에 포함된 LL의 개수와 S의 개수를 구합니다.
cnt_LL = str.count('LL')
cnt_S = str.count('S')

# 3. 컵홀더의 개수를 구합니다.
cups = cnt_S + cnt_LL + 1

# 4. 컵홀더의 개수와 사람의 수를 비교해 로직에 맞게 정답을 출력합니다.
if cups > N:
    print(N)
else:
    print(cups)