알고리즘/백준

백준 1316 그룹 단어 체커 c++ [컴공과고씨]

시간빌게이츠 2022. 4. 5. 21:23
반응형

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

 

1316번: 그룹 단어 체커

그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때

www.acmicpc.net

떠올린 방법은 정렬하지 않고 일단 unique 함수를 사용해서 연속되는 수를 제거한다.

(unique, erase를 잘 모른다면 https://hagisilecoding.tistory.com/53 여기서 공부하고 오면 편함)

aabbbccb가있다면 unique함수를 정렬을 하고 써주면 연속되는 값이 쓰레기 값으로 가고 이것을 erase를 통해 지워주면 abcb가된다. 그 후 이것을 sort해주면 abbc이렇게되는데 사실 그룹이 이루어져있으면 sort를 했을 때 중복이 일어날 수 없다. 왜냐하면 그룹이 이루어져있으면 중복되는 값은 없어져야하기 때문이다. 그래서 unique erase sort를 사용한 후 문자열을 확인하면서 중복되는 값이 있다면 그룹에서 제외시키면 된다.

 

단계별풀이

1.string 선언

2. 입력 받은 문자열을 unique를 통해 연속된 중복값을 뒤로 보내주고 erase로 쓰레기값 제거

3. sort를 이용해서 문자열 정렬

4. 정렬된 문자열을 한개씩 확인하는데 다음 문자열과 같으면 false

5. true이면 그룹이고 false이면 그룹제외

 

전체코드

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
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
    int n;
    cin >> n;
    string word;
    int ans = 0;
    for (int i = 0; i < n; i++){
        bool isgroup = true// 그룹인지 확인하는 변수
        cin >> word;
        word.erase(unique(word.begin(), word.end()), word.end());
        //연속된 중복값 맨 뒤로 보내서 제거
 
        sort(word.begin(), word.end()); // 정렬
        for (int k = 0; k < word.length()-1;k++){
            if(word[k] == word[k+1]){//중복된값이 있으면
                isgroup = false//그룹이 아님
                break;
            }
        }
        if(isgroup){
            ans++;
        }
    }
    cout << ans;
    return 0;
// 11min
cs
체감난이도 걸린시간 참고 사용 알고리즘, 문법
11min x erase, unique

 

반응형