๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
โœจ Algorithm

[๋ฐฑ์ค€/C++] 1620๋ฒˆ : ๋‚˜๋Š”์•ผ ํฌ์ผ“๋ชฌ ๋งˆ์Šคํ„ฐ ์ด๋‹ค์†œ

by nitronium102 2021. 9. 12.

๋ฌธ์ œ

์˜ค๋ฐ•์‚ฌ : ๊ทธ๋Ÿผ ๋‹ค์†œ์•„ ์ด์ œ ์ง„์ •ํ•œ ํฌ์ผ“๋ชฌ ๋งˆ์Šคํ„ฐ๊ฐ€ ๋˜๊ธฐ ์œ„ํ•ด ๋„๊ฐ์„ ์™„์„ฑ์‹œํ‚ค๋„๋ก ํ•˜์—ฌ๋ผ. ์ผ๋‹จ ๋„ค๊ฐ€ ํ˜„์žฌ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ํฌ์ผ“๋ชฌ ๋„๊ฐ์—์„œ ํฌ์ผ“๋ชฌ์˜ ์ด๋ฆ„์„ ๋ณด๋ฉด ํฌ์ผ“๋ชฌ์˜ ๋ฒˆํ˜ธ๋ฅผ ๋งํ•˜๊ฑฐ๋‚˜, ํฌ์ผ“๋ชฌ์˜ ๋ฒˆํ˜ธ๋ฅผ ๋ณด๋ฉด ํฌ์ผ“๋ชฌ์˜ ์ด๋ฆ„์„ ๋งํ•˜๋Š” ์—ฐ์Šต์„ ํ•˜๋„๋ก ํ•˜์—ฌ๋ผ. ๋‚˜์˜ ์‹œํ—˜์„ ํ†ต๊ณผํ•˜๋ฉด, ๋‚ด๊ฐ€ ์ƒˆ๋กœ ๋งŒ๋“  ๋„๊ฐ์„ ์ฃผ๋„๋ก ํ•˜๊ฒ ๋„ค.

์ž…๋ ฅ

์ฒซ์งธ ์ค„์—๋Š” ๋„๊ฐ์— ์ˆ˜๋ก๋˜์–ด ์žˆ๋Š” ํฌ์ผ“๋ชฌ์˜ ๊ฐœ์ˆ˜ N์ด๋ž‘ ๋‚ด๊ฐ€ ๋งž์ถฐ์•ผ ํ•˜๋Š” ๋ฌธ์ œ์˜ ๊ฐœ์ˆ˜ M์ด ์ฃผ์–ด์ ธ.

N๊ณผ M์€ 1๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 100,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์•ผ

๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ํฌ์ผ“๋ชฌ์˜ ๋ฒˆํ˜ธ๊ฐ€ 1๋ฒˆ์ธ ํฌ์ผ“๋ชฌ๋ถ€ํ„ฐ N๋ฒˆ์— ํ•ด๋‹นํ•˜๋Š” ํฌ์ผ“๋ชฌ๊นŒ์ง€ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ž…๋ ฅ์œผ๋กœ ๋“ค์–ด์™€. ํฌ์ผ“๋ชฌ์˜ ์ด๋ฆ„์€ ๋ชจ๋‘ ์˜์–ด๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ์žˆ๊ณ , ์ฒซ ๊ธ€์ž๋งŒ ๋Œ€๋ฌธ์ž์ด๊ณ , ๋‚˜๋จธ์ง€ ๋ฌธ์ž๋Š” ์†Œ๋ฌธ์ž๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ ์žˆ์–ด. ํฌ์ผ“๋ชฌ ์ด๋ฆ„์˜ ์ตœ๋Œ€ ๊ธธ์ด๋Š” 20์ด์•ผ. ๊ทธ ๋‹ค์Œ ์ค„๋ถ€ํ„ฐ ์ด M๊ฐœ์˜ ์ค„์— ๋‚ด๊ฐ€ ๋งž์ถฐ์•ผํ•˜๋Š” ๋ฌธ์ œ๊ฐ€ ์ž…๋ ฅ์œผ๋กœ ๋“ค์–ด์™€. ๋ฌธ์ œ๊ฐ€ ์•ŒํŒŒ๋ฒณ์œผ๋กœ๋งŒ ๋“ค์–ด์˜ค๋ฉด ํฌ์ผ“๋ชฌ ๋ฒˆํ˜ธ๋ฅผ ๋งํ•ด์•ผ ํ•˜๊ณ , ์ˆซ์ž๋กœ๋งŒ ๋“ค์–ด์˜ค๋ฉด, ํฌ์ผ“๋ชฌ ๋ฒˆํ˜ธ์— ํ•ด๋‹นํ•˜๋Š” ๋ฌธ์ž๋ฅผ ์ถœ๋ ฅํ•ด์•ผํ•ด. ์ž…๋ ฅ์œผ๋กœ ๋“ค์–ด์˜ค๋Š” ์ˆซ์ž๋Š” ๋ฐ˜๋“œ์‹œ 1๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , N๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™๊ณ , ์ž…๋ ฅ์œผ๋กœ ๋“ค์–ด์˜ค๋Š” ๋ฌธ์ž๋Š” ๋ฐ˜๋“œ์‹œ ๋„๊ฐ์— ์žˆ๋Š” ํฌ์ผ“๋ชฌ์˜ ์ด๋ฆ„๋งŒ ์ฃผ์–ด์ ธ. 

