[BOJ] 1620번 : 나는야 포켓몬 마스터 이다솜

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

 

---

 

 생각

변수에 이름을 모두 받아놓고 검색만 하면 되는 간단한 문제 (라고 생각했다..매우 큰 오산)

 

 구현 

몬스터 이름을 받은 경우 -> 번호를 출력하기 위해 map 변수 doc 선언

번호를 받은 경우 -> 몬스터 이름을 출력하기 위해 string 배열 mon 선언

ans는 질문으로 입력 받은 데이터를 저장하기 위해 선언

---

 구현 코드 

#include<bits/stdc++.h>
using namespace std;

int n, m;
string ans[100001], mon[100001];
map<string, int> doc;

int main()
{
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   cin >> n >> m;
   for (int i = 1; i <= n; i++)
   {
      string input;
      cin >> input;
      doc.insert({ input,i });
      mon[i] = input;
   }

   for (int i = 0; i < m; i++)
      cin >> ans[i];

   for (int i = 0; i < m; i++) 
   {
      if (atoi(ans[i].c_str()) != 0)   // 숫자면 문자 출력
         cout << mon[stoi(ans[i])] << "\n";
      else 
      {
         cout << doc[ans[i]] << "\n";
      }
   }
   return 0;
}

 

 

 디버깅 

시간 초과와의 싸움이었다...

1. string 배열에서 탐색

시간 초과가 날만한 곳이 else문에서 이름을 가지고 배열 탐색을 도는 구간뿐이었다. 이 구간을 O(n) 보다 빠른 방법으로 해결해야했다.

string doc[100001], ans[100001];


for (int i = 0; i < m; i++) {
      if (atoi(ans[i].c_str()) != 0)
         cout << doc[stoi(ans[i])] << "\n";
      else {
         for (int j = 0; j < n; j++) {
            if (doc[j + 1] == ans[i])
               cout << j + 1 << "\n";
         }
      }

 

2. vector find()로 해결?

슬프게도 코드가 간단해보인다고 다가 아니다.  vector에서도 탐색은 O(n).. 다른 자료구조가 필요하다고 생각했다.

vector<string> doc(100001), ans(100001);

 for (int i = 0; i < m; i++){
      if (atoi(ans[i].c_str()) != 0) 
         cout << doc[stoi(ans[i])] << "\n";  
      else {
         cout << find(doc.begin(), doc.end(), ans[i]) - doc.begin() << "\n";
      }

 

3. map으로 선언

드디어 해결했다하고 신나게 map으로 코드를 작성하는데 map <int,string>으로 작성하고보니

value 값으로 key값을 찾으려면 직접 구현을 해야한다는 것이다. (시간 복잡도도 O(n)ㅋㅋ)

 

그래서 뒤집어서 map<string,int>로 선언하고 문제의 구간을 해결했다.

번호를 받아서 문자를 출력하려면 배열로 선언했을 때처럼 index로 바로 찾아가는게 더 빨라서 따로 배열을 선언하여 한 번 더 저장해줬다.

 

 리뷰 

자료구조의 시간 복잡도를 잘 외워두고 삽질하지 않도록 하자 ^^

솔직히 같은 데이터를 한 번 더 저장하는게 매우 비효율적이라고 생각해서 그렇게 할 생각은 전혀 못한게 가장 힘든점이었다. 그래서 다른 사람들 코드도 봤는데

1. map<string,string>으로 선언해서 {번호, 이름}, {이름, 번호}로 2번 저장하여 key값이 어떻게 들어오든 검색 가능

2. map<string, int>, map<int,string> 으로 선언해서 따로 저장하여 key값으로 검색

하는 식으로 해결하더라.

효율적인 코드를 짜는 것도 중요하지만 코테를 풀 때는 문제 해결에 중점을 두고 좀 더 열린 생각을 해야하나 싶었다.