<알고리즘 문제풀이&연습>/[C++] 백준

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

사용자 BlockDMask 2017. 10. 21. 20:51
반응형
  • 안녕하세요. BlockDMask 입니다.

  • 오늘자 문제 풀어보았습니다.

  • 접근을 너무 잘못해서 1시간 반 이상 삽질하다가 풀었네요.

0. 제목

  • 백준 1620 나는야 포켓몬 마스터 이다솜

  • BOJ 1620 나는야 포켓몬 마스터 이다솜

1. 문제 설명

  • 안녕? 내 이름은 이다솜. 나의 꿈은 포켓몬 마스터야. 일단 포켓몬 마스터가 되기 위해선 포켓몬을 한 마리 잡아야겠지?
    .
    .
    (문제.. 전 스토리가 너무 길어요..)
    .
    중략
    .
    .
    .
    오박사 : 그럼 다솜아 이제 진정한 포켓몬 마스터가 되기 위해 도감을 완성시키도록 하여라.
    일단 네가 현재 가지고 있는 포켓몬 도감에서 포켓몬의 이름을 보면 포켓몬의 번호를 말하거나,
    포켓몬의 번호를 보면 포켓몬의 이름을 말하는 연습을 하도록 하여라
    나의 시험을 통과하면, 내가 새로 만든 도감을 주도록 하겠네.
    .
    .
    .
    .
    드디어 여기서 문제;

  • 입력--
    첫째 줄에는 도감이 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야하는 문제의 개수 M 이 주어집니다.
    (1 <= N, M <= 100,000)
    둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력이 들어옵니다.
    포켓몬의 이름은 모두 영어로만 이루어져있고, 첫 글자만 대문자 입니다. 나머지 문자는 소문자로 이루어져 있습니다.
    포켓몬 이름의 최대 길이는 20 입니다.
    다음줄 부터 총 M의 줄에 내가 맞춰야 하는 문제가 입력으로 들어옵니다.
    문제가 알파벳으로만 들어오면 포켓몬 번호를 말해야 합니다.
    문제가 숫자로만 들어오면 포켓몬 번호에 해당하는 문자를 출력하면됩니다.
    입력으로 들어오는 숫자는 반드시 1 보다 크거나 같고 N 보다 작거나 같습니다. 
    입력으로 들어오는 문자도 반드시 도감에 있는 포켓몬 이름만 주어집니다.

  • 출력--
    첫째 줄부터 차례대로  M개의 줄에 각각의 문제에 대한 답을 말하면 됩니다.


2. 풀이 과정

  • 이게;; 쉬워보여도 시간초과가 좀 많이 나서;;
    어떻게 하면 줄일까? 라는 생각을 많이 하게 된 문제였습니다.

  • 결국 생각해 낸것이

  • 문자가 입력될 때를 대비하여 
    (문자 기준으로 오름차순 정렬되게)

  • STL 의 map container를 이용하여 map<string, int>  두가지 타입으로 
    string 을 key 로 받으면서 정렬이 되게끔 하여 string 순으로 나열하는 방법이었고

  • 번호가 입력될 때를 대비하여
    (번호 기준으로 오름차순 정렬되게)
    번호가 입력될 때를 대비하여 string 타입의 배열을 선언하여 접근하는 방식으로 풀었습니다. 


3. 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <string>
#include <cstdio>
#include <map>
#include <cstdlib>
 
using namespace std;
 
int n; //포켓몬의 수
int m; //입력받을 문제의 수
 
char str[21];   //포켓몬 이름
 
map<stringint> mp1;   //문자열 기준으로 정렬
string mp2[100001];     //번호 기준으로 정렬
 
void input(){
    cin >> n;
    cin >> m;
 
    for(int i=0; i<n; i++){
        scanf("%s", str);
        string s = str;
 
        mp1.insert(pair<stringint>(s, i));
        mp2[i] = s;
    }
}
 
 
void solution(){
 
    for(int i=0; i<m ; i++) {
        scanf("%s", str);
 
        if(isdigit(str[0])) {
            cout << mp2[atoi(str)-1<< "\n";
        }else{
 
            string s = str;
            printf("%d\n", mp1[s] + 1);
        }
 
    }
}
 
 
int main(void){
    input();
    solution();
    return 0;
}
 
cs


4. 인증


문제 출처 - https://www.acmicpc.net/problem/1620

감사합니다.


반응형

'<알고리즘 문제풀이&연습> > [C++] 백준' 카테고리의 다른 글

[백준 2439] 별찍기2  (2) 2017.10.30
[백준 2438] 별찍기1  (0) 2017.10.29
[백준 2739] 구구단  (0) 2017.10.28
[백준 8958] OX퀴즈  (0) 2017.10.27
[백준 1620] 나는야 포켓몬 마스터 이다솜  (0) 2017.10.21
[백준 2622] 삼각형 만들기  (0) 2017.10.19
[백준 10818] 최소, 최대  (0) 2017.10.18
[백준 2566] 최댓값  (0) 2017.10.17
[백준 2501] 약수 구하기  (0) 2017.10.17