[BOJ/백준] 20047 동전 옮기기 - 자바

문제

 

문제풀이

입력받은 S 배열에서 두 동전을 제외한 배열을 새로 만들고 선택받은 두 동전은 또 따로 temp 배열로 만들어서 T 배열과 비교할 때 사용했다. find 함수를 이용해서 조건에 따라 재귀적으로 풀었다.

 

find 함수

 1. s 배열 index 값 + 두 동전 사용 횟수 == n-1이면 탐색 완료, 1을 return

 2. index가 n-2인 경우 -> T로 만들 수 없다. 0을 return (ex) oxo 에서 x,o를 뽑아서 oox를 만드는 경우)

 3. s[index] == t[index+cnt] 이면 index를 증가시켜서 다음 값을 비교한다. 

 4. 두 동전 사용 횟수가 2인 경우; 위에서 해당하는 경우가 없었기에 선택한 동전을 새로 넣어 변화를 주어야 하는데 그      럴 수 없으므로 0 return

 5. temp[cnt] == t[index+cnt] 이면 선택한 동전을 해당 위치에 사용. cnt 증가. s배열과 비교한 것이 아니기에 index 값      은 증가 하지 않는다. 

 

 

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
	static int n;
	static char s[],t[],temp[];
	public static int find(int index, int cnt) {
		if (index+cnt==n-1) {//s탐색 완료+temp사용 완료
			return 1;
		}
		if(index==n-2) return 0;
		if(s[index]==t[index+cnt]) { //같으면 다음 순서
			if(find(index+1,cnt)==1) return 1;
		}
		if(cnt==2)return 0; //배열 다를 때 temp 다 쓴 경우
		
		if(temp[cnt]==t[index+cnt]) {//안맞는 부분이랑 temp부분이랑 같은지
			if(find(index,cnt+1)==1) return 1; //같으면 temp 하나 사용
		}
		return 0;
	}
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		n=Integer.parseInt(bf.readLine());
		s=bf.readLine().toCharArray();
		t=bf.readLine().toCharArray();
		int a,b;
		StringTokenizer st=new StringTokenizer(bf.readLine());
		a=Integer.parseInt(st.nextToken());
		b=Integer.parseInt(st.nextToken());
		temp= new char[2];
		temp[0]=s[a];
		temp[1]=s[b];
		int t=0;
		for(int i=0;i<n;i++) {
			if(i==a||i==b)continue;
			s[t]=s[i];
			t++;
		}
		int result=find(0,0);
		if(result==1){
			System.out.print("YES");
		}
		else {
			System.out.print("NO");
		}
		
	}

}

 

기타

dp 문제인 것 같았는데 어떻게 해야할 지 몰라서 recursive하게 풀었다.

파이썬이었으면 시간초과 났을 것 같은데 다행이댜 아직 자바가 익숙하지 않아서 코드 짜는 데 오래걸렸음 ㅜㅜ

내가 고려하지 못했던 예외적인 상황들이 있어서 코드 제출하면서 반례 찾고 , 조건 추가하면서 짰더니 깔끔하지는 않은 느낌 아쉽따