[BOJ] 1764번: 듣보잡

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

2018-11-18 1차시도 - 시간초과

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

unsigned int N, M;

cin >> N >> M;

vector<string> all;

vector<string> n;

vector<string> m;

while (N--)

{

string name;

cin >> name;

n.push_back(name);

}

while (M--)

{

string name;

cin >> name;

m.push_back(name);

}

vector<string>::iterator iter;

if (N > M)

{

for (int i = 0; i < m.size(); i++)

{

iter = find(n.begin(), n.end(), m[i]);

if (iter != n.end())

iter = find(iter, n.end(), m[i]);

if (iter != n.end())

{

all.push_back(m[i]);

}

}

}

else

{

for (int i = 0; i < n.size(); i++)

{

iter = find(m.begin(), m.end(), n[i]);

if (iter != m.end())

iter = find(iter, m.end(), n[i]);

if (iter != m.end())

{

all.push_back(n[i]);

}

}

}

sort(all.begin(), all.end());

cout << all.size() << endl;

for (int i = 0; i < all.size(); i++)

cout << all[i] << endl;

}

사실 시간 초과 예상했음 ㅎㅅㅎ 떠오르는 방법이 없었다고 한다

2018-11-18 2차시도 - 시간초과

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <cstdio>

using namespace std;

int main()

{

int N, M;

scanf("%d %d", &N, &M);

vector<string> all;

vector<string> n;

vector<string> m;

while (N--)

{

string name;

cin >> name;

n.push_back(name);

}

while (M--)

{

string name;

cin >> name;

m.push_back(name);

}

sort(m.begin(), m.end());

sort(n.begin(), n.end());

vector<string>::iterator here;

vector<string>::iterator iter;

if (N > M)

{

here = m.begin();

for (int i = 0; i < n.size(); i++)

{

iter = find(here, m.end(), n[i]);

if (iter != m.end())

{

all.push_back(n[i]);

here = iter;

}

}

}

else

{

here = n.begin();

for (int i = 0; i < m.size(); i++)

{

iter = find(here, n.end(), m[i]);

if (iter != n.end())

{

all.push_back(m[i]);

here = iter;

}

}

}

printf("%d\n", all.size());

for (int i = 0; i < all.size(); i++)

cout << all[i] << "\n";

}

이것도 시간초과 예상했음 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ주륵................ 바보샛기......

2018-11-18 3차시도 - 런타임에러

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <cstdio>

using namespace std;

int main()

{

int N, M;

scanf("%d %d", &N, &M);

vector<string> ans;

vector<string> n;

vector<string> m;

for (int i = 0; i < N; i++)

cin >> n[i];

for (int i = 0; i < M; i++)

cin >> m[i];

sort(m.begin(), m.end());

sort(n.begin(), n.end());

if (N > M)

{

for (int i = 0; i < M; i++)

if (binary_search(m.begin(), m.end(), n[i]))

ans.push_back(n[i]);

}

else

{

for (int i = 0; i < N; i++)

if (binary_search(n.begin(), n.end(), m[i]))

ans.push_back(m[i]);

}

printf("%d\n", ans.size());

for (int i = 0; i < ans.size(); i++)

cout << ans[i] << "\n";

}

2차시도때부터 뭔가 찾기 전에 sort를 하면 빠를 것 같은데 내가 쓰는 방법이 구려서 시간초과가 난 것을 생각하고 있었는데, 갑자기 문득 binary_search가 떠올랐다! 거기까진 좋았는데 갑자기 입력한 것을 바로 벡터에 때려넣고 싶어서 저렇게 바꿨다가 런타임 오류가 났다. 이건 다음 시도에서 고쳤다. 바보샛기22

2018-11-18 4차시도 - 맞았습니다

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <cstdio>

using namespace std;

int main()

{

int N, M;

scanf("%d %d", &N, &M);

vector<string> ans;

vector<string> n(N);

vector<string> m(M);

for (int i = 0; i < N; i++)

cin >> n[i];

for (int i = 0; i < M; i++)

cin >> m[i];

sort(m.begin(), m.end());

sort(n.begin(), n.end());

if (N > M)

{

for (int i = 0; i < M; i++)

if (binary_search(n.begin(), n.end(), m[i]))

ans.push_back(m[i]);

}

else

{

for (int i = 0; i < N; i++)

if (binary_search(m.begin(), m.end(), n[i]))

ans.push_back(n[i]);

}

printf("%d\n", ans.size());

for (int i = 0; i < ans.size(); i++)

cout << ans[i] << "\n";

}

드디어^^........ 런타임 에러가 난 이유는 당연하다. 크기도 없는데 뭘 인덱스로 접근해서 뭘 때려넣냐는 말이냐 바보 주인샛갸 이러면서 에러가 난 것이었다. C++ 시간에 배웠던 벡터 크기 선언(?)하는 방법을 통해서 미리 벡터 크기를 지정해 주면 인덱스로 접근할 수 있으므로 입력값을 받고 저장하는데 걸리는 시간도 줄였다. 

---

• C++ 벡터 크기 지정하는 방법
  
  vector<string> vec(벡터 크기);
  
  
• 벡터 크기가 정해져 있으면 인덱스를 통해 접근하고, 입력값을 바로 집어넣을 수 있음
  
  
• binary_search(벡터.begin(),벡터.end(),찾을 항목);
  
  중요한 것은 벡터가 오름차순으로 sort되어있어야 한다.