[백준(BOJ)] 19948 음유시인 영재 C++

문제

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

19948번: 음유시인 영재

 

계획 세우기

// 예제 입력1
There is no cow level
5
1 0 2 0 4 3 0 1 2 0 0 3 0 2 2 0 4 1 1 2 0 1 1 0 0 0

// 예제 출력1
TINCL

// a b c d e f g h i j k l m n o p q r s t u v w x y z
// 1 0 2 0 4 3 0 1 2 0 0 3 0 2 2 0 4 1 1 2 0 1 1 0 0 0 사용 가능 횟수
// 0 0 1 0 4 0 0 1 1 0 0 2 0 1 2 0 0 1 1 1 0 1 1 0 0 0 실제 사용 횟수(내용만)
// 0 0 2 0 4 0 0 1 2 0 0 3 0 2 2 0 0 1 1 2 0 1 1 0 0 0 실제 사용 횟수(내용+제목)

"There is no cow level" 이라는 예제 문장에 사용된 영어의 갯수는 위와 같다.

 

string을 입력받아서 규칙에 맞게(aaaaaa는 a로 취급) 사용한 알파벳, 공백이 몇 개인지 체크한다.

stringstream을 이용해서 공백을 기준으로 나누고, 첫 글자를 string에 더해서 title을 만들어준다.

title의 알파벳 사용 갯수도 체크한다.

 

풀이(실패)

#include <iostream>
#include <sstream>
#include <string>

using namespace std;


int used_Alphabet[26] ={0, };
int used_Spacebar = 0;

void CheckString(string s){
    bool isSame = false;
    for(int i=0; i<s.length();i++){
        if(i>0 && s[i-1]==s[i]) isSame=true;
        else isSame =false;

        if(isSame) continue;
        //A=65 a=97
        if (s[i]==' ') used_Spacebar+=1;
        if(s[i]>=97) used_Alphabet[s[i]-97]+=1;
        else used_Alphabet[s[i]-65]+=1;
    }
}
// 시에 나오는 단어들의 첫 글자를 대문자로 바꾼 뒤 순서대로 이어서 제목으로 만든다. 만약 시의 내용이 'There is no cow level' 이라면 시의 제목은 'TINCL'이 된다.
    // 키보드를 쓸 때 같은 문자가 연속으로 나오거나 빈칸이 연속으로 나오는 경우 영재는 자판을 꾹 눌러 한 번만 사용해서 키보드를 좀 더 효율적으로 쓸 수 있다.
    // (A와 a는 다른 문자이므로 'Aa'는 2번의 a자판을 누른 것으로 한다.)
int main(){
    // input
    // 첫 줄에 시의 내용이 주어진다.
    string contents;
    cin >> contents;
    // 둘째 줄에는 스페이스 바의 남은 사용 가능 횟수 주어진다.
    int available_spacebar;
    cin >> available_spacebar;
    // 셋째 줄에는 대소문자를 구별하지 않고, 26개의 알파벳에 대한 영자판의 남은 사용 가능 횟수가 알파벳순으로 주어진다.
    int available_Alphabet[26];
    for (int i=0;i<26;i++){
        cin >> available_Alphabet[i];
    }

    // 사용된 횟수(내용) 체크
    CheckString(contents);
    
    // 사용된 횟수(제목) 체크
    stringstream ss(contents);
    string title ="";
    string word;
    while(getline(ss, word, ' ')){
        title =title+word[0];
    }
    transform(title.begin(), title.end(), title.begin(), ::toupper);

    CheckString(title);
    // 정답 출력
    string answer="";
    if (available_spacebar<used_Spacebar) {
        cout << "-1";
        return 0;
    }
    for (int i=0;i<26;i++){
        if(answer == "-1") {
            cout << "-1";
            return 0;
        }
        if(available_Alphabet[i]<used_Alphabet[i]) answer ="-1";
    }
    answer=title;
    cout << answer;
    return 0;
}

 

1 0 2 0 4 3 0 1 2 0 0 3 0 2 2 0 4 1 1 2 0 1 1 0 0 0 // available_Alphabet
0 0 2 0 4 0 0 1 2 0 0 3 0 2 2 0 0 1 1 2 0 1 1 0 0 0 // 정답
0 0 0 0 2 0 0 1 0 0 0 0 0 0 0 0 0 1 0 2 0 0 0 0 0 0 // used_Alphabet

 

used_Alphabet을 출력하니 위와 같은 결과가 나왔다. 정답보다 적게 나오거나 표시가 되지 않은 것도 있다.

 

a b c d e f g h i j k l m n o p q r s t u v w x y z
0 0 0 0 2 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 //contents
0 0 0 0 2 0 0 1 0 0 0 0 0 0 0 0 0 1 0 2 0 0 0 0 0 0 //+title

title을 더하기 전과 후의 used_Alphabet을 출력한 결과이다. 마찬가지로 정상적으로 작동하지 않는다...

 

 

함수에 들어가는 string s를 출력하니 공백이 생기는 순간 입력이 끝나서 저런 일이 생기는 거였다. 공백을 포함한 입력을 받을 수 있는 방법을 사용해야 한다. getline(cin, string);을 이용하여 입력 부분을 수정해주었다.

 

 

2차 풀이

처음 코드를 수정할 엄두가 안 나서 처음부터 다시 짰다. used_space/alphabet을 만드는 것보다 기존의 available에서 빼다가 0이하가 나오면 -1을 출력하도록 만드는 게 더 나아보였다.

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
using namespace std;

int alphabet[26];
int space;
string poem;

void Check(string s)
{
    for (int i = 0; i < s.length(); i++)
    {
        // 이전 문자와 같은 경우(aaaaaa) count하지 않고 넘어가야 함
        if (i > 0 && (s[i - 1] == s[i])) continue;

        // A=65 a=97
        int idx = s[i];
        if (idx >= 97) idx -= 97;
        else idx -= 65;
        // alphabet[] 범위를 넘어가면 체크x
        if (idx < 0 || idx >= 26) continue;

        alphabet[idx] -= 1;
    }
}

string GetTitle(string s)
{
    string title = "";
    stringstream ss(s);
    string word;
    // 공백 기준 구분 + 첫 글자를 title에 더함
    while (getline(ss, word, ' '))
    {
        title = title + word[0];
    }

    // 대문자로 바꾸기
    transform(title.begin(), title.end(), title.begin(), ::toupper);
    return title;
}

int main()
{
    // input
    getline(cin, poem);
    cin >> space;
    for (int i = 0; i < 26; i++)
    {
        cin >> alphabet[i];
    }

    Check(poem);
    string title = GetTitle(poem);
    Check(title);

    // 시의 내용과 제목을 모두 기록할 수 있다면 시의 제목을 출력하여라.
    // There is no cow level의 제목은 TINCL(5) 사용된 스페이스바는 4
    if (space < title.length() - 1)
        cout << "-1";
    else
    {
        bool isAnswer = true;
        // alphabet 하나라도 0보다 작아지면 안 됨
        for (int i = 0; i < 26; i++)
        {
            if (alphabet[i] < 0)
                isAnswer = false;
        }
        if (isAnswer)
            cout << title;
        else
            cout << "-1";
    }

    return 0;
}