오늘을 배우고 내일을 개발하다

문제 링크 : https://www.acmicpc.net/problem/13305

[문제]

어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다. 

처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km 마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.

예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 위에 있는 숫자는 도로의 길이를 표시한  것이다.

제일 왼쪽 도시에서 6리터의 기름을 넣고, 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총 비용은 30원이다. 만약 제일 왼쪽 도시에서 2리터의 기름을 넣고(2x5 = 10원) 다음 번 도시까지 이동한 후 3리터의 기름을 넣고(3x2 = 6원) 다음 도시에서 1리터의 기름을 넣어(1x4 = 4원) 제일 오른쪽 도시로 이동하면, 총 비용은 20원이다. 또 다른 방법으로 제일 왼쪽 도시에서 2리터의 기름을 넣고(2x5 = 10원) 다음 번 도시까지 이동한 후 4리터의 기름을 넣고(4x2 = 8원) 제일 오른쪽 도시까지 이동하면, 총 비용은 18원이다.

각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

[입력]

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다. 다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다. 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다.

[출력]

표준 출력으로 제일 왼쪽 도시에서 오른쪽 도시로 가는 최소 비용을 출력한다.

[서브태스크]

[알고리즘 분류]

• 그리디 알고리즘

[정답 코드]

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

long long N, v, price, s[n], r[n-1];
int main() {
	cin >> N;
    
    // 길 입력
	for(int i=0;i<N-1;++i) cin >> r[i];
    
    // 주유소 입력
	for(int i=0;i<N;++i) cin >> s[i];
    
    // v는 주유소 최소 가격
    // 시작은 기름이 없는 상태로 다음 도시까지는 무조건 거리만큼 충전 = price(총 가격)
	v = s[0]; price = v * r[0];

	for(int i=1;i<N-1;i++) {
      // 최소 주유 가격과 다음 도시의 주유 가격을 비교해 저장
	  v = min(v,s[i]);
      // 최소 주유 가격과 다음 도시까지의 거리를 곱해 price에 추가
	  price += v * r[i];
	}
	cout << price;
}

[결과]

문제 링크 : https://www.acmicpc.net/problem/20920

[문제]

화은이는 이번 영어 시험에서 틀린 문제를 바탕으로 영어 단어 암기를 하려고 한다. 그 과정에서 효율적으로 영어 단어를 외우기 위해 영어 단어장을 만들려 하고 있다. 화은이가 만들고자 하는 단어장의 단어 순서는 다음과 같은 우선순위를 차례로 적용하여 만들어진다.

1. 자주 나오는 단어일수록 앞에 배치한다.
2. 해당 단어의 길이가 길수록 앞에 배치한다.
3. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다.

M보다 짧은 길이의 단어의 경우 읽는 것만으로도 외울 수 있기 때문에 길이가 M이상인 단어들만 외운다고 한다. 화은이가 괴로운 영단어 암기를 효율적으로 할 수 있도록 단어장을 만들어 주자.

[입력]

첫째 줄에는 영어 지문에 나오는 단어의 개수 N과 외울 단어의 길이 기준이 되는 M이 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100000, 1 ≤ M ≤ 10)

둘째 줄부터 N + 1번째 줄까지 외울 단어를 입력받는다. 이때의 입력은 알파벳 소문자로만 주어지며 단어의 길이는 10을 넘지 않는다.

단어장에 단어가 반드시 1개 이상 존재하는 입력만 주어진다.

[출력]

화은이의 단어장에 들어 있는 단어를 단어장의 앞에 위치한 단어부터 한 줄에 한 단어씩 순서대로 출력한다.

[알고리즘 분류]

• 자료 구조
• 문자열
• 정렬
• 해시를 사용한 집합과 맵
• 트리를 사용한 집합과 맵

[해설]

주어진 단어장의 순서에 따라 정렬하는 법을 구상할 줄만 안다면 sort와 정렬 식을 이용해 쉽게 해결할 수 있는 문제였다.

[정답 코드]

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

