백준: Class 3 ② - 2667, 5430, 5525

</br> 클래스 3 계속 계속
</br>

2667: 단지번호붙이기

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

void func(int x, int y){
    d++;
    visited[x][y] = d;
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if( visited[nx][ny] == 0 && mmap[nx][ny] == 1 ){
            func(nx, ny);
        }
    }
}

// in main()
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if( visited[i][j] == 0 && mmap[i][j] == 1 ){
                d = 0;
                func(i, j);
                v.push_back(d);
            }
        }
    }
    sort(v.begin(), v.end());
    cout << v.size() << '\n';
    for(int i = 0; i < v.size(); i++){
        cout << v[i] << '\n';
    }

자꾸 왜 틀리지 했는데 마지막 출력에 소팅을 안 해서 그랬다ㅜ
dfs로 방문하지 않았는데 1이면 쭉 들어가서 탐색하고, 그 깊이를 벡터에 저장한다.
벡터의 사이즈가 곧 총 단지 수이고, 각 단지마다 집의 수를 출력한다.
</br>

5430: AC

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

    while( t-- ){
        string s;
        cin >> s;
        int n;
        cin >> n;
        string a;
        cin >> a;

        deque<int> dq;
        for(int i = 1; i < a.size()-1; i++){
            if( a[i] == ',' ) continue;
            int k = a[i++]-'0';
            while( a[i] != ',' && i < a.size()-1 ){
                k *= 10;
                k += a[i++]-'0';
            }
            dq.push_back(k);
        }

        bool error = false;
        bool rev = false;
        for(int i = 0; i < s.size(); i++){
            if( s[i] == 'R' ){
                rev = !rev;
            }
            else if ( s[i] == 'D' ){
                if( dq.size() ){
                    if( rev ) dq.pop_back();
                    else dq.pop_front();
                }
                else error = true;
            }
        }

        if( error ) cout << "error\n";
        else if( dq.size() == 0 ) cout << "[]\n";
        else{
            cout << '[';
            if( rev ){
                while( dq.size() > 1 ){
                    cout << dq.back() << ",";
                    dq.pop_back();
                }
            }
            else{
                while( dq.size() > 1 ){
                    cout << dq.front() << ",";
                    dq.pop_front();
                }
            }
            cout << dq.front() << "]\n";

        }
    }

문자열로 들어오는 배열 파싱, 명령어 처리, 출력으로 나뉘겠다
명령어 처리할 때 뒤집으라고 진짜 뒤집었더니 시간 초과 난다…
deque로 지금 뒤집은 상태인지 아닌지만 체크해서 pop해주자
</br>

5525: IOIOI

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

방법 1.

    string IOI = "";
    for(int i = 0; i < n; i++){
        IOI.append(1, 'I');
        IOI.append(1, 'O');
    }
    IOI.append(1, 'I');

    string s;
    cin >> s;

    int cnt = 0;
    for(int i = 0; i <= s.size()-IOI.size(); i++){
        if( s[i] == 'O' ) continue;
        int j = 0;
        for( ; j < IOI.size(); j++){
            if( s[i+j] != IOI[j] ) break;
        }
        if( j == IOI.size() ) cnt++;
    }

    cout << cnt << endl;

처음에 IOI 문자열을 만들어서 맞대 보는 식으로 했는데, 50점 받았다.
</br>

방법 2.

    int cnt = 0;
    for(int i = 0; i < s.size()-1; i++){
        if( s[i] == 'O' ) continue;
        int c = 0;
        while( i+1 < s.size() ){
            if( s[i] == s[i+1] ){
                if( s[i] == 'O' ){
                    c--;
                }
                else{
                    c++;
                }
                break;
            }
            c++;
            i++;
        }
        if( c/2 - n + 1 > 0 ) cnt += c/2 - n + 1;
    }
    cout << cnt << endl;

m <= 1000000 이므로 이중 포문을 돌면 시간 초과가 나는 거였다!
위 코드 제출하면서 쓸데없는 계산 중복으로 한다 싶기는 했는데…

ex) IOIOIOIOI	4(4+1개의 I, 4개의 O)
1:  IOI
      IOI
        IOI
          IOI   4

2:  IOIOI
      IOIOI
        IOIOI	3

3:   IOIOIOI
      IOIOIOI	2

4:   IOIOIOIOI	1

그래서 생각해 보니, IOIOI…를 찾을 수 있을 만큼 길게 찾고 넘기면 되겠더라.
위처럼, 문자열에서 찾은 IOIOI…의 길이가 4라면, n이 1이면 4번, 2면 3번, 이런 식으로 (4-n+1)개 찾을 수 있다.

ex) n = 1,
OOIOIOIOIIOII(백준 예제 1)

  IOIOIOI     > (3-1+1) = 3개
         IOI  > (1-1+1) = 1개
총 4개

</br>

---

클래스 문제 풀이가 더 재밌는 것 같다
문제 난이도도 섞여 있고
</br>