[백준] 1620 : 나는야 포켓몬 마스터 이다솜 | C++

0. 문제

 

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

 

---

1. 문제풀이 핵심

a) map의 인덱스 접근 제한

  map은 배열이나 vector처럼 인덱스를 통한 직접 접근이 불가능합니다. map은 키-값 쌍으로 이루어져 있으며, 키를 이용해 값을 찾아야 합니다. 따라서 숫자로 입력을 받았을 때, 해당 숫자에 해당하는 문자열을 찾기 위해서는 다른 방법이 필요합니다. 여기서 이유는 map의 내부 구조 때문입니다.

  map의 메모리 구조와 이에 따른 인덱스 접근 불가능

  map은 내부적으로 이진 트리 구조를 사용합니다. 이 때문에 요소들이 삽입되는 순서와 상관없이 자동으로 정렬(현재 노드를 기준으로 왼쪽 노드에는 작은값, 오른쪽 노드에는 큰 값)되며, 이는 키를 기준으로  이루어집니다. 또한 map은 포인터를 통해 트리의 노드들이 연결되어 있어, 특정 인덱스에 바로 접근하는 것이 불가능합니다. 이 점 때문에 map에서의 요소 접근은 키를 통해 이루어져야 하며, 인덱스나 정수로 접근하는 것이 불가능합니다. 또한 인덱스로 값에 접근하기 위해서는 순차적으로 요소를 탐색해야 합니다. 반면에 배열이나 벡터는 메모리상에 연속적으로 저장되기 때문에 인덱스를 통한 직접 접근이 가능합니다. 

 

 

b) map과 배열의 조합

해결 방법은 두 가지입니다:

1. map을 두 개 사용하여 하나는 이름을 키로, 다른 하나는 인덱스를 키로 저장합니다.
2. map과 배열을 조합하여 map으로 이름-인덱스 관계를, 배열로 인덱스-이름 관계를 저장합니다.

이번 문제에서는 두 번째 방법을 사용해 해결했습니다. 왜냐하면 배열은 인덱스 접근이 가능하며 이에 따라 검색에 소요되는 시간복잡도가 O(1)으로 map의 시간복잡도인 O(log n)보다 빠르기 때문입니다.

 

---

2. 문제풀이에 사용된 개념

 

map<string, int> marr;

 

- map 사용하여 O(1)의 시간복잡도로 필요한 값 찾기

- map 에서 iterator 를 이용하여 요소에 접근하는 방법

 

map의 iterator 사용 하기

- auto를 사용하여 간단하게 이터레이터를 사용할 수 있습니다.

for(auto it = marr.begin(); it != marr.end(); ++it){ 
	// 전체 값을 다 돌면서 value를 출력한다 
	cout << it->second; 
}

 

- map의 이터레이터를 선언하는 다른 방법

map<string,int> marr; 
map<string,int>::iterator it; 

for(it = marr.begin(); it != marr.end(); ++it){ 
	cout << it->second; 
    // 또는 cout << it->first; 와 같이 key를 출력할 수도 있음 
}

 

문자열과  int  구별하기

 

a) 아스키코드 범위 사용하기 

문자열의 첫 번째 문자가 알파벳인지 숫자인지를 아스키코드 값을 이용하여 확인합니다.

 

아스키코드 체계

대문자 알파벳 = 65('A') ~ 90('Z')

소문자 알파벳 = 97('a') ~ 122('z')

 

이를 활용하여 문자열의 첫 글자가 이 범위에 속하면 문자로, 그렇지 않으면 숫자로 판단할 수 있습니다.

if (s[0] >= 65 && s[0] <= 122) { // 대문자 'A'부터 소문자 'z'까지
    // s가 문자인 경우
} else {
    // s가 숫자인 경우
}

b) atoi 사용하기 (더 간편한 방법)

atoi 함수는 문자열을 정수로 변환해주는 함수입니다.

이 함수는 문자열에 숫자가 아닌 문자가 포함되어 있으면 0을 리턴합니다. 

 

주의할 점 : 문자열로서 "0"자체가 입력된 상황은 아닌지 추가적으로 검토가 필요합니다.

