[BaekJoon 2941][⚪5] 크로아티아 알파벳
❓ 문제
🎯 난이도
Silver ⚪5
🧠 풀이
1. 내 풀이 (구현)
- 알고리즘
Implementation,string
- 설명
일반적인 반복문을 통해 문자열을 순회하는 방식의 풀이이다.
미리 가능한 크로아티아 알파벳을 배열에 저장하고, 입력 받은 문자열을 순회하며 찾는 알파벳이 있는지를 찾는 방식이다. substr로 원하는 길이만큼의 문자열을 잘라내고, 알파벳을 찾으면 반복문의 i가 그 길이만큼 옆으로 이동해야 하기에 증감식도 추가해줘야 한다.
일반적으로 substr이 문자열을 새로 생성하고 그 길이만큼 복사해야하는 상수 비용이 존재하지만, 가능한 문자열을 모두 조건식으로 묶어 놓는 것보다는 깔끔해보여서 이렇게 로직을 만들었다.
substr은 상수 시간이고 배열을 순회하는 반복문 또한 크기가 8인 상수 시간의 반복문이므로, 전체적인 시간 복잡도는 O(N)이다.
- 코드
내 풀이 코드
#include <iostream>
#include <string>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 가능한 알파벳 미리 할당
string arrCroa[7]
{
"c=",
"c-",
"d-",
"lj",
"nj",
"s=",
"z="
};
string strInput{};
cin >> strInput;
int iCnt{}; // 알파벳 개수
int iLength{ static_cast<int>(strInput.length()) }; // 입력받은 문자열 길이
for(int i = 0; i < iLength; ++i)
{
// 3글자 이상이고 잘라낸 문자열이 알파벳에 해당하는 경우
if(i < iLength - 2 && strInput.substr(i, 3) == "dz=")
{
// 알파벳 개수 증가, 반복문의 i에 2를 더하면 반복문의 증감식이랑 합쳐져서 3칸 옆으로 이동
++iCnt;
i += 2;
continue;
}
// 2글자 이상인 경우
else if(i < iLength - 1)
{
bool bFound{}; // 알파벳 발견했을 때의 플래그 변수
string strCurr{ strInput.substr(i, 2) }; // 2글자로 잘라낸 문자열
for(const string& strCroa : arrCroa)
{
// 알파벳 발견한 경우
if(strCurr == strCroa)
{
// 플래그 변수 갱신
bFound = true;
// 알파벳 개수, i 증가, 반복문의 증감식이랑 합쳐져서 2칸 옆으로 이동
++iCnt;
++i;
break;
}
}
// 알파벳 발견했으면 continue
if(bFound)
{
continue;
}
}
// 위의 조건식들에 해당 안하면 그냥 알파벳으로 간주해 개수 증가
++iCnt;
}
cout << iCnt;
return 0;
}
2. 추가 풀이 (문자열 치환)
- 알고리즘
Implementation,string
- 설명
string의 함수들을 이용해 문자열 탐색, 치환하는 방식이다.
위에서는 반복문 내의 조건문을 사용해 로직을 만들었지만, 이 풀이 같은 경우는 'string'의 'find', 'replace' 함수를 이용해 간결함과 가독성을 챙겼다.
find 함수로 원하는 알파벳이 문자열 내에 존재하는지를 찾는 동시에 그 위치를 갱신하고, 찾으면 replace 함수로 해당 문자열을 "#" 한 문자로 치환한다. 그리고 위치를 1 증가시켜 다음 위치에서도 계속 찾고 다시 치환하고를 반복하면 결국에 크로아티아 알파벳은 모두 "#"로 치환되고, 최종 문자열의 길이는 곧 전체 알파벳의 개수가 된다.
find, replace는 일반적으로 O(N)이지만 발견되는 알파벳 개수가 최대 N개일수도 있으므로 최악의 경우 시간 복잡도는 O(N²)이 된다.
- 코드
내 풀이 코드
#include <iostream>
#include <string>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 가능한 알파벳 미리 할당
string arrCroa[8]
{
"c=",
"c-",
"dz=",
"d-",
"lj",
"nj",
"s=",
"z="
};
string strInput{};
cin >> strInput;
for(const string& strCroa : arrCroa)
{
size_t sPos{}; // 현재 찾아낸 알파벳의 위치 변수
// 알파벳 찾으면서 sPos 갱신
while((sPos = strInput.find(strCroa, sPos)) != string::npos)
{
// sPos 위치에서 알파벳 길이만큼을 "#" 한 문자로 치환
strInput.replace(sPos, strCroa.length(), "#");
// 찾은 위치 다음 위치에서도 계속 찾을 수 있도록 증가
++sPos;
}
}
// 전체 길이가 곧 알파벳의 갯수가 됨
cout << strInput.length();
return 0;
}
💭 후기
코드가 간결하고 가독성이 좋은 쪽은 두 번째 풀이지만, 이번 문제처럼 상수가 작은 경우가 아니라면 좀 위험할 수도 있다. 그 이유는 find 함수는 전체 문자열을 순회하므로 O(N), replace도 문자열을 지우고 치환하면서 문자들이 당기거나 밀어지므로 O(N)이다. 거기에 replace는 이 과정에서 문자열의 이동 및 재할당도 일어날 수 있어서 상수 비용이 더 늘어날 가능성도 있다.
따라서 상술한 듯이 로직 자체의 시간 복잡도도 최악의 경우 'O(N²)'이고, 상수 비용도 상당히 늘어날 가능성이 있으므로, 조건을 잘 따져보고 로직을 짜도록 하자.
Comments