1620 나는야 포켓몬 마스터 이다솜
문제 링크
문제 출제자이신 백준님이 포켓몬을 정말 좋아하시는 것 같다.
이 문제의 경우 시간초과를 잘 통과해야하는 문제이고, 이를 해결하려면 두 개의 자료구조를 사용한다.
string:int 은 map, int:string 의 경우 array, map 모두 사용 가능하다.
#include<iostream>
#include<string>
#include<map>
using namespace std;
int n,m;
string s;
map<string, int> mp; // 포켓몬 이름(key) 으로 도감번호(value) 찾기
map<int, string> mp2; // 도감번호로 포켓몬 이름 찾기
string a[100004]; // 도감번호로 포켓몬 이름 찾기
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
for(int i=0; i<n; i++)
{
cin >> s;
mp[s]=i+1;
mp2[i+1]=s;
a[i+1]=s;
}
for(int i=0; i<m; i++)
{
cin >> s;
if(atoi(s.c_str())==0)
{
cout << mp[s] << '\n';
}
else
{
cout << a[atoi(s.c_str())] <<'\n';
// cout << mp2[atoi(s.c_str())] <<'\n';
}
}
}atoi
문자열을 int로 바꿔야 할 상황에서 쓰일 수 있다. 문자열이 문자라면 0을 반환하고 그게 아니라면 숫자를 반환하게 된다.
9375 패션왕 신해빈
문제 링크
경우의 수 문제이다.
#include<iostream>
#include<map>
#include<string>
using namespace std;
int t, n;
string a, b;
int main()
{
cin >> t;
while(t--)
{
map<string, int> _map;
cin >> n;
for(int i=0; i<n; i++)
{
cin >> a >> b;
_map[b]++; // 종류 증가
}
long long ret = 1; // 경우의 수라면 수가 커질 수 있어서 long long을 사용한다
for(auto c : _map)
{
ret *= ((long long)c.second + 1); // +1 은 종류마다 아무것도 안읽는 경우
}
ret--; // 모든 종류를 아무것도 안입는 경우
cout << ret << '\n';
}
return 0;
}1213 팰린드롬 만들기
문제 링크
팰린드롬에서 홀수가 두개면 안된다. AB AAABBB 처럼!
#include<iostream>
#include<string>
using namespace std;
string s, ret;
int cnt[200], flag;
char mid;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> s; // 임한수의 영어 이름
for (char a : s) cnt[a]++; // 문자가 몇개 있는지 확인하기 위해 카운팅(홀수가 2개이상이면 팰린드롬을 만들 수 없다)
for (int i='Z'; i>='A'; i--) // 오름차순을 해야해서 Z부터 붙였다
{
if (cnt[i]){
if (cnt[i] & 1) // 통과하면 홀수이다
{
mid = char(i); flag++;
cnt[i]--;
}
if (flag==2) break;
for (int j=0; j<cnt[i]; j+=2)
{
ret = char(i) + ret;
ret += char(i);
}
}
}
if (mid) ret.insert(ret.begin() + ret.size() / 2, mid);
if (flag==2) cout << "I'm Sorry Hansoo\n";
else cout << ret << '\n';
}1940 주몽
문제 링크
순서가 상관없는 조합의 경우가 된다. nC2
#include<iostream>
using namespace std;
int n, m, a[15001], cnt;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i=0; i<n; i++) cin >> a[i];
// 시간 초과를 고려해서 예외 처리
if (m > 200000) cout << 0 << '\n';
else
{
// combination
for(int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
if(a[i] + a[j] == m) cnt++;
}
}
cout << cnt << '\n';
}
}3986 좋은 단어
문제 링크
문제가 안풀린다면 뒤집거나 붙여보거나 90도 회전해보자.
이 경우 90도로 세워보니, 스택 자료구조를 활용할 수 있었다.
같으면 pop, 다르면 pop 하지 않는다.
앞으로 문제에서 만약에 짝짓기, 폭발 이라는 단어가 있다면 스택을 생각하면 좋을 것 같다.
#include<iostream>
#include<stack>
#include<string>
using namespace std;
int n, ret;
string s;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for(int i=0; i<n; i++)
{
cin >> s;
stack<char> stk; // 문자열 받을 때마다 빈 스택을 매번 정의해야 한다. 문자열 하나가 곧 하나의 테스트 케이스라서.
for(char a : s)
{
// 항상 size 를 꼭 체크한 후에 top,pop 을 사용해야 한다. 그래야 참조 에러가 발생하지 않는다.
if(stk.size() && stk.top() == a) stk.pop(); // 가장 위(마지막꺼)에 있는 거가 지금 들어오려하는 애랑 같다면 pop
else stk.push(a); // 다르면 들어간다
}
if(stk.size()==0) ret++;
}
cout << ret << '\n';
}1629 곱셈 🎯
문제 링크
A와 B는 최댓값이 약 20억이다. 최악의 경우 A^B 는 long long 으로도 담을 수 없고 overflow 가 생길 수 있기에 시간복잡도를 잘 생각해야 한다. 연산마다 % 연산을 해주겠다.
이 문제는 분할 정복/재귀함수을 이용한 거듭제곱이라는 유명한 풀이법을 사용할 수 있는 문제이다. logN의 시간복잡도를 가질 수 있다.
#include<iostream>
using namespace std;
typedef long long ll;
ll a, b, c;
ll go (ll a, ll b)
{
// 재귀함수는 일단 기저사례가 만들어져야 한다.
if (b == 1) return a % c;
ll ret = go(a, b / 2);
ret = (ret * ret) % c;
if(b % 2) ret = (ret * a) % c; // 홀수라면 한 번 더 곱한다 C++에서는 0 이외의 값이 true, 0만 false
return ret;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> a >> b >> c;
cout << go(a,b) << '\n';
return 0;
}