Topcoder-SRM689 div2 500

Problem Statement

     You are given two Strings: A and B. Each character in A is either '0' or '1'. Each character in B is '0', '1', or '?'.


A string C matches B if we can change B into C by changing each '?' in B either to '0' or to '1'. Different occurrences of '?' may be changed to different digits. For example, C = "0101" matches B = "01??". Note that each character in C must be either '0' or '1', there cannot be any '?' remaining.


Consider all possible strings that match B. How many of these strings occur as a (contiguous) substring in A? Compute and return their number. Note that we only count each good string once, even if it has multiple occurrences in A

접근 방법:

(수도코드)
일단 A의 길이와 B의 길이보다 무조건 커야한다.
A의 문자열을 정수형으로 변환시킨다. 그리고 1비트씩 왼쪽으로 쉬프트 시켜
(A의정수형<<i) B.length()만큼 잘라 낸 것을 Set자료구조에 집어넣는다(Set을 선택 한 이유는 중복이 불가능하기 때문이다. 
그리고 결과적으로 Set의 사이즈가 우리가 구하고자 하는 값의 갯수가 되는 것이다.

문자열 A를 잘라낸 것과 B의 문자열이 일치하면 그 값을 Set에 추가한다.
물론  문자열 B에서 ?가 아닌 부분은 잘라낸 문자열A와 무조건 일치해야 한다.

*****주의사항****
Integer.parseInt(number)를 사용하여 문자열을 숫자로 변경 할 때, number가 10001이었는데 이는 10진수 이다. 그러므로 Integer.parseInt(number,2)로 해야 한다.
또한, 000000문자열을 정수로 변환시 00000을 유지하는게 아니라 0으로 바뀌어버린다. 이를 유지시킬 필요가 있다.

A.length()-B.length()+1까지 for문을 탐색한다. 여기서 A의 길이에서 B의 길이를 빼고 for문이 < 이기 때문에 +1을 시켜주어야한다. 결과적으로 다음과 같다
for(int i=0;i<A.length()-B.length()+1;i++)

<Java Code>

public static long ways(String A,String B) throws UnsupportedEncodingException
{
if(B.length()>A.length())
return 0;

   
Set<String> set=new HashSet<String>();
String plus="";
for(int i=0;i<A.length()-B.length()+1;i++){
boolean check=true;
plus=A.substring(i, B.length()+i);
if(plus.length()!=B.length())
continue;

for(int j=0;j<plus.length();j++){
if(B.charAt(j)!=plus.charAt(j) && B.charAt(j)!='?'){
check=false;
break;
}

}
System.out.println(plus);
if(check==true)
set.add(plus);
left_shift(A,1);
}

//System.out.println(set);

return set.size();

}
public final static void left_shift(String str,int size) throws UnsupportedEncodingException{

byte[] orgByte=null;
byte[] resultByte=new byte[str.length()];
orgByte=str.getBytes("ASCII");
String s="0";
byte []a=s.getBytes("ASCII");

int strlen=orgByte.length;
for(int i=1;i<strlen;i++){
resultByte[(i-size)%strlen]=orgByte[i];
if(i==strlen-1){
resultByte[i]=a[0];
}
}

String result=null;
result=new String(resultByte);
System.out.println(result);
}

댓글

이 블로그의 인기 게시물

(네트워크)폴링방식 vs 롱 폴링방식

(ElasticSearch) 결과에서 순서 정렬

(18장) WebSocekt과 STOMP를 사용하여 메시징하기