https://www.acmicpc.net/problem/1919
1919번: 애너그램 만들기
두 영어 단어가 철자의 순서를 뒤바꾸어 같아질 수 있을 때, 그러한 두 단어를 서로 애너그램 관계에 있다고 한다. 예를 들면 occurs 라는 영어 단어와 succor 는 서로 애너그램 관계에 있는데, occurs
www.acmicpc.net
Sol 1)
문제 조건을 보면 소문자가 주어지니까 한글자씩 비교하면서, 같은 글자가 존재하면 이를 'A'로 바꿔버린다.
예를들어, dared와 bread라고 하면
d a r e d
b r e a d
가
A A A A d
b A A A A
로 바뀌게 되는 것이다. 이제 b,d 두 문자만 남으므로 2개를 제거하는 것이 답이다.
a a b b c c
x x y y b b
이면,
a a A A c c
x x y y A A
로 바뀌니까 총 8개이다.
코드로 작성해보면,
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str1 = sc.next();
String str2 = sc.next();
char[] char1 = str1.toCharArray();
char[] char2 = str2.toCharArray();
int cnt = 0;
for (int i = 0; i < char1.length; i++) {
for (int j = 0; j < char2.length; j++) {
if (char1[i] == char2[j]) {
char1[i] = 'A';
char2[j] = 'A';
}
}
}
for (int i = 0; i < char1.length; i++) {
if (char1[i] != 'A') {
cnt++;
}
}
for (int i = 0; i < char2.length; i++) {
if (char2[i] != 'A') {
cnt++;
}
}
System.out.println(cnt);
}
}
|
cs |
Sol 2)
애너그램이라는게 결국 알파벳의 종류, 그 개수가 완전히 같은 단어이므로
각 단어에서 어떤 알파벳을 가지고 있고, 각각 몇개씩 가지고 있는지를 비교하도록 한다.
예를들어,
dared: 'a': 1, 'b': 0, 'd': 2, 'e': 1, 'r': 1 이고
bread: 'a': 1, 'b': 1, 'd': 1, 'e': 1, 'r': 1 이다.
알파벳의 종류와 그 개수가 동일하다면 제거할 필요가 없다. 즉 신경쓸 필요가 없다.
종류와 개수가 다른 경우만 체크해주면 된다.
즉, b와 d만 비교해주고, 그 개수의 차이만큼만 제거해주면 된다. (b 1개, d 1개 총 2개)
코드로 작성해보자.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str1 = sc.next();
String str2 = sc.next();
/*
알파벳 카운트되는 배열만들기
index 0 1 2 3 4 5 ... 25
count
알파벳 a b c d e f ... z
int[] arr = new int[26]; 에서
어떤 단어가 bear이다?
{1, 1, 0, 0, 1.... } 이런식으로 카운트를 표시!
*/
int[] alphaArr1 = new int[26]; // 알파벳 개수(26개)
for (int i = 0; i < str1.length(); i++) {
alphaArr1[str1.charAt(i) - 'a']++;
}
int[] alphaArr2 = new int[26]; // 알파벳 개수(26개)
for (int i = 0; i < str2.length(); i++) {
alphaArr2[str2.charAt(i) - 'a']++;
}
int ans = 0;
for (int i = 0; i < 26; i++) {
if(alphaArr1[i] > alphaArr2[i]) {
ans += alphaArr1[i] - alphaArr2[i];
}
else if(alphaArr1[i] < alphaArr2[i]) {
ans += alphaArr2[i] - alphaArr1[i];
}
}
System.out.println(ans);
}
}
|
cs |
위 코드에서 사용된 중요한 생각!
int[ ] arr = new int [ 26 ];을 만드는 부분
그 결과를 아래 그림처럼 생각해라
첫번째 행은 a,b,c...처럼 알파벳의 위치로 생각하는 부분
두번째 행은 초기값은 다 0이지만, 카운트가 되면 1씩 증가시키는 부분
세번째 행은 index number
Sol 2-1)
위 코드를 좀 더 간결하게 만들기 위해 함수를 사용해보자.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
import java.util.Scanner;
public class Main {
public static int[] get_alphabet_count(String str) {
int[] count = new int[26];
for (int i = 0; i < str.length(); i++) {
count[str.charAt(i) - 'a']++;
}
return count;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str1 = sc.next();
String str2 = sc.next();
int[] alphaArr1 = get_alphabet_count(str1);
int[] alphaArr2 = get_alphabet_count(str2);
int ans = 0;
for (int i = 0; i < 26; i++) {
ans += Math.abs(alphaArr1[i] - alphaArr2[i]); // 차이 구하기 위해 절댓값 사용
}
System.out.println(ans);
}
}
|
cs |