์ถœ๋ ฅ

์ฒซ์งธ ์ค„๋ถ€ํ„ฐ ์ฐจ๋ก€๋Œ€๋กœ M๊ฐœ์˜ ์ค„์— ๊ฐ๊ฐ์˜ ๋ฌธ์ œ์— ๋Œ€ํ•œ ๋‹ต์„ ๋งํ•ด์คฌ์œผ๋ฉด ์ข‹๊ฒ ์–ด!!!. ์ž…๋ ฅ์œผ๋กœ ์ˆซ์ž๊ฐ€ ๋“ค์–ด์™”๋‹ค๋ฉด ๊ทธ ์ˆซ์ž์— ํ•ด๋‹นํ•˜๋Š” ํฌ์ผ“๋ชฌ์˜ ์ด๋ฆ„์„, ๋ฌธ์ž๊ฐ€ ๋“ค์–ด์™”์œผ๋ฉด ๊ทธ ํฌ์ผ“๋ชฌ์˜ ์ด๋ฆ„์— ํ•ด๋‹นํ•˜๋Š” ๋ฒˆํ˜ธ๋ฅผ ์ถœ๋ ฅํ•˜๋ฉด ๋ผ. ๊ทธ๋Ÿผ ๋•กํ~

ํ’€์ด

๋ฌธ์ œ ์ž์ฒด๋Š” map์„ ์‚ฌ์šฉํ•˜๋ฉด ์–ด๋ ต์ง€ ์•Š๊ฒŒ ํ’€ ์ˆ˜ ์žˆ์œผ๋‚˜ ์‹œ๊ฐ„์ดˆ๊ณผ์— ์œ ์˜ํ•ด์•ผ ํ•œ๋‹ค.

#include <iostream>
#include <map>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m;
    string input;
    map<string, int> name;
    map<int, string> number;

    cin >> n >> m;
    // ํฌ์ผ“๋ชฌ ๋ฒˆํ˜ธ : 1๋ฒˆ ~ n๋ฒˆ
    for (int i=1; i<=n; i++){
        cin >> input;
        name[input] = i; // ์ด๋ฆ„ ๋„๊ฐ์— ์ €์žฅ
        number[i] = input; // ๋ฒˆํ˜ธ ๋„๊ฐ์— ์ €์žฅ
    }

    while(m--){
        cin >> input;
        if (isdigit(input[0])) // ์ˆซ์ž๋ฉด ๋ฒˆํ˜ธ ๋„๊ฐ ์ฐธ์กฐ
            cout << number[stoi(input)] << "\n";
        else
            cout << name[input] << "\n";
    }
}

๋Œ“๊ธ€