인프런 커뮤니티 질문&답변
작성한 질문수
1-M 좋은단어 반례를 찾아보고싶습니다!
해결된 질문
작성
·
162
0
강의를 듣기전에 제가 먼저 문제를 해결해보고, 강사님의 풀이방법이랑 비교하는식으로 학습중에 있습니다.
1-M 좋은단어 푸는 도중 백준의 반례 예시
BABBAB
ABBABB
ABBBBA
AAAAABBAAAAA
이경우를 다 해봤는데도 안되서, 강사님 풀이를 보기 전에 제힘으로 해결해보고자 하는데 반례 찾기에 도움을 여쭐수 있을까요?
아래는 코드입니다
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
using namespace std;
int main()
{
ios::ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int count = 0;
bool check = true;
for (int i = 0; i < n; i++)
{
string temp;
cin >> temp;
int cnt2=0;
check = true;
if (temp.length() % 2 == 1)
continue;
while (check && temp.length())
{
if (temp[0] == 'A')
{
if (temp[temp.length()-1] == 'A')
{
temp.erase(temp.length() - 1, 1);
temp.erase(0, 1);
}
else
{
int loc = temp.find('A', 1);
if (loc % 2 == 0 or loc == -1)
check = false;
else
{
temp.erase(loc, 1);
temp.erase(0, 1);
}
}
}
else
{
int end = temp.length() - 1;
if (temp[temp.length()-1] == 'B')
{
temp.erase(temp.length() - 1, 1);
temp.erase(0, 1);
}
else
{
int loc = temp.find('B', 1);
if (loc % 2 == 0 or loc == -1)
check = false;
else
{
temp.erase(loc, 1);
temp.erase(0, 1);
}
}
}
}
if(check)
count++;
}
cout << count;
system("pause");
return 0;
}
답변 1
2
안녕하세요. 안형준님ㅎㅎ
먼저 자신의 힘으로 코드를 구축하려고 하는 것은 잘했습니다.
하지만 코드 상에 틀린 점이 있습니다.
1. 시간복잡도가 너무 큽니다. 이 문자열의 최대길이는 10만이고. 형준이님이 짠 코드의 시간복잡도는 얼마일까요?
N^2인데요? 매번 문자열 전체를 확인하고 있어요(find함수를 씀)
2. 틀린 로직이 있습니다. 자 예를 들어
BBAABAAB
를 들어보죠.
이 문자열은 BB / AA / B...B / .AA. 이렇게 연결해야 좋은 단어입니다.
하지만 형준님의 코드는 그렇지가 않죠.
B.......B연결하고
.B...B 연결하고 그렇게 해서 삭제되어 남은 AAAA 중에서
그 다음 A.....A 이렇게 연결해 버리는 즉, "끝점의 우선순위"가 높게 설정되어있기 때문에
(AAAA이렇게 되어있을 때 A...A를 먼저 연결해버리는.)
문제의 의도와는 다르게 틀리게 되는 것이죠.
자 그렇게 연결하면 B가 중간에 섞여있기 때문에 나쁜단어가 되어버리죠?물론 코드를 구동하게 되면 "맞는 답"으로 나오지만 이건 형준님의 로직과는 전혀 상관없이 AAAA라는게 나와서 결국 모두 erase가 되서 맞게 나오는 것 뿐입니다. 문제에서 "교차하지 말고"라고 되어있다면 교차하지 않게 짝을 짓게 해야하는 것이죠.
위 그림처럼 말이죠.
아 그리고 인프런 에디터가 좀 안좋습니다. 그렇기 때문에 앞으로 코드 올려주실 때 VSCODE등 에디터에 있는 내용을 그대로
복사해서 붙여넣기해서 보내주세요. 제가 올린 것처럼 말이죠.
지금 올려주신 내용처럼 올려주시면... 정말 코드 보기가 힘들어요 ㅜ
또 질문사항있으시면 언제든 말씀 부탁드립니다.
감사합니다.
강사 큰돌 올림.
답변 감사합니다!