TopCoder 練習

InternetSecurity(SRM 480 Div1 Easy)

■問題
幾つかのサイトのURLとそのサイトに含まれるキーワードと，危険なサイトであることを表すキーワード群が与えられる．どのサイトが危険であるかを判定せよ．

■解法
危険キーワードをリストに取っておく．
n個のサイトについて以下を調べる．
あるサイトが危険キーワードを含む場合，そのサイトを「危険である」とし，そのサイトが含むキーワードを危険キーワードリストに追加．
「危険である」サイトが見つからなくなるまでループ．

view plainprint?

1. import java.lang.*;  
2. import java.util.*;  
3.   
4. public class InternetSecurity{  
5.  public String[] determineWebsite(String[] address, String[] keyword, String[] d, int threshold){  
6.   int n=address.length;  
7.   LinkedList<String> dangerous=new LinkedList<String>();  
8.   boolean[] flag=new boolean[n];  
9.   for(String s:d){  
10.    dangerous.add(s);  
11.   }  
12.   for(;;){  
13.    boolean f=false;  
14.    for(int i=0;i<n;i++){  
15.     if(flag[i]){  
16.      continue;  
17.     }  
18.     int c=0;  
19.     for(String s:keyword[i].split(" ")){  
20.      if(dangerous.contains(s)){  
21.       c++;  
22.      }  
23.     }  
24.     if(c>=threshold){  
25.      for(String s:keyword[i].split(" ")){  
26.       dangerous.add(s);  
27.      }  
28.      flag[i]=f=true;  
29.     }  
30.    }  
31.    if(!f){  
32.     break;  
33.    }  
34.   }  
35.   LinkedList<String> list=new LinkedList<String>();  
36.   for(int i=0;i<n;i++){  
37.    if(flag[i]){  
38.     list.addLast(address[i]);  
39.    }  
40.   }  
41.   
42.   return list.toArray(new String[0]);  
43.  }  
44. }  

import java.lang.*;
import java.util.*;

public class InternetSecurity{
 public String[] determineWebsite(String[] address, String[] keyword, String[] d, int threshold){
  int n=address.length;
  LinkedList<String> dangerous=new LinkedList<String>();
  boolean[] flag=new boolean[n];
  for(String s:d){
   dangerous.add(s);
  }
  for(;;){
   boolean f=false;
   for(int i=0;i<n;i++){
    if(flag[i]){
     continue;
    }
    int c=0;
    for(String s:keyword[i].split(" ")){
     if(dangerous.contains(s)){
      c++;
     }
    }
    if(c>=threshold){
     for(String s:keyword[i].split(" ")){
      dangerous.add(s);
     }
     flag[i]=f=true;
    }
   }
   if(!f){
    break;
   }
  }
  LinkedList<String> list=new LinkedList<String>();
  for(int i=0;i<n;i++){
   if(flag[i]){
    list.addLast(address[i]);
   }
  }

  return list.toArray(new String[0]);
 }
}