2회 문제풀이 10 / ABC 137 C - Green Bin
ABC 137 C - Green Bin
【문제 개요】
문자열 a에 포함된 문자를 랜덤한 순서로 정렬하여 얻은 문자열 a의 _애너그램_이라고 합니다.
예를 들어, greenbin는 beginner의 애너그램입니다. 이와 같이, 같은 문자가 여러개 있는 경우 그 문자는 그 횟수만큼 사용해야 합니다.
N개의 문자열 s1, s2, …, sN가 주어집니다. 각각 문자열은 길이가 10인 영소문자로 구성됩니다.
또한 이 문자열들은 전부 다릅니다. 두개의 정수 i, j(1 ≦ i ≦ j ≦ N)의 조합일때 si가 sj의 애너그램인 갯수를 구하시오.
힌트 : 이진 탐색 알고리즘
【전제】
- 2 ≦ N ≦ 10^5
- si은 길이 10의 문자열이다.
- si의 문자열은 영소문자로 구성되어있다.
- s1, s2, …, sN은 모두 다르다.
【입력 형태】
1
2
3
4
5
N
s1
s2
...
sN
【출력 형태】
두개의 정수 i, j(1 ≦ i ≦ j ≦ N)일때 si가 sj의 애너그램인 갯수를 출력하시오.
【예시】
입력 예 1
1
2
3
4
3
acornistnt
peanutbomb
constraint
출력 예 1
1
1
s1 = acornistnt는 s3 = constraint의 애너그램이다. 그 외에 si가 sj의 애너그램인 경우의 조합은 없기때문에 답은 1이다.
입력 예 2
1
2
3
2
oneplustwo
ninemodsix
출력 예 2
1
0
si가 sj의 애너그램 인 i,j의 조합은 없기때문에 0이 출력됩니다.
입력 예 3
1
2
3
4
5
6
5
abaaaaaaaa
oneplustwo
aaaaaaaaba
twoplusone
aaaabaaaaa
출력 예 3
1
4
- s1 =
abaaaaaaaa는 s3 =aaaaaaaaba과 s5 =aaaabaaaaa의 애너그램이다. (1, 3) (1, 5) - s2 =
oneplustwo는 s4 =twoplusone의 애너그램이다. (2, 4) - s3 =
aaaaaaaaba는 s5 =aaaabaaaaa의 애너그램이다. (3, 5) 조건을 만족하는 값은 이 4종류이기 때문에 출력은 4이다.
ABC 137 C - Green Bin
【문제 개요】
문자열 a에 포함된 문자를 랜덤한 순서로 정렬하여 얻은 문자열 a의 _애너그램_이라고 합니다.
예를 들어, greenbin는 beginner의 애너그램입니다. 이와 같이, 같은 문자가 여러개 있는 경우 그 문자는 그 횟수만큼 사용해야 합니다.
N개의 문자열 s1, s2, …, sN가 주어집니다. 각각 문자열은 길이가 10인 영소문자로 구성됩니다.
또한 이 문자열들은 전부 다릅니다. 두개의 정수 i, j(1 ≦ i ≦ j ≦ N)의 조합일때 si가 sj의 애너그램인 갯수를 구하시오.
힌트 : 이진 탐색 알고리즘
【전제】
- 2 ≦ N ≦ 10^5
- si은 길이 10의 문자열이다.
- si의 문자열은 영소문자로 구성되어있다.
- s1, s2, …, sN은 모두 다르다.
【입력 형태】
1
2
3
4
5
N
s1
s2
...
sN
【출력 형태】
두개의 정수 i, j(1 ≦ i ≦ j ≦ N)일때 si가 sj의 애너그램인 갯수를 출력하시오.
【예시】
입력 예 1
1
2
3
4
3
acornistnt
peanutbomb
constraint
출력 예 1
1
1
s1 = acornistnt는 s3 = constraint의 애너그램이다. 그 외에 si가 sj의 애너그램인 경우의 조합은 없기때문에 답은 1이다.
입력 예 2
1
2
3
2
oneplustwo
ninemodsix
출력 예 2
1
0
si가 sj의 애너그램 인 i,j의 조합은 없기때문에 0이 출력됩니다.
입력 예 3
1
2
3
4
5
6
5
abaaaaaaaa
oneplustwo
aaaaaaaaba
twoplusone
aaaabaaaaa
출력 예 3
1
4
- s1 =
abaaaaaaaa는 s3 =aaaaaaaaba과 s5 =aaaabaaaaa의 애너그램이다. (1, 3) (1, 5) - s2 =
oneplustwo는 s4 =twoplusone의 애너그램이다. (2, 4) - s3 =
aaaaaaaaba는 s5 =aaaabaaaaa의 애너그램이다. (3, 5) 조건을 만족하는 값은 이 4종류이기 때문에 출력은 4이다.