본문 바로가기
algorithm/hackerRank

[HackkerRank] Sherlock and Anagrams

by 무대포 개발자 2018. 10. 12.
728x90
반응형

2. Feedback

  • Brute force 로 풀었는데, O(n3) 이 나와서 최적화 하는데 시간 엄청 잡아먹음.
  • 문제 Constaint 에 1<n<100 이라고 되있어서, 최대 100의 3승을 체크못해서 시간을 많이 잡아먹음.
  • Brute force 로 풀었으며, 로직 플로우는 아래와 같다.
    • String 의 부분집합 사이즈를 for 문 돌림 (1,2,3,… n-1 / 부분집합 사이즈 별로 뽑아내서 비교하기 위해)
    • 뽑아낸 부분집합을 Set 에 집어넣고, 다른 부분집합 들을 set 에 넣어 비교 함.
    • 부분집합의 처음부터 마지막 - 1 까지 for 문을 돌린다. (모든 부분집합의 비교를 위해)

3. Source

public class SherlockAndAnagrams
{
 public static void main(String [] args)
 {
  Scanner in = new Scanner(System.in);
  int n = in.nextInt();
  String strArr[] = new String[n];
  for (int i = 0 ; i < n ; i++)
  {
   strArr[i] = in.next();
   System.out.println(solve(strArr[i]));
  }
 }
 
 private static int solve(String str)
 {
  Set<String> set;
  int sum = 0;
  
  // 끝까지 체크할 필요가 없기에, str.length
  int strLen = str.length();
  for (int i = 1 ; i <= strLen - 1 ; i++)
  {
   // j 는 단어의 시작부분을 의미
   for (int j = 0 ; j < strLen - i ; j++)
   {
    // set 을 사용한 이유는 비교를 쉽게 하기 위해
    set = new HashSet<String>();
    int sIdx = j;
    
    // 초기 String 을 set 에 넣는다.
    set.add(extractString(str, sIdx, sIdx + i));
    sIdx++;
    while (sIdx + i <= strLen)
    {
     if (set.contains(extractString(str, sIdx, sIdx + i)))
      sum++;
     sIdx++;
    }
   }
  }
  return sum; 
 }
 
 private static String extractString(String str, int to, int from)
 {
  String tmp = str.substring(to, from);
  char ch[] = tmp.toCharArray();
  Arrays.sort(ch);
  return new String(ch);
 }
}

'algorithm > hackerRank' 카테고리의 다른 글

[HackerRank] Encryption  (0) 2020.07.10
[HackerRank] Climbing the Leaderboard  (0) 2020.07.10
[HackerRank] Minimum Swap2  (0) 2018.10.11
[HackerRank] New Year Chaos  (0) 2018.10.11
[HackerRank] Sock Merchant  (0) 2018.10.11

댓글