파이썬 Python | 알고리즘 | 백준 컵홀더

⭕ 파이썬 Python | 알고리즘 | 백준 컵홀더

➡️ 문제링크

• https://www.acmicpc.net/problem/2810

 

➡️ 문제 탐색하기

• 극장의 한 줄에 있는 좌석의 정보가 주어졌을 때, 모든 사람이 컵홀더를 사용할 수 있는 최대 사람의 수를 구하는 문제이다.
  1. 일반석(S)의 경우, 각 좌석마다 컵홀더가 하나씩 배치되는 것이 당연하다. 이를 바탕으로 초기 계산은 각 좌석 수 + 1로 설정하였다.
  2. 커플석(L)은 두 개씩 쌍으로 주어지므로, 하나의 커플석 쌍당 하나의 컵홀더가 필요하다. 따라서 커플석 두 개당 하나의 컵홀더만 필요하다는 점을 고려하여 컵홀더 수를 줄였다. 커플석 두 개당 하나의 컵홀더가 필요하다는 점에서 커플석의 수를 2로 나누는 것이 합리적이다.
• 좌석의 수 N과 계산된 컵홀더 수 중 작은 값을 출력한다. 실제 좌석 수보다 컵홀더의 수가 많을 수 있지만, 이는 불필요한 컵홀더 수가 된다. 실제로는 좌석 수와 컵홀더 수 중 작은 값을 선택해야 모든 사람이 컵홀더를 사용할 수 있는 최대 인원이 된다.
• 시간 복잡도는 O(N)이다. 좌석의 정보 길이 N에 대해 각 좌석을 한 번씩 검사하고, 'S'와 'L'의 개수를 세기 때문이다. N의 최대값이 50이므로, 시간 복잡도는 1초 이내 매우 충분하다.

 

➡️ 코드 설계하기

1. 사람의 인원수와 좌석의 정보를 입력받는다.
2. 기본적으로 사람의 인원수에 +1을 더해 총 컵홀더의 개수를 계산한다.
3. 커플석의 수를 세어 그 수를 2로 나눈 값을 총 컵홀더 수에서 뺀다.
4. 좌석의 수 N과 계산된 컵홀더 수 중 작은 값을 출력한다.

 

➡️ 시도 회차 수정 사항 (Optional)

1회차

• strip과 split을 잘못 사용하여 리스트를 올바르게 만들지 못하였다. split() 메서드는 기본적으로 공백을 기준으로 문자열을 나누기 때문에, 좌석 정보가 공백 없이 이어진 문자열로 주어졌을 때, split()을 사용하면 하나의 요소로 이루어진 리스트가 생성된다. 입력 예시가 SSS인 경우, 위 코드는 ['SSS']와 같이 리스트를 하나의 요소로 만들어버린다. 원하는 형태인 ['S', 'S', 'S']와 다르다. 따라서, split()을 사용할 필요가 없고, strip()만 사용하여 문자열의 앞뒤 공백을 제거한 후, 리스트로 저장해야 한다.

import sys

N = int(sys.stdin.readline())
seats = list(sys.stdin.readline().strip().split())
count = len(seats)
count += 1

if seats.count('L') > 0:
    count -= seats.count('L') // 2  

print(count)

---

2회차

• count 값이 총 사람의 수보다 클 경우, 모든 사람이 컵홀더를 사용할 수 있는 최대 인원을 제대로 구하지 못하였다.

import sys

N = int(sys.stdin.readline())
seats = list(sys.stdin.readline().strip())
count = len(seats)
count += 1

if seats.count('L') > 0:
    count -= seats.count('L') // 2

print(count)

---

3회차

• 시간 88ms
• min 함수를 사용하여 총 사람의 수와 계산된 컵홀더 수 중 작은 값을 출력함으로써, 최종적으로 모든 사람이 컵홀더를 사용할 수 있는 최대 인원을 구할 수 있었다.

import sys

N = int(sys.stdin.readline())
seats = list(sys.stdin.readline().strip())
count = len(seats)
count += 1

if seats.count('L') > 0:
    count -= seats.count('L') // 2

print(min(N, count))

 

➡️ 정답 코드

import sys

N = int(sys.stdin.readline())
seats = list(sys.stdin.readline().strip())
count = len(seats)
count += 1

if seats.count('L') > 0:
    count -= seats.count('L') // 2

print(min(N, count))