[ 자바 ] - 사탕게임, 빗물

 

특별한 알고리즘이 들어갔다기 보다는 문제를 잘 이해하고 코드로 잘 구현하면 되는 문제였다.

일단 문제도 이해하기 힘들었고, 설마 그많은 경우를 다 검사해봐야 하는 생각에 자꾸 다른방법을 찾다가. 그냥 경우에수를 모두 찾아보자고 생각을 바꿔 진행하였다. 

 

 

문제의 요점은 가로 세로 바둑판에  바로옆이나 아래 글자가 다른 글자이면 서로 위치를 교환하고 그때 반복해서 문자가 많이 오는 횟수를 찾으라는것이다.

 

EX) 

AAB

BBC

CCD

 

[0,0] 은 [0,1]과는 바꾸지못하고 , [1,0]과는 교환할수있다. 교환 했을때 AAA,BBB,CCC와같이 연속한 문자가 가장 많이 올때 몇번 오는가 이다.

결국 [1,2]와 [2,2]를 교환했을떄 [2,0][2,1][2,2] 가 CCC임으로 여기서 가장 높은 점수는 3점이된다 .

 

그래서 일단 교환을 했다가 다시 복구할수있는 SWAP 매소드를 만들었고 교환한 상태에서 가로 세로 모든경우의 문자를 string으로 만들어 검사를 check 메소드를만들었다. 

 

마지막으로 매 문자마다 옆과 아래 문자와 교환을 시켰다.  옆에 문자가 같더라도 교환을 시킨후 check에서 카운팅하지않음 .

 

 

https://www.acmicpc.net/problem/3085

3085번: 사탕 게임

 

 

import java.util.*;

public class Main {

public static void main(String[] args) { 
Scanner sc = new Scanner(System.in);

String a = sc.nextLine();
int b=  Integer.parseInt(a);

String[][] arr = new String[b][b];
for(int i=0;i<b;i++) {
String c = sc.nextLine();
for(int j = 0 ; j < c.length();j++) {
arr[i][j]=c.charAt(j)+"";
}
}
int max = 0;
int count = 0;
//옆에숫자가 다른경우 교환
for(int i=0;i<b;i++) {
for(int j =0;j<b;j++) {
if(j<b-1) {
swap(arr,i,j,i,j+1);
count= check(arr,b);
if(count>max) max=count;
swap(arr,i,j,i,j+1);
}
}
for(int j =0;j<b;j++) {
if(j<b-1) {
swap(arr,j,i,j+1,i);
count=check(arr,b);
if(count>max) max=count;
swap(arr,j,i,j+1,i);
}
}
}
System.out.println(max);

}

static void swap(String[][] arr,int t1,int t2,int d1,int d2) {
String tmp = arr[t1][t2];
arr[t1][t2]=arr[d1][d2];
arr[d1][d2]=tmp;
}


static int check(String[][] arr,int b) {
int max=0;
int count=1;
for(int i = 0 ; i <b;i++) {
String v ="";
for(int j=0;j<b;j++) {
String v1=arr[i][j];
if(v.contentEquals(v1)) {
count++;
if(count>max) max=count;
}else {

v=v1;
count=1;
}

}


String h ="";
for(int j=0;j<b;j++) {
String h1=arr[j][i];
if(h.contentEquals(h1)) {
count++;
if(count>max) max=count;
}else {
h=h1;
count=1;
}

}
}
return max;
}

}

 

 

 

 

 

빗물 - 여태까지 푼문제중에 가장 빨리 풀었다..

 

문제의 포인트는 벽과 벽사이에 물이고인다는 것이다. 벽이 한쪽만 있으면 물 안고임

그래서 각 줄을 분리하여 문제를 풀었다. 별다른 알고리즘은 사용하지않고 풀수 있는 문제다.

 

 

https://www.acmicpc.net/problem/14719

14719번: 빗물

 

 

 

import java.util.*;

public class Main {

public static void main(String[] args) { 
Scanner sc = new Scanner(System.in);
String s = sc.nextLine(); //input1 
String s1 = sc.nextLine(); //input2

int h = Integer.parseInt(s.split(" ")[0]);  // h
int w = Integer.parseInt(s.split(" ")[1]);  // w 

int[] arr = new int[w]; //input2 를 담을 배열 

for(int i=0;i<w;i++) {   //배열에 나눠 담음 
arr[i]=Integer.parseInt(s1.split(" ")[i]);
}


int total=0;  // 빗물 담을 공간 


for(int i = 0; i<h;i++) {    //각각의 줄 
boolean[] d = new boolean[w]; //각 줄의 빗물을 구문할 boolean 배열

for(int j = 0;j<w;j++) { // 각 줄의 숫자가 1이상이면 true / 0이면 false 로 배열에 담음 
if(arr[j]>0) {
arr[j]-=1;
d[j]=true;
}
}


boolean bool =false;        //벽이 닫혔는지 열렸는지 구분 
int start=-1; //시작점 -1 ,  벽이 닫히지않은 상태면 체크하지않게하기위함 

for(int j =0;j<d.length;j++) { //각 boolean값을꺼낸다.
if(d[j]) {   //벽이 있고 
if(bool) {  //이미 닫혀 있으면 , 이전벽과 현재 벽사이를 카운트
total+=j-start-1;
start=j;
}else {    // 벽이 아직 닫히지않으면 벽을 닫고 j를 start로 변경 
bool =true;
start=j;
}
}
}

}
System.out.println(total);
}
}