vector<string> wds;
unordered_map<string,int> nt;
int n, m;
string w;

bool cmp(string a, string b) {
  // 단어의 길이가 같고 빈도수가 동일하다면 사전 순으로 정렬
  if(a.size() == b.size() && nt[a] == nt[b]) {
    return a < b;
  }
  // 빈도수가 동일하다면 길이 순으로 정렬
  else if (nt[a] == nt[b]) {
    return a.size() > b.size();
  }
  // 빈도수로 정렬
  return nt[a] > nt[b];
}

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> n >> m;
  while(n--) {
    cin >> w;
    // 주어진 단어의 길이가 m보다 크거나 같은 경우
    if(w.length() >= m) {
      // 만약 단어가 단어장에 이미 존재한다면 빈도수 + 1
      if(nt[w]) nt[w]++;
      // 존재하지 않는 경우 단어장에 빈도수 1로 저장한다.
      else {
        nt[w] = 1;
        wds.push_back(w);
      }
    }
  }
  // 주어진 단어를 저장한 배열을 위의 cmp식에 따라 정렬한다.
  sort(wds.begin(), wds.end(), cmp);
  
  for(const auto& i : wds) cout << i << '\n';
}

[결과]

문제 링크 : https://www.acmicpc.net/problem/1629

[문제]

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

[입력]

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

[출력]

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

[알고리즘 분류]

• 수학
• 분할 정복을 이용한 거듭제곱

[해설]

참고자료 : https://st-lab.tistory.com/237

이 문제는 분할 정복(Divide and Conquer) 알고리즘을 적극 활용해야하는 문제로, 반복문 혹은 재귀를 단순하게 사용하는 식으로 접근하게 되면 메모리 초과, 시간 초과 등의 문제로 인해 해결이 불가능하다.

그렇다면 어떻게 문제를 분할해야하는가를 생각해보았을 때, 모듈러 성질( (a * b) % c = (a % c * b % c) % c )과 지수법칙( a^n+m = aⁿ * a^m )를 이용할 수 있음을 알 수 있을 것이다.

해당 문제에서 지수법칙을 이용하는 방법은 간단하다, 문제에서 주어진 지수를 1이 될 때까지, 즉 문제가 더 이상 나눠지지 않을 때 까지 분할정복을 계속 이어나가는 것이다.

예시)

a4 = ((a1 * a1) * (a1 * a1)) * ((a1 * a1) * (a1 * a1))

이를 코드로 나타내면 다음과 같이 나타낼 수 있다.

long long p(long long A, long long Exp) {
	if(Exp == 1) return A;

  	long long t = p(A, Exp / 2);
	
	if(Exp % 2 == 1) return t * t * A;
	return t * t;
}

그 다음으로 생각해보아야 하는 것이 모듈러 연산이다.

위에 주어진 식에 그냥 c로 나누게 되면, 즉 다음과 같은 식( t * t * A % c )을 만들게 되면 틀린 값이 나오게 되는데, 이는 문제에서 입력으로 주어지는 A, B, C 중 A와 B가 최댓값 2,147,483,647으로 주어지게 되는 경우 t * t 식에서 long long의 범위를 넘어가 잘못된 계산이 진행되기 때문이다.

( t * t * A % c ) 식에 모듈러 연산( (a * b) % c = (a % c * b % c) % c )을 적용해 올바르게 식을 구성해보면 다음과 같이 나타낼 수 있다.

(t * t * A) % c = ((t * t % c) * (A % c)) % c
			    = (((t * t % c) % c) * (A % c)) % c 
			    = ((t * t % c) * A) % c

이렇게 구성한 식을 이용해 리턴값을 다음과 같이 재구성해주면 된다.

long long p(long long A, long long Exp) {
	if(Exp == 1) return A % c;

  	long long t = p(A, Exp / 2);
	
	if(Exp % 2 == 1) return (t * t % c) * A % c;
	return t * t % c;
}

[정답 코드]

#include <ios>
long long a, b, c, k;

