S14713 앵무새

문제 이해

• 1~4번 조건 ⇒ 단어들을 순서대로 말한다. queue를 이용해야함을 알 수 있음.
• 문장단위, 단어단위로 잘라 입력받을 수 있도록!!
• 문장 L의 단어가 Si의 front들중에 존재하는지 검사! → 완성가능 여부에 따라 결과 출력

시간/공간 복잡도

• 입력 크기문장 → 100개의 단어, 32개 이하의 소문자 (string → char 배열, 개당 1byte)
• 받아 적은 문장 L , 최대 10,000개의 단어, 32개 이하의 소문자
• 앵무새의 수 N 100
• 시간 제한 1초→ 최대 10^6
• L의 10,000개의 단어를 100개의 queue의 front에서 검사
• 메모리 제한 512MB ⇒ 보통 100MB이상이면 여유로움.받아 적은 문장 L , 최대 10,000개의 단어, 32개 이하의 소문자 * 2
• 640,000 byte < 1MB = 1048576 byte (대략 10^6)
• string 변수 사용 공간
  (string → char 배열, 개당 1byte)

정답 코드

#include <iostream>
#include <queue>
#include <sstream>
using namespace std;

int N;
string s;
queue<string>q[105];  // 배열대신 벡터 이용 가능.
bool res = true;

int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin >> N;
    cin.ignore();
    for (int i = 0; i < N+1; ++i) {  // q[N]이 ans
        getline(cin,s);
        istringstream iss(s);
        string str_buf;
        while(getline(iss, str_buf, ' '))
        {
            q[i].push(str_buf);
        }
    }

    while(!q[N].empty()) {
        bool check = false;
        for (int i = 0; i < N; ++i) {
            if(!q[i].empty()) {  // empty의 경우에는 front에 접근 불가능
                if (q[i].front() == q[N].front()) {
                    q[i].pop();
                    q[N].pop();
                    check = true;
                }
            }
        }

        if (!check) {
            res = false;
            break;
        }
    }

    for (int i = 0; i < N; i++) {
        if(!q[i].empty())
        {
            res = false;
            break;
        }
    }

    res ? cout << "Possible" : cout << "Impossible";
    return 0;
}

---

주의점

런타임 에러

접근할 수 없는 부분에 대한 예외처리 필요!

ex)

q[3].front() 에 접근하는데

q[3]이 존재하지 않거나 q[3]이 empty 인 경우!

 if(!q[i].empty()) // 예외처리!!

틀렸습니다!

예외 케이스

문장 L이 완성되었는데 앵무새가 단어를 더 말하는 경우 (queue가 empty가 아닌 경우)

 for (int i = 0; i < N; i++) {
        if(!q[i].empty())
        {
            res = false;
            break;
        }
    }

앵무새의 말을 담았던 queue가 모두 비워져있는지 확인!

---

관련 정보

C++ String 입력받기

    #include <sstream>

        string s;

    cin.ignore(); // 이전에 입력을 받은 경우 버퍼를 지워주어야함! getline을 이용해서도 가능

    for (int i = 0; i < N+1; ++i) {  
        getline(cin,s); // 기본 delimiter(구분자) \n으로 입력받음.
        istringstream iss(s); // inputstreamstring 타입 변수 iss에 s를 대입 
        string str_buf;  // 단어들을 임시로 저장하기 위한 string
        while(getline(iss, str_buf, ' '))  // 공백을 구분자로 하여 단어 잘라받기
        {
            q[i].push(str_buf);
        }

getline은 기본적으로 istream을 반환. 그 외 상황에서는 flag를 반환.

flag가 return되는 경우 while문이 종료됨.

벡터의 초기화 방법

vector<int> v;                       // int타입 벡터 생성
vector<int> v = { 1, 2, 3};          // int형 백터 생성 후 1, 2, 3 으로 초기화
vector<int> v[10];                   // int타입 벡터 배열(크기 : 10) 생성
vector<int> v[] = {{ 1, 2}, {3, 4}}; // int형 백터 배열 생성(행은 가변이지만 열은 고정)
vector<vector<int>> v;               // 2차원 백터 생성(행과 열 모두 가변)
vector<int> v(5);                    // 5개의 원소를 0으로 초기화
vector<int> v(5, 3);                 // 5개의 원소를 3으로 초기화
vector<int> v2(v);                   // 벡터 v를 복사하여 벡터v2 생성