구현 능력을 보여주는데 적합하기 때문에 많은 코딩테스트에서 사용되는 단골 문제이기 때문에 꼭 연습하시길 추천 드립니다.
정말 다양한 방법이 있습니다. 우선 탐색을 통해서 값을 얻어야 하는데 dfs, bfs 모두 상관없습니다. (여기서는 dfs가 코드가 짧고 가독성이 좋습니다.)
알고리즘은
1. 탐색을 통해서 없애야 하는 인덱스들을 표시한다.
2. 없애야 하는 인덱스들을 없애고, 빈 칸들을 채워넣는다.
3. 없애야 하는 인덱스가 없을때 까지 반복한다.
주의 하실점은 연쇄로 터지는 것을 한번의 과정으로 본다는 것입니다.
저는 vector를 사용하였고, dfs 두가지를 이용해서 구현하였습니다.
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
string val[12];
vector <char> arr[6];
int result = 0;
int x_ar[4] = { 1,-1,0,0 };
int y_ar[4] = { 0,0,1,-1 };
int visited[6][12] = { 0 };
void dfs2(char a, int yy, int xx,int cnt) {
int sum = cnt;
for (int i = 0; i < 4; i++) {
int y = yy + y_ar[i];
int x = xx + x_ar[i];
if (y >= 0 && y < 6 && x >= 0 && x < 12 && arr[y][x] == arr[yy][xx] && visited[y][x] == 0) {
sum++;
visited[y][x] = sum;
dfs2(a, y, x,sum );
}
}
}
void dfs(char a,int yy,int xx) {
arr[yy][xx] = '8';
visited[yy][xx] = -1;
for (int i = 0; i < 4; i++) {
int y = yy + y_ar[i];
int x = xx + x_ar[i];
if (y >= 0 && y < 6 && x >= 0 && x < 12 && arr[y][x] == a && visited[y][x] != -1) {
dfs(a, y, x);
}
}
}
bool solve() {
bool jud = false;
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 12; j++) {
if (arr[i][j] != '.' ) {
memset(visited, 0, sizeof(visited));
visited[i][j] = 1;
dfs2(arr[i][j], i, j, 1);
for (int u = 0; u < 6; u++)
for (int m = 0; m < 12; m++)
if (visited[u][m] >= 4) {
char word = arr[u][m];
dfs(word, u, m);
}
}
}
}
for (int i = 0; i < 6; i++)
for (int j = 0; j< arr[i].size(); j++)
if (arr[i][j] == '8') {
jud = true;
arr[i].erase(arr[i].begin() + j), j--;
}
for (int i = 0; i<6; i++)
if (arr[i].size() < 12) {
while (arr[i].size() != 12)
arr[i].push_back('.');
}
return jud;
}
int main() {
for (int i = 0; i < 12; i++) {
cin >> val[i];
}
for (int i = 0; i < 6; i++)
for (int j = 11; j >= 0; j--)
arr[i].push_back(val[j][i]);
while (1) {
bool jud = false;
jud = solve();
if (jud == false)
break;
result++;
}
cout << result << '\n';
}
벡터를 사용하기 위해 입력받은 문자열을 90도 회전해서 벡터에 넣었습니다.
dfs2를 호출해서 탐색하며 visited에 이동값들을 표시했습니다.
이후 dfs를 통해서 visited값이 4인 값과 연결되는 모든 arr값들을 '8'로 바꿔주었습니다.
그 이후 라운드별로 '8' 값들을 모두 지워주고 뒷부분을 '.' 로 채워주는 방식으로 구현했습니다.
m<= 10000 이기때문에 m을 입력받고 O(m*m)인 이중포문으로 구현하게 되면 O(100,000,000)으로 1억번 실행되기에 1초에 딱맞습니다. 그래서 시간초과가 날까 걱정했습니다.
#include <iostream>
using namespace std;
int n = 0, m = 0, result = 0;
bool visited[501] = { 0 };
int arr[10000][2] = { 0 };
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++)
cin >> arr[i][0] >> arr[i][1];
for (int i = 0; i < m; i++) {
if (arr[i][0] == 1) { //상근이의 친구
int val = arr[i][1];
visited[val] = 1; //체크
for (int j = 0; j < m; j++) {// 상근이 친구의 친구들도 체크
if (arr[j][0] == val)
visited[arr[j][1]] = 1;
else if (arr[j][1] == val)
visited[arr[j][0]] = 1;
}
}
}
for (int i = 1; i <= n; i++)
if (visited[i] == 1) {
result++;
}
cout << result - 1 << endl;
}
다행히 ac를 받았습니다.
시간도 얼마걸리지 않았습니다. ( 아마 테스트케이스에 극단값이 없을 수 있기 때문에 )
구현문제는 항상 좀더 컴팩트한 답을 생각하셔야 합니다.
#include <cstdio>
int main(){
int n,m,a,b,ans=0;
short int arr[501][501]={0,};
scanf("%d%d",&n,&m);
for(int i =0 ; i<m; i++)
scanf("%d%d",&a,&b),arr[a][b] = 1,arr[b][a] = 1;
for(int i=2; i<=n; i++){
if(arr[1][i] ==1){
ans++;
}
else{
for(int j = 1; j<=n; j++){
if(arr[i][j] == 1 && arr[j][1] == 1){
ans++;break;
}}}}
printf("%d\n",ans);
}
구현문제입니다. 단순히 반복되는 값들에서 100에 가까운 만큼 더해주면 되는 쉬운문제였습니다.
별다른 설명없이 정답코드입니다.
#include <iostream>
#include <cmath>
using namespace std;
int arr[10] = { 0 };
int sum = 0;
int main() {
for (int i = 0; i < 10; i++)
cin >> arr[i];
for (int i = 0; i < 10; i++) {
if (abs(100 - sum) >= abs(100 - (sum + arr[i])))
sum += arr[i];
else
break;
}
cout << sum << endl;
}
#include <iostream>
#include <algorithm>
using namespace std;
struct country {
int country_number;
int gold;
int sliver;
int bronze;
};
bool cmp(country a, country b) {
if (a.gold > b.gold) return true;
else if (a.gold == b.gold) {
if (a.sliver > b.sliver) return true;
if (a.sliver == b.sliver) {
if (a.bronze > b.bronze) return true;
}
}
return false;
}
country arr[1001];
int n, k;
int n1, n2, n3, n4;
int result = 0,val=0;
int main() {
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> n1 >> n2 >> n3 >> n4;
arr[i].country_number = n1;
arr[i].gold = n2;
arr[i].sliver = n3;
arr[i].bronze = n4;
}
sort(arr, arr + n, cmp);
for (int i = 0; i < n; i++) {
if (arr[i].country_number == k) {
result = i;
break;
}
}
for (int i = result - 1;; i--) {
if (arr[i].gold != arr[result].gold || arr[i].sliver != arr[result].sliver || arr[i].bronze != arr[result].bronze) {
break;
}
val++;
}
cout << result - val + 1 << endl;
}
#include <iostream>
using namespace std;
int n = 0, result = 0;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
if (i <= 9)
result += 1;
else if (i <= 99)
result += 2;
else if (i <= 999)
result += 3;
else if (i <= 9999)
result += 4;
else if (i <= 99999)
result += 5;
else if (i <= 999999)
result += 6;
else if (i <= 9999999)
result += 7;
else if (i <= 99999999)
result += 8;
else
result += 9;
}
cout << result << endl;
}
네 당연히 ac입니다.
하지만 조금 더 효율적인 코드를 찾아봤습니다.
#include<cstdio>
int n, r;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i *= 10)
r += n - i + 1;
printf("%d", r);
return 0;
}
크으 ... 아름다운 코드...
위 코드의 핵심은 매번 반복문마다 1의자리수의 합을 더해주고, 다음 반복문에서는 2의 자리수의 합을 더해준다는 개념입니다.
대략 120정도의 값을 대입해보시면 이해가 가실겁니다.
이렇게 구현문제는 풀어보는 것이 끝이 아니라 다른사람의 효율적인 코드를 보는게 더욱 도움이 된다고 생각합니다.
