[2810번] 컵홀더

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 구현

이 문제를 두가지 방법으로 설명하고자 한다.

우선 첫번째로 문자열까지 구현하는 방법이다.

아래에 코드를 수록해두었는데, 이 방법의 특징은 결국 문자열을 모두 만들고 

*을 몇개 찍었는지 확인해주면 되는 문제이다.

이때 아래 str[i] == 'L' -> chk = false라는 구문이있는데 

좌석이 SSS같은 경우는 컵홀더가 3개만 있으면 된다. 이때 가장 오른쪽에는 없어도 된다는 의미이고

L이 한번이라도 있는 경우는 SLL인 경우 *S*LL* 즉, 컵홀더가 가장 오른쪽에 필요하다는 의미가 된다.

두번째 방법은 문자열을 구현하지 않고 위의 내용을 압축하여 그대로 구현하는 방법이다.

속도면에서는 후자가 좋지만, 알고리즘을 확인하는 측면에서는 전자 방식이 더 좋아 보인다.(시간 복잡도가 그리 크지 않기 때문)

소스 코드 : 

(문자열까지 모두 구현)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

#include <iostream> #include <cstdio> #include <string>   using namespace std;   int main() {     int n;     cin >> n;       string str;     cin >> str;       int star = 0;     int len = str.size();     for (int i = 0; i < len; i++)     {         if (str[i] == 'S')         {             str.insert(str.begin() + i, '*');             i++;             len++;             star++;         }         else if (str[i] == 'L')         {             str.insert(str.begin() + i, '*');             i += 2;             len++;             star++;         }     }     str.push_back('*');     star++;          bool chk = true;     for (int i = 0; i < len; i++)     {         if (str[i] == 'L')         {             chk = false;             break;         }     }     if (chk)         cout << star - 1;     else         cout << star;     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

(문자열 구현 X)

#include <iostream>
#include <cstdio>
#include <string>
 
using namespace std;
 
int main()
{
    int n;
    cin >> n;
 
    string str;
    cin >> str;
 
    bool chk = true;
    int star = 0;
    int len = str.size();
    for (int i = 0; i < len; i++)
    {
        if (str[i] == 'S')
            star++;
        
        else if (str[i] == 'L')
        {
            i ++;
            star++;
            chk = false;
        }
    }
    star++;
    
    if (chk)
        cout << star - 1;
    else
        cout << star;
    
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>