[코테 챌린지] 10일차. 컵홀더

십년이면 강산이 변한다. 강산이네 동네에 드디어 극장이 생겼고, 강산이는 극장에 놀러갔다.
매점에서 콜라를 산 뒤, 자리에 앉은 강산이는 큰 혼란에 빠졌다. 양쪽 컵홀더를 이미 옆 사람들이 차지했기 때문에 콜라를 꽂을 컵 홀더가 없었기 때문이다. 영화를 보는 내내 콜라를 손에 들고 있던 강산이는 극장에 다시 왔을 때는 꼭 콜라를 컵 홀더에 놓겠다는 다짐을 한 후 집에 돌아갔다.
극장의 한 줄에는 자리가 N개가 있다. 서로 인접한 좌석 사이에는 컵홀더가 하나씩 있고, 양 끝 좌석에는 컵홀더가 하나씩 더 있다. 또, 이 극장에는 커플석이 있다. 커플석 사이에는 컵홀더가 없다.극장의 한 줄의 정보가 주어진다. 이때, 이 줄에 사람들이 모두 앉았을 때, 컵홀더에 컵을 꽂을 수 있는 최대 사람의 수를 구하는 프로그램을 작성하시오.
모든 사람은 컵을 한 개만 들고 있고, 자신의 좌석의 양 옆에 있는 컵홀더에만 컵을 꽂을 수 있다. S는 일반 좌석, L은 커플석을 의미하며, L은 항상 두개씩 쌍으로 주어진다.

- 첫째 줄에 좌석의 수 N이 주어진다. (1 ≤ N ≤ 50) 둘째 줄에는 좌석의 정보가 주어진다.
-컵을 컵홀더에 놓을 수 있는 최대 사람의 수를 출력한다.

---

📌 문제 탐색하기 

우리가 문제를 이해해가는 과정을 작성하시면 됩니다.
- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정 등을 작성해주시면 됩니다.

알고리즘 선택

• 각 사람이최대한 많은 컵홀더를 사용할 수 있도록 해야하고, 각 사람의 선택이 이후 사람의 선택에 영향을 미치지 않는다. -> 문제의 최적해가 부분 문제의 최적해로 구성되는 그리드알고리즘의 최적 부분 구조 특징을 가질 수 있다. 
• 커플석 "LL" 의 문자열 개수만 세면되기 때문에 문자열을 순회하는 데 걸리는 시간 O(N)이 걸린다. 그리드 알고리즘으로 충분히 간단하게 구현할 수 있다고 판단했다. 

Greedy Algorithm 특성

• 최적 부분 구조 : 문제의 최적해가 부분 문제의 최적해로 구성될 때
• 탐욕적 선택 속성 : 전체 문제를 해결하기 위해 가장 좋아보이는 선택을 반복하면서 최적해를 보장할 때

---

📌코드 설계하기 

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡으셨을 것 같습니다.
이제 문제 풀이를 본격적으로 하기 전, 이 문제를 풀기 위한 로드맵을 그려보겠습니다.
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성해주시면 됩니다.
처음에는 어려울 수 있지만, 문제를 풀기 전 미리 지도를 그린다라는 생각으로 적어나가 보시면 좋을 것 같습니다 :)

• 인원 수와 좌석배치 입력 받기
• 커플석("LL") 개수 세기
• 컵홀더 계산
  - 모든 사람들은 컵홀더 하나씩은 사용할 수 있기 때문에 사람수(N)보다 하나씩 더 많다. 
  - 커플석("LL")이 있다면, 커플석 개수만큼 컵홀더가 줄어든다. 
• 사용할 수 있는 컵홀더의 개수가 인원 수보다 크다면, 모든 인원이 사용할 수 있다는 예외처리가 필요하다. 

---

📌 시도 회차 수정 사항 (Optional)

- 무문별하게 “맞았습니다”가 나올때 까지 수정하는 형태의 문제 풀이를 반복하면 , 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 됩니다.
- 틀렸습니다를 받았다면 왜 틀렸는지 고민해보고 , 어떻게 수정할 수 있는지 고민하는 과정을 작성해주시면 됩니다.
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검해보세요
- 한번에 맞출수도 있기 때문에 이 칸은 Optional입니다.

 

x

---

📌정답 코드

# 1. 인원 수와 좌석배치 입력 받기
person_cnt = int(input())
seat = input()

# 2. 커플석("LL")개수 세기
couple_seat = seat.count("LL")

# 3. 컵홀더 계산 
# 모든 사람들은 컵홀더 하나씩은 사용할 수 있기 때문에 사람수(N)보다 하나씩 더 많다. 
# 커플석("LL")이 있다면, 커플석 개수만큼 컵홀더가 줄어든다. 
result = person_cnt + 1 - couple_seat

# 4. 사용할 수 있는 컵홀더의 개수가 인원수보다 크다면, 모든 인원이 사용할 수 있다. 
if person_cnt < result:
    result = person_cnt

print(result)