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

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

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

 

문제에 그림과 글이 되게 길게 있는데 실질적으로 문제 푸는데는 없어도 전혀 지장이 없었기 때문에 가져오지 않았는데

궁금하다면 문제 링크를 클릭!🖱

 

---

 

✍️ 해결 방법

문자를 입력받았으면 포켓몬의 이름이 사전식으로 정렬되어 있는 배열에서 해당 문자를 찾아서 번호를 출력해 줄 것이고,

숫자를 입력받았으면 인덱스를 활용하여 바로 포켓몬의 이름을 출력해주면 된다.

 

따라서 포켓몬의 이름만 저장할 poketmon 벡터와 포켓몬의 이름과 번호를 쌍으로 저장할 pair 구조체 dictionary를 선언하였다. 

1. 포켓몬의 이름을 입력받을 때마다 poketmon과 dictionary에 각각 저장해준다.

 

2. dictionary를 오름차순(사전식)으로 정렬한다.

(<algorithm> 헤더에 내장되어있는 sort 함수를 사용하면 사전식으로 정렬됨)

 

3. 문제를 입력받는다.

3-1. 입력이 문자인 경우(65 <= (int)key[0] <= 90)

이분 탐색 코드를 활용하여 dictionary에서 해당 문자열을 찾은 뒤에 두번째 원소(포켓몬의 번호) 출력

3-2. 입력이 숫자인 경우

입력받는 문제의 자료형을 string으로 선언했기 때문에 poketmon[입력값] 같이 인덱스에 입력값을 바로 넣을 수 없다.

따라서 string 입력값을 숫자로 변환한 후에 인덱스로 삽입해야 한다.

string 객체를 숫자로 바꾸기 위해서는 atoi(ket.c_str()) 함수를 사용하면 된다!

 

---

 

❗️ 주의 사항

이 문제도 시간 초과와 싸워야 했다.

다른 사람들의 질문을 보니 내 코드도 입출력이 문제였기 때문에 cin, cout 을 scanf, printf로만 바꾸면 끝나는 문제였다.

 

하지만 나는 string 객체를 입력받아야 했기 때문에 cin을 무조건 사용해야 했고,

cin, cout 을 사용하려면 main 함수의 시작 부분에 

cin.tie(NULL);
ios::sync_with_stdio(false);

위와 같은 코드를 추가해주면 scanf, printf를 쓰는 것만큼 속도를 향상시킬 수 있다.

 

그럼 string 객체가 아닌 다른 자료형은 다 cin으로 입력받고 출력할 때는 printf를 사용하면 되는 줄 알았는데,,,

위의 코드를 사용할 경우에는 주의할 사항이 있다.

 

scanf, printf는 c의 표준 입출력 방식이고 cin, cout은 c++ 의 입출력 방식이기 때문에

두개를 혼용할 경우 멀티 쓰레드 환경이 되어 때문에 프로그램이 실행되지 않는다. 

 

따라서 항상 하나로 통일해서 쓰도록 하자!

위의 코드에 대한 자세한 설명과 scanf, printf, cin, cout 이외에도 다양한 입출력 방식의 속도 차이를 자세하게 정리해놨으니 필요할때마다 들어가서 읽어보면 좋을 것 같다 ㅎㅎ

https://aerimforest.tistory.com/130

cin.tie(NULL) / ios_base::sync_with_stdio(false) 사용시 주의사항

 

---

 

🔎 내 코드(C++)

// [1620] 나는야 포켓몬 마스터 이다솜
// https://www.acmicpc.net/problem/1620
// binary search
// cin, cout, c 표준 입출력(printf, scanf)을 혼용할 경우 틀림
// 즉, 멀티 쓰레드 환경이 아닌 싱글 쓰레드 환경이어야 함
// 알고리즘 문제풀이시에만 사용하고 실무에서는 사용 X

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void)
{
    cin.tie(NULL);
	ios::sync_with_stdio(false);

    int n, m;
    string key;
    vector <string> poketmon;
    pair<string, int> dictionary[100001];
    cin >> n >> m;

    for(int i = 0 ; i < n ; i++) {
        cin >> key;
        poketmon.push_back(key);
        dictionary[i].first = poketmon[i]; dictionary[i].second = i;
    }

    // 사전순으로 정렬
    sort(dictionary, dictionary + n);

    for(int i = 0 ; i < m ; i++) {
        cin >> key;
        
        // 입력이 '문자'라면
        if(65 <= (int)key[0] && (int)key[0] <= 90) {
            int mid, left = 0, right = n - 1;
            
            while(left <= right) {
                mid = (left + right) / 2;
                
                if(dictionary[mid].first < key) {
                    left = mid + 1;
                }
                else if(dictionary[mid].first > key) {
                    right = mid - 1;
                }
                else {
                    // endl 대신  '/n'을 사용할 것!(endl은 출력 버퍼를 비우기 때문에 느림)
                    cout << dictionary[mid].second + 1 << '\n';
                    break;
                }
            }
        }
        
        // 입력이 '숫자'라면
        else {
            cout << poketmon[atoi(key.c_str()) - 1] << '\n';
        }
    }
}