728x90
반응형
1. Link to the problem
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 |
댓글