[백준 2941] 크로아티아 알파벳 [C++]

문제 링크: https://www.acmicpc.net/problem/2941

 

 

1. 문제

 

 

 요약해보자면 문자열이 주어졌을 때, 크로아티아를 포함해서 몇 개의 알파벳이 있는지 확인하는 문제입니다. 만약 dddz= 라는 문자열이 들어왔을 때 dz= 1개, d 2개로 해서 총 3개를 출력해주면 됩니다.

 

 

2. 해설

 

 문제 풀이를 간략하게 정리하자면 문자열 안에 문자열이 있는 지 확인하는 방식입니다. 그 문자열을 찾는 방식을 다양하게 풀 수 있는데, 백준의 질문 게시판이나 사람들 풀이를 보니 문자열 자체로 찾기 or 문자를 차례로 비교하기가 있더라고요. 처음에는 후자의 방식을 사용할까 했습니다. 어차피 알파벳을 찾는 거니까 =, - 등의 기호는 잘 안 나올 테니 뒤의 문자를 기준으로 나눠도 괜찮겠다 했습니다. 하지만 솔직히 if나 switch로 나누기 귀찮아서... 어차피 C++은 속도도 빠르겠다 걍 전자의 방식을 택하고 문자열을 찾는 것 자체는 컴퓨터에게 맡기기로 했습니다.

 

 처음 선택한 방식은

1. 문자열을 찾는다

2. 있으면 카운트 변수에 1을 추가하고 그 문자열을 삭제한다

3. 크로아티아 알파벳이 전부 없어질 때까지 반복 후 남은 문자열의 길이를 카운트 변수에 더해준다

 

 였습니다. 하지만 기존 테스트 케이스도 통과하지 못하더라고요. 문제는 바로... 문자열이 삭제되었을 때 그 앞뒤의 문자들이 합쳐져서 새로운 크로아티아 알파벳을 생성한다는 점이었습니다. 

테스트 케이스: ddz=z=
1. 크로아티아 알파벳 "dz=" 검색 -> d 'dz=' z=
2. 문자열 삭제 -> dz= 
3. 다시 알파벳 "dz=" 검색 -> 'dz='
4. 문자열 삭제

 

 이런 방식이 되었기에... 문자열을 삭제하는 대신 공백으로 대체되게끔 했습니다. 

 

3. 풀이

#include <iostream>	// 필요 라이브러리
#include <string>
using namespace std;

int main(){
    string arr[] = {"c=", "c-", "dz=", "d-", "lj", "nj", "s=", "z="};	// 크로아티아 알파벳
    string str;	// 입력 문자열
    cin >> str;	// 문자열 입력
    
    int cnt = 0;	// 카운트 함수
    for(int i = 0; i < 8; i++){	// 크로아티아 알파벳 배열을 원소 하나씩 차례대로 탐색
        // 같은 크로아티아 알파벳이 여러 개 있을 수 있으니 완전히 없어질 때까지 반복
        while(1){
            if(str.find(arr[i]) == string::npos){	
                break;	// 해당 크로아티아 문자열이 없으면 while문에서 나감
            }
            else{
                int index = str.find(arr[i]);	// 해당 크로아티아 알파벳이 있는 인덱스를 찾음
                cnt++;	// 카운트 + 1
                str.replace(index, arr[i].length(), " ");	// 해당 알파벳 길이만큼 공백으로 대체
            }
        }
    }

    for(int i = 0; i < str.length(); i++){
        if(str[i] != ' '){
            cnt++;	// 공백이 아닌 남은 알파벳 수만큼 카운트 변수에 추가
        } 
    }
    
    cout << cnt;	// 카운트 변수 출력
}

 

 옛날부터 어떻게 해야할까 낑낑대던 문제였는데 나중에 다시 보니 너무 쉬운 문제였습니다. 계속 문자열의 첫 글자부터 찾나?  하고 막막했는데 문자열 자체를 find 할 수 있다는 걸 알게 되니까 바로 풀 수 있겠더라고요. 실감이 안 나지만 점차 성장하는 것만 같습니다.