int num = atoi(s.c_str()); 
if (num == 0 && s != "0") {
    // s가 문자인 경우
} else {
    // s가 숫자인 경우
}

 

c_str() = c++ 형식의 문자열을 c형식의 문자열로 변환합니다.

 

+) stoi랑 atoi 의 차이점

stoi는 c++11부터 만들어진 표준 라이브러리 이고, atoi는 c언어 초창기 시절부터 존재해온 c 표준 라이브러리입니다.

 

stoi는 숫자로 변환할 수 없는 경우 예외를 던집니다. 그래서 다음과 같이 try catch 문을 이용하여 사용할 수 있습니다.

try {
    int num = stoi("123");
} catch (invalid_argument &e) {
    // 문자열이 숫자가 아닌 경우에 대한 예외 처리
}

 

그런데 문자열 숫자 구분에 대해 검색해보면 stoi에 대한 이야기는 많이 안나옵니다. 왜일까 생각해봤는데 타임어택이 있는 코테에서는 더 익숙하고 기억하기 쉽고 빠른 방법을 사용하게 되다보니 atoi가 문자열 구분용으로 쓰이게 된게 아닐까 싶습니다

---

 

3. 문제풀이 코드

#include<bits/stdc++.h>

using namespace std;

#define X first
#define Y second

int n,m;
map<string, int> marr;
vector<string> nameArr;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;

    for(int i=1;i<=n;i++){ //포켓몬 이름 n개 입력받기. 첫대문자+나머지소문자 영어 or 마지막만 대문자 영어
        string s;
        cin>>s;

        marr.insert({s,i}); //포켓몬 이름을 key로 저장
        nameArr.push_back(s); //인덱스로 접근가능하도록 이름 저장
    }

    while(m--){ //내가 맞춰야 하는 문제 입력받기. 문자 들어오면 인덱스로 답, 인덱스 들어오면 문자로 답.
        string s;
        cin>>s;
		
        //문자인지 숫자인지 판별하기
        if(s[0] >= 65 && s[0]<= 122){ //대문자 첫 아스키코드 값 ~ 소문자 마지막 아스키코드 값
            auto it = marr.find(s); 
            cout << it -> Y<<'\n'; // 숫자 출력

        }else{ // 숫자 입력 받은 경우
            int a = stoi(s);
            cout << nameArr[a-1]<<'\n'; // 이름 출력
        }
    }
    
}

 

3-1. 코드 로직 설명

 

1. 포켓몬 이름 저장
   • marr 맵을 사용하여 포켓몬 이름을 키로, 인덱스를 값으로 저장합니다.
   • nameArr 배열을 사용하여 인덱스를 통해 포켓몬 이름을 저장합니다.
2. 문제 해결
   • 입력받은 값이 문자인지 숫자인지 판별합니다.
   • 문자인 경우: map을 통해 해당 포켓몬 이름에 해당하는 인덱스를 찾습니다.
   • 숫자인 경우: 배열을 통해 인덱스에 해당하는 포켓몬 이름을 찾습니다.

 

 

---

 

4. 문제풀이에 사용된 함수

marr.find(s)

 

marr.find(s): map에서 키 s에 해당하는 이터레이터를 반환합니다. 찾는 키값이 없는 경우 marr.end()를 반환합니다.

 

 

stoi(s)

 

문자열 s를 정수로 변환합니다.

 

 

---

 

5. 요약 정리

• map 사용 이유: map은 키-값 쌍으로 데이터를 관리하며, 키를 통해 빠르게 값을 찾을 수 있습니다.
• map의 제한: map은 내부적으로 이진 트리 구조(일반적으로 레드-블랙 트리)를 사용하여 데이터를 저장합니다. 따라서 인덱스 접근이 불가능하며, 이터레이터를 통한 순회가 가능합니다. 
• 해결 방법: map과 배열을 함께 사용하여 인덱스 접근과 키 접근을 모두 지원하는 구조를 구현할 수 있습니다.
• 시간 복잡도: map의 탐색은 O(log n)의 시간 복잡도를 가지며, 배열의 인덱스 접근은 O(1)입니다.