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);
 }
}

'ACM > hackkerrank' 카테고리의 다른 글

[HackkerRank] Sherlock and Anagrams  (0) 2018.10.12
[HackerRank] Minimum Swap2  (0) 2018.10.11
[HackerRank] New Year Chaos  (0) 2018.10.11
[HackerRank] Sock Merchant  (0) 2018.10.11
[HackerRank] Encryption  (0) 2018.08.14
[HackerRank] Organizing Containers of Balls  (0) 2018.07.12
Posted by 무대포개발자
0 Comments

1. Problem

2. Feedback

  • array 가 연속적인 것이 아님. 문제 잘못된듯
  • brute force 로 풀면 앞에서부터 마지막까지 비교해서 정렬시킴. 복잡도 - O(n2))
  • 최적화 작업
    • 메모리를 이용해서 값이 같으면, count 하고, swap 시킴. 이 방법은 모든 값을 비교하지 않고, 가지치기 하기에 그나마 비교횟수가 떨어짐.

3. Source

public class MinimumSwaps2
{
 public static void main(String [] args)
 {
  Scanner in = new Scanner(System.in);
  int n = in.nextInt();
  int arr[] = new int [n];
  for (int i = 0; i < n; i++)
   arr[i] = in.nextInt();
  System.out.println(solve(arr));
 }

 public static int solve(int arr[])
 {
  int arrLength = arr.length;
  int swapCount = 0;
  int copyArr[] = arr.clone();
  Arrays.sort(copyArr);
  for (int i = 0 ; i < arrLength ; i++)
  {
   if (arr[i] != copyArr[i])
   {
    swapCount++;
    for (int j = i + 1 ; j < arrLength ; j++)
    {
     if (arr[j] == copyArr[i])
     {
      int temp = arr[j];
      arr[j] = arr[i];
      arr[i] = temp;
      break;
     }
    }
   }
  }
  return swapCount;
 }
}

'ACM > hackkerrank' 카테고리의 다른 글

[HackkerRank] Sherlock and Anagrams  (0) 2018.10.12
[HackerRank] Minimum Swap2  (0) 2018.10.11
[HackerRank] New Year Chaos  (0) 2018.10.11
[HackerRank] Sock Merchant  (0) 2018.10.11
[HackerRank] Encryption  (0) 2018.08.14
[HackerRank] Organizing Containers of Balls  (0) 2018.07.12
Posted by 무대포개발자
0 Comments

1. Problem

2. Feedback

  • 못풀음. 힌트 보고 풀음.
  • 규칙
    • bribe 는 한 사람이 최대 2번 까지 가능
    • 앞에 있는 얘는 뒤에 있는 얘한테 bribe 를 못 줌.
  • Brute force 로 풀어볼려는데, Swap 해서 규칙을 찾아서 프로그래밍화 하는 방법을 못찾음.
  • 입력 받은 상태를 초기 상태로 변환하는 방법으로 풀음.
  • 최대 2번 바꿀 수 있으며, 초기상태는 오름차순이기에, 끝에서부터 최대 index 2 이내의 값이, 앞의 값이 뒤에 값보다 작다. 또한, 앞의 값이 뒤에 값보다 크다는 것은 swap 한다는 의미이며, ans++ 를 해준다.
  • 여기서 내가 잘못 생각한 것은 최소 값을 구하라는 것에서 여러 조합이 나올 수 있다 생각한 것. 여러 조합이 나올 수 없음. 2번 이내로 변경해야하니.
  • 이런 문제를 풀 때, 반드시 for 문을 통해 어떻게 규칙화할 것인지 생각해야 함.

3. Source

public static void main(String [] args)
 {
  Scanner in = new Scanner(System.in);
  int t = in.nextInt();
  
  for (int i = 0 ; i < t ; i++)
  {
   int n = in.nextInt();
   int arr[] = new int[n];
   for (int j = 0 ; j < n ; j++)
   {
    arr[j] = in.nextInt();
   }
   int ans = solve(arr);
   if (ans == 0)
    System.out.println("Too chaotic");
   else
    System.out.println(ans);
  }
 }
 
 public static int solve(int arr[])
 {
  int ans = 0;
  for (int i = arr.length - 1 ; i >= 0 ; i--)
  {
   if (arr[i] - (i + 1) > 2)
   {
    return 0;
   }
   for (int j = Math.max(0, arr[i] - 2) ; j < i ; j++)
   {
    if (arr[j] > arr[i]) ans++;
   }
  }
  return ans;
 }

'ACM > hackkerrank' 카테고리의 다른 글

[HackkerRank] Sherlock and Anagrams  (0) 2018.10.12
[HackerRank] Minimum Swap2  (0) 2018.10.11
[HackerRank] New Year Chaos  (0) 2018.10.11
[HackerRank] Sock Merchant  (0) 2018.10.11
[HackerRank] Encryption  (0) 2018.08.14
[HackerRank] Organizing Containers of Balls  (0) 2018.07.12
Posted by 무대포개발자
0 Comments