[파이썬/Python] 백준 2810번: 컵홀더

📌 문제 : 백준 2810번

---

📌 문제 탐색하기

N : 한 줄에 있는 좌석의 수 (1 ≤ N ≤ 50)
seats : 한 줄의 자리 정보 (S: 일반 좌석 / L: 커플석)

✅ 입력 조건
1. 첫번째 줄 : 좌석의 수 입력
2. 두번째 줄 : 좌석 정보 N개를 입력
3. L은 항상 2개씩 쌍으로 입력
✅ 출력 조건
1. 컵홀더를 쓸 수 있는 최대 사람의 수 출력

(❗️주의: 굳이 이렇게 풀어야 하나 싶은 복잡한 풀이로 작성...)

입력받은 좌석의 정보를 하나씩 S인지 L인지 확인하면서 문제에서 예처럼 컵홀더 위치를 넣어주고 개수를 세면 되겠다고 생각했다.

그래서 리스트의 요소를 읽고 다른 리스트에 컵홀더 정보와 함께 넣어준 후, 컵홀더를 의미하는 *의 개수를 세고 그 개수가 N보다 크면 -1 해주는(S만 있는 경우) 방식으로 구현했다.

가능한 시간복잡도

좌석 정보 입력받아 리스트화 → $O(N)$
while 루프를 통해 좌석 정보 처리 → $O(N)$
for 루프로 컵홀더 개수 계산 → $O(N)$

최종 시간복잡도
$O(N)$으로 제한 시간 내에 연산이 가능하다.

알고리즘 선택

while루프를 활용해 좌석 정보와 컵홀더 정보를 리스트에 추가하고,
for루프로 컵홀더 개수 계산하기.

---

📌 코드 설계하기

1. N 입력
2. 좌석 정보 입력
3. 컵홀더 포함한 좌석 정보 입력할 큐 선언
4. 맨 첫번째 컵홀더 추가
5. 입력받은 좌석 정보를 돌면서 컵홀더 추가
6. 컵홀더 개수 세기
7. L이 없는 경우
8. L이 있는 경우

---

📌 시도 회차 수정 사항

1회차

---

📌 정답 코드

import sys
from collections import deque

input = sys.stdin.readline

# 1. N 입력
N = int(input())

# 2. 좌석 정보 입력
info = list(str(input().rstrip()))

# 3. 컵홀더 포함한 좌석 정보 입력할 큐 선언
seats = deque()

# 4. 맨 첫번째 컵홀더 추가
seats.append('*')

# 5. 입력받은 좌석 정보를 돌면서 컵홀더 추가
while info:
    seat = info.pop()

    if seat == 'S':
        seats.append(seat)
        seats.append('*')
    elif seat == 'L':
        info.pop()
        seats.append('LL')
        seats.append('*')

# 6. 컵홀더 개수 세기
count = 0

for s in seats:
    if s == '*':
        count += 1

# 7. L이 없는 경우
if count > N:
    print(count - 1)
# 8. L이 있는 경우
else:
    print(count)

• 결과
  

다른 풀이

import sys

N = int(input())

info = input().rstrip()

count = info.count('LL')

if count <= 1 :
	print(N)
else:
	print(N - count + 1)

• 결과
  
• 연산량이 줄어 더 빠른 시간의 연산이 가능했다.
  
  

---

📌 회고

• 문제 속에서 규칙을 찾았다면 풀이의 길이가 이렇게 길지 않았을 것이다. S, L을 찾는 문제라고만 생각해서 단순히 하나하나 비교하고 계산하는 식으로 풀려고 했다.
• LL인 경우가 컵홀더 개수에 영향을 주기 때문에 이부분을 고려해서 규칙을 찾았다면 아래와 같은 더 간단한 코드를 얻을 수 있었을 것이다.
• 문자열.count(): ()안의 문자가 문자열 내에 몇 개인지 계산