long long p(long long A, long long Exp) {
	if(Exp == 1) return A % c;

  	long long t = p(A, Exp / 2);
	
	if(Exp % 2 == 1) return (t * t % c) * A % c;
	return t * t % c;
}

int main() {
  scanf("%lld%lld%lld",&a,&b,&c);
  printf("%lld",p(a, b));
}

[결과]

문제 링크 : https://www.acmicpc.net/problem/2096

[문제]

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

[입력]

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

[출력]

첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.

[알고리즘 분류]

• 다이나믹 프로그래밍
• 슬라이딩 윈도우

[해설]

해당 문제는 "위에서부터 내려오면서 값을 더해온"라는 개념이 아닌, "아래의 값은 위에서 어떤 값을 가져와야 크거나 작은 값을 가질 수 있는가?"를 생각하면서 해결하면 쉽게 해결할 수 있었다.

그림으로 나타내면 다음과 같이 나타낼 수 있다.

[정답 코드]

#include <bits/stdc++.h>
using namespace std;
// a배열은 현재 칸으로 입력되는 숫자배열
// 최솟값, 최댓값을 누적해가며 도출할 배열 mn과 mx, 그리고 이전 값을 임시로 저장할 t0~2를 선언한다
int n,a[3],mn[3],mx[3],t0,t1,t2;

int main(){
  cin >> n;
  while(n--){
  	// 현재 칸 입력받기
    cin >> a[0] >> a[1] >> a[2];
    // 최솟값 누적
    t0 = mn[0]; // 이전 줄의 첫 번째 누적값
    t1 = mn[1]; // 이전 줄의 두 번째 누적값
    t2 = mn[2]; // 이전 줄의 세 번째 누적값

	// 이전 줄의 각 누적값들을 비교해 더 작은 값을 현재 칸의 값과 더해 저장한다
    mn[0] = min(t0,t1) + a[0]; 
    mn[1] = min({t0,t1,t2}) + a[1];
    mn[2] = min(t1,t2) + a[2];
	// 최댓값 누적
    t0 = mx[0];
    t1 = mx[1];
    t2 = mx[2];

	// 이전 줄의 각 누적값들을 비교해 더 큰 값을 현재 칸의 값과 더해 저장한다
    mx[0] = max(t0,t1) + a[0];
    mx[1] = max({t0,t1,t2}) + a[1];
    mx[2] = max(t1,t2) + a[2];
  }
  // 누적된 각 값들의 배열에서 최댓값, 최솟값을 순서대로 출력한다
  cout << max({mx[0],mx[1],mx[2]}) << " " << min({mn[0],mn[1],mn[2]});
}

[결과]

문제 링크 : https://www.acmicpc.net/problem/1932

[문제]

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

[입력]

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

[출력]

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

[알고리즘 분류]

• 다이나믹 프로그래밍

[해설]

문제의 설명을 보면 이 문제는 주어진 값을 가지고 특정 위치에서 시작하여 끝까지 값을 중복해 나가 정답을 구하는 문제임을 알 수 있다.
문제에서는 위에서부터 내려오면서 수의 합이 최대가 되는 경로를 구한다고 하고있지만 코드를 이와 같이 작성할 경우 n의 크기가 커질 수록 아래층에서의 분기점이 많아지게 되어 계산 과정이 복잡하게 될 것이다.

하지만, 정수 삼각형의 아래에서 두 숫자끼리 비교해가며 더 큰 수를 윗 층의 숫자에 중복해 나가는 방식으로 풀게되면 복잡한 비교 과정이 단순하게 변하게 된다.

문제에서 주어진 예시로 표현해보자면 다음과 같이 나타낼 수 있는 것이다.

[정답 코드]

#include<bits/stdc++.h>
using namespace std;
int n, M[501][501];

int main(){
	scanf("%d",&n);
    
	for(int i=0;i<n;i++) 
      for(int j=0;j<i+1;j++) 
        scanf("%d",&M[i][j]);
    
	for(int i=n-1;i>=1;i--) 
      for(int j=0;j<i;j++) 
        M[i-1][j] += max(M[i][j],M[i][j+1]);
        
	printf("%d",M[0][0]);
}

