A Sign of Inequality - Back Tracking

문제 조건에 맞지 않거나 계속 재귀호출해도 정답이 나오지 않을 경우 계속 재귀를 실행하는 것을 멈추는 것을 백트랙킹(Back Tracking)이라고 한다.

앞에서 풀어본 부등호(A Sign of Inequality) 문제를 백트래킹을 이용하여 시간을 훨씬 줄일 수 있다. 그 방법은 불가능한 경우를 처리해주는 것이다.

이 문제에서 불가능한 경우란, 조건을 체크해서 조건을 만족하지 않는 경우는 처리하지 않도록 하는 것이다. 앞에서는 다음 경우를 호출할 때 조건 체크하지 않고 index==n+1이 되야만 조건을 체크해주었는데, 백트랙킹방식에서는 현재에서 숫자를 추가할 때마다 조건을 체크해준다!

부등호가 담긴 배열 : input[ ] = {<,<} 현재의 인덱스 : index 현재 넣을 수 : i

=> s.charAt(index-1)과 i를 비교한다!이 때 비교하는 부등호는 input(index-1)이 된다! 조건 검사하는 함수를 수도코드로 다시 구현해보면 다음과 같다. boolean ok(a,b,op) { if(op == '<') { if(a>b) return false;} if(op == '>') { if(a<b) return false;} return true; }

하지만 현재 s.charAt(index-1)은 char 타입이고, i는 int 타입이다. 두개의 자료형이 다르기 때문에 char 타입으로 통일해준다.=> (char)i+'0'

• 소스 코드 구현 1) 조건 체크 함수

static boolean bt_ok(char a,char b,char op) {
		 if(op == '<') { if(a>b) return false;}
		 if(op == '>') { if(a<b) return false;}
		return true;
	}

2) 백트랙킹 : 현재 index에 수 i를 넣을 때마다 조건 체크

for(int i=0;i<=9;i++) {
			if(check[i]) continue;
			//백트랙킹=>현재 수 넣을 때 조건체크를하면서 넣는다!
			if(index == 0||bt_ok(s.charAt(index-1),(char)(i+'0'),input[index-1])) {
				check[i] = true;
				go(index+1,s+Integer.toString(i));
				check[i] = false;
			}
		}

• 결과 확인 : 백트랙킹 솔루션이 약 3배 정도 더 빠른 것을 확인할 수 있다.

3배 빠른 백트랙킹