1. 커플
처음에는 옛날에 푼 괄호찾기 같이 스택을 이용하여 커플을 배제하고 남은 사람들을 더했는데
timout이 발생하여 좀 더 생각해보니 굳이 찾아주지 않고 전부 더하면 결국 짝끼리는 더해져서 0이되고 남은 사람들의 값이 나옴을 알게되어 배열에 넣고 전부 더하여 결과를 냈다.
(함수형식으로 풀지 않았으면 그냥 받는 부분에서 다 더하고 결과를 도출하여도 된다.)
2. 폴더폰
구현 문제로 우선 공백없이 입력을 받기 위해 string을 사용하였고 string s에 받은 숫자들과
해당 숫자들이 입력된 횟수를 받기 위해 queue자료 구조안에 pair형태로 쌓았습니다.
int prev = s[0] - 48; int count = 0; for (int i = 0; i < n; i++) { int a = s[i] - 48; if (prev != a) { count_a.push({ prev,count }); count = 0; } count++; prev = a; } count_a.push({ prev,count });
이 때 숫자들을 나누기 위해 현재 입력된 수와 다른지를 prev를 통해 확인하였고 다르면 queue안에 숫자와 그 숫자가 입력된 횟수를 넣었습니다. 마지막에 나오는 수는 비교할 필요 없이 for문을 벗어나면 queue안에 넣어주면 됩니다.
위에 코드에서 마지막으로 나오는 수와 비교할 수가 없으면 queue안에 넣을 방법이 없다고 생각하여 처음에는 if문을 통해 넣어줬는데 그렇게 되면 2가지만 입력할시 즉, 1,0만 입력하면 잘못된 값이 나온다.
그 이후에는 넣어진 queue에 원소들을 하나씩 빼서 위에 만들어둔 char형에 배열인 phone에서 알맞은 문자들을 result값에 넣어주면 된다. 이때 횟수를 넘겨서 입력하면 다시 처음부터 숫자부터 입력되니 각 핸드폰 자판에 문자들의 수에 맞는 값을 나머지 연산으로 연산해줍니다.
3. 구름섬
옛날에 bfs 문제중 미로탐색과 비슷한 문제였다. 1부터 시작하여 마지막 섬까지 최단 거리로 가기 위해서는 몇개의 다리를 건너야하는지인데, 간단하게 너비탐색을 하면된다. 모든 경우의 수를 구할 필요없이 우리는 최단으로 해당 섬을 가는 다리의 갯수가 몇개인지만 알면되기 때문에 섬과 섬끼리 연결되어 있는 다리는 vector 배열 형태로 받고 처음에 1을 queue에 넣어서 1에서 갈 수 있는 모든 섬을 방문하고 visited을 통해 잠군다. 이 때 dist에는 1에서 해당 섬까지 가는 다리의 수를 저장시킨다. visited을 통해 잠군 이유는 1에서 뻗어나가고 다시 해당 노드를 방문할 필요가 없기 때문이다. 해당 노드를 방문해서 가야 될 경우면 애초에 최단거리가 되지 않기 때문이다.
이렇게 나온 dist 배열을 통해 마지막 섬에 거리를 확인한다.
이때 dist가 0이거나 목표한 최단 거리보다 작으면 NO를 아니면 YES를 출력합니다.
4. 물탱크
4. 물탱크
풀이
1. 커플
#include <iostream>
using namespace std;
void solve();
void solution();
int g[100005];
int N, result;
void solve()
{
for (int i = 0; i < N; i++)
result += g[i];
solution();
}
void solution()
{
cout << result;
}
int main()
{
cin.tie(0); cout.tie(0);
ios::sync_with_stdio(0);
cin >> N;
for (int i = 0; i < N; i++)
{
int a;
cin >> a;
g[i] = a;
}
solve();
}2. 폴더폰
#include<iostream>
#include<string>
#include<queue>
#include<utility>
using namespace std;
void solve();
void solution();
queue<pair<int, int>>count_a;
int n;
string s, result;
char phone[10][5] = {{}
,{'1','.',',','?','!'}
,{'2','A','B','C'}
,{'3','D','E','F'}
,{'4','G','H','I'}
,{'5','J','K','L'}
,{'6','M','N','O'}
,{'7','P','Q','R','S'}
,{'8','T','U','V'}
,{'9','W','X','Y','Z'} };
void solve()
{
while (!count_a.empty())
{
auto x = count_a.front(); count_a.pop();
if (x.first == 1 || x.first == 7 || x.first == 9)
{
result += phone[x.first][(x.second - 1) % 5];
}
else
{
result += phone[x.first][(x.second - 1) % 4];
}
}
solution();
}
void solution()
{
cout << result;
}
int main()
{
cin.tie(0); cout.tie(0);
ios::sync_with_stdio(0);
cin >> n;
cin >> s;
int prev = s[0] - 48;
int count = 0;
for (int i = 0; i < n; i++)
{
int a = s[i] - 48;
if (prev != a)
{
count_a.push({ prev,count });
count = 0;
}
count++;
prev = a;
}
count_a.push({ prev,count });
solve();
}3. 구름섬
#include<iostream>
#include<queue>
using namespace std;
void solve();
void solution();
int N, M, K;
int result = 0x3f3f3f3f;
bool visitied[1005];
int dist[1005];
vector<int>v[1005];
queue<int>q;
void solve()
{
while (!q.empty())
{
auto x = q.front(); q.pop();
for (int i = 0; i < v[x].size(); i++)
{
if (visitied[v[x][i]])continue;
visitied[v[x][i]] = true;
dist[v[x][i]] = dist[x] + 1;
q.push(v[x][i]);
}
}
solution();
}
void solution()
{
if (dist[N] > 0 && dist[N] <= K)cout << "YES";
else cout << "NO";
}
int main()
{
cin.tie(0); cout.tie(0);
ios::sync_with_stdio(0);
cin >> N >> M >> K;
for (int i = 0; i < M; i++)
{
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
q.push(1);
visitied[1] = true;
solve();
}4. 물탱크