[결과]

문제 링크 : https://www.acmicpc.net/problem/1149

[문제]

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

[입력]

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

[출력]

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

[알고리즘 분류]

• 다이나믹 프로그래밍

[해설]

이번 문제는 집들의 색깔이 이전 색과 겹치지 않도록 칠하며, 그 중에서도 비용이 최소가 되는 결과를 구하는 문제이다.

해당 문제를 작게 나누어 생각해보면,

"'집i'가 빨간색이 되기 위해서는 '집i-1'가 초록색 혹은 파란색이어야 한다."

"'집i'가 파란색이 되기 위해서는 '집i-1'가 빨간색 혹은 초록색이어야 한다."

"'집i'가 초록색이 되기 위해서는 '집i-1'가 빨간색 혹은 파란색이어야 한다."

로 나타낼 수 있다.

즉, r에는 (g와 b 중 더 작은 값 + 현재 집을 빨강으로 칠하는 비용)을 중복해 나가고, g에는 (r과 b중 더 작은 값 + 현재 집을 초록으로 칠하는 비용)을, b에는 (r과 g중 더 작은 값 + 현재 집을 파랑으로 칠하는 비용)을 지속적으로 중복하고 이들 중 최솟값을 선택하게 되면 그 값이 모든 집을 칠하는 비용의 최솟값이 된다. 

[정답 코드]

#include<bits/stdc++.h>
using namespace std;
int main() {
	int N,r=0,g=0,b=0,i,j,k,nr,ng,nb;
	cin >> N;
	while(N--) {
		cin >> i >> j >> k;
		nr=min(g,b)+i;ng=min(r,b)+j;nb=min(r,g)+k;
		r=nr; g=ng; b=nb;
	}
	cout << min({r,g,b});
}

[결과]

문제 링크 : https://www.acmicpc.net/problem/1697

[문제]

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*N의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

[입력]

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

[출력]

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

[알고리즘 분류]

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

[해설]

이 문제는 수빈이가 동생의 위치까지 이동(n+1, n-1, n*2)했을 때의 최소 이동 시간을 구하는 문제이다.

따라서, 여러 경우의 수를 탐색해가며 해답을 찾기에 가장 적합한 너비 우선 탐색(BFS) 알고리즘을 이용해 쉽게 해결할 수 있는 문제이다.

너비 우선 탐색에 사용할 queue에 삽입될 요소는 각각 수빈이의 {위치, 이동 시간} 이며, "이동 범위가 0과 100001 이내에 존재한다" 라는 조건에 부합할 경우 각각의 이동 경우 (n-1, n+1, n*2)를 queue에 지속적으로 삽입하고 방문 여부를 기록한다.

위의 과정을 "수빈이의 위치 = 동생의 위치" 가 될 때까지 반복하며, 마지막에는 이동 횟수를 출력하며 실행을 종료한다.

[정답 코드]

#include <bits/stdc++.h>
std::queue<std::pair<int,int>> q;
// v배열은 이동 가능한 범위에서 방문 여부를 확인할 배열
int N,M,v[100001];

int main() {
  scanf("%d%d",&N,&M);
	q.push({N, 0});
	while(!q.empty()) {
		int a=q.front().first, b=q.front().second;
		q.pop();
        // 수빈이의 위치와 동생의 위치인가?
		if(a==M) {
      printf("%d",b);
			return 0;
		}
        // 수빈의 위치 + 1을 했을 때 이동가능 범위에 속하는가?
		if(a+1 >= 0 && a+1 < 100001 && !v[a+1]) {
			v[a+1] = 1;
			q.push({a+1, b+1});
		}
        // 수빈의 위치 - 1을 했을 때 이동가능 범위에 속하는가?
		if(a-1 >= 0 && a-1 < 100001 && !v[a-1]) {
			v[a-1] = 1;
			q.push({a-1, b+1});
		}
        // 수빈의 위치 * 2을 했을 때 이동가능 범위에 속하는가?
		if(a*2 >= 0 && a*2 < 100001 && !v[a*2]) {
			v[a*2] = 1;
			q.push({a*2, b+1});
		}
	}
}

[결과]

문제 링크 : https://www.acmicpc.net/problem/1620

[문제]

대충 포켓몬 스토리.... (길어서 생략)

[입력]

첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 물어봐도 괜찮아. 나는 언제든지 질문에 답해줄 준비가 되어있어.

둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어와. 포켓몬의 이름은 모두 영어로만 이루어져있고, 또, 음... 첫 글자만 대문자이고, 나머지 문자는 소문자로만 이루어져 있어. 아참! 일부 포켓몬은 마지막 문자만 대문자일 수도 있어. 포켓몬 이름의 최대 길이는 20, 최소 길이는 2야. 그 다음 줄부터 총 M개의 줄에 내가 맞춰야하는 문제가 입력으로 들어와. 문제가 알파벳으로만 들어오면 포켓몬 번호를 말해야 하고, 숫자로만 들어오면, 포켓몬 번호에 해당하는 문자를 출력해야해. 입력으로 들어오는 숫자는 반드시 1보다 크거나 같고, N보다 작거나 같고, 입력으로 들어오는 문자는 반드시 도감에 있는 포켓몬의 이름만 주어져. 그럼 화이팅!!!

[출력]

첫째 줄부터 차례대로 M개의 줄에 각각의 문제에 대한 답을 말해줬으면 좋겠어!!!. 입력으로 숫자가 들어왔다면 그 숫자에 해당하는 포켓몬의 이름을, 문자가 들어왔으면 그 포켓몬의 이름에 해당하는 번호를 출력하면 돼. 그럼 땡큐~

이게 오박사님이 나에게 새로 주시려고 하는 도감이야. 너무 가지고 싶다ㅠㅜ. 꼭 만점을 받아줬으면 좋겠어!! 파이팅!!!

[알고리즘 분류]

• 자료 구조
• 해시를 사용한 집합과 맵

[해설]

이 문제는 key를 통해 value를 검색하는 map 구조를 사용하면 쉽게 해결할 수 있다.

다만, 주의해야할 것은 도감번호를 입력했을 때는 포켓몬 이름을, 포켓몬 이름을 입력했을 때는 도감번호를 출력한다는 조건이다.

해당 조건에 부합하는 로직을 구성하기 위해서는 map에 도감번호(key) = 포켓몬 이름(value) / 포켓몬 이름(value) = 도감번호(key) 의 형식으로 반복문의 한 루프에서 총 두 번의 삽입을 수행해야 한다.

추가적으로, 나중에 도감번호를 이용해 포켓몬 이름을, 포켓몬 이름을 통해 도감번호를 찾아야하므로 이 두 과정을 조건문으로 나누지 않고 단순화하기 위해 도감번호를 int형이 아닌, to_string() 메서드를 이용해 string형으로 바꾸어 key와 value로 삽입한다.

그리고 이를 로직으로 구성하면 다음과 같이 나타낼 수 있다.

[정답 코드]

#include<bits/stdc++.h>
using namespace std;
// 포켓몬 도감 map 선언
map<string,string> P;

int N,M;
// 반복문에서 이름과 도감번호를 담을 변수 pokemon을 선언
string pokemon;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> N >> M;
	for(int i=1;i<=N;i++) {
    	// 포켓몬의 이름을 입력받아
		cin >> pokemon;
        // 후반부의 출력부에서의 과정을 단순화 하기 위해
        // 각각 "P[도감번호] = 포켓몬 이름", "P[포켓몬 이름] = 도감번호" 로 삽입한다.
		P[to_string(i)] = pokemon;
		P[pokemon] = to_string(i);
	}

	while(M--) {
    	// 도감번호와 포켓몬 이름 모두 string형 이므로 그냥 입력받아 map에서 찾으면 된다
		cin >> pokemon;
		cout << P[pokemon] << '\n';
	}
}

[결과]