[알고리즘/자료구조] JAVA 애너그램(Anagram) 알고리즘 문제 (코딩테스트 준비)
난이도 [하]
문제: 문자열 o와 문자열 a가 입력으로 들어오고, a는 o의 애너그램이라면 true, 그렇지 않다면 false를 반환 하라.
case 1.
입력: apple, lepap
출력: true
case 2.
입력: samsung, nanssug
출력: false
문제풀이.
위의 문제를 풀기위해서 천천히 알아보려고 합니다.
input형식은 문자열과 문자열 들어오고, 출력값은 true or false입니다.
class Solution {
public int[] twoSum(String o, String a) {
return true;
}
}문제를 먼저 이해하고 넘어가도록 합니다.
나무 위키에서 검색해보면
애너그램?
어떠한 단어의 문자를 재배열하여 다른 뜻을 가지는 다른 단어로 바꾸는 것을 말한다.
즉. o가 원본 orignal이고 a가 anagram입니다.
그럼 조건을 볼까요?
1. a가 o의 애너그램인지 아닌지를 판단
2. 애너그럼이라면 true, 아니라면 false를 반환
우리는 완전하지는 않지만 2번은 반은 성공했습니다.
return true를 주었으닌깐요!
이젠 1번 로직을 완성하여 최종적으로 return false도 만들어 봅시다.
해당문제를 푸는 방법은 여러개가 있습니다.
1. 하나하나 비교를 한다.
o=abc, a= bac라면
a-b -> a-a : ok 다음 인덱스
b-b : ok 다음 인덱스
c-b -> c-a -> c-c : ok 다음 인덱스
다음 인덱스 없음 true로 종료.
2. 글자수를 비교한다.
o=abc, a= bac라면
o에 a=1개, b=1개, c=1개
a에 a=1개, b=1개, c=1개
o를 반복하면서 a와 비교 (key:value)
3. 단순하게 1, 0으로 표기하기.
o=abc, a= bac라면
o = a를 첫번째에 넣고,
a = a를 첫번째에서 빼고,
o = b를 두번째에 넣고,
a = b를 두번째에서 빼고,
....
크게 이러한 방법이 있겠네요!
그럼 위와 같은 경우를 자료구조를 이요한다면?
1번 경우 두개의 배열을 만들어두고 하나하나 비교해가능방식.
2번 경우 두개의 해쉬맵을 이용하여 key-value를 비교하는 방식
3번 경우 한개의 배열을 가지고 a라면 0번째 b라면 1번째..식으로 비교하는방식
이있습니다.
우리는 간단하게 하기위해 하나의 자료구조를 사용하는 3번을 예로 들어볼께요.
3번이 무슨말인가..? 는 코드를 보면서 설명하겠습니다.
그럼 우린 하나의 배열을 이용할 것이기 때문에 배열을 하나 선언하도록 할께요.
배열의 크기는 26만 넘으면 됩니다.
그 이유는 우리는 a는 0, b=1 , c=2 ... 처럼 알파벳에 따라 인덱스를 사용할 것이기 때문에 알파벳이 26자 임으로 배열의 크기는 26이상! 그 이상잡는다해도 안쓸거예요. 즉, 공간 낭비가 되겠죠?
그럼 배열을 만들어 보겠습니다.
class Solution {
public int[] twoSum(String o, String a) {
int[] arrTemp = new int[26];
return true;
}
}26크기의 배열을 만들었습니다.
다음으로는 각 알파벳에 맞춰 해당 인덱스로 넣어보겠습니다.
우리가 반복할 최대 갯수는 원본인 o의 최대 크기입니다.
class Solution {
public int[] twoSum(String o, String a) {
int[] arrTemp = new int[26];
for(int i=0-;i<o.length();i++){
// 실제 로직
}
return true;
}
}위와 같이 만들어 졌습니다.
이제 o의 크기만큼 반복을 할거고, o에 있는 단어 하나하나를 각 인덱스에 넣어보겠습니다.
class Solution {
public int[] twoSum(String o, String a) {
int[] arrTemp = new int[26];
for(int i=0-;i<o.length();i++){
arrTemp[o.charAt(i)-'a']++;
}
return true;
}
}arrTemp[o.charAt(i)-'a']++;
이코드를 보면 우리가 만든 26크기를 가지는 arrTemp를 증가시킬건데, 어떤 인덱스를 증가시킬거냐면 [o.charAt(i)-'a']인덱스를 증가 시키겠다 입니다.
charAt는 String으로 들어온 값을 char로 만들어주는 기능을합니다.
더 쉽게 코드를 분해해 보겠습니다.
arrTemp : 26의 크기를 가지는 배열
[o.charAt(i)-'a'] : 인덱스
-> o.charAt(i) : o의 i번째를 char로 만들겠다. 처음 for문을 돌게되면 i=0이기 때문에 o가 가지는 String의 첫번째를 단어로 만들겠다.
-> -'a' : 위에서 String의 첫번재 단어를 'a'를 빼겠다 (아스키코드를 이용)
++; : 증가
[o.charAt(i)-'a'] 이부분은 하단에 부연설명을 해드리겠습니다.
그럼 위코드는 o의 크기만큼 돌건데, 돌면서 arrTemp 각 인덱스를 1증가시켜줘!
가 됩니다.
그럼 1을 증가했으니, 똑같은 알파벳이 들어온다면 ? 1을 감소시키면 최종적으로 0이라는 숫자가 arrTemp에 들어가겠죠?
다시말해 arrTemp에 1이 있다면 o에 a에중복된 알파벳이 없었다는 뜻입니다.
a의 알파벳도 똑같이 코드를 작성하는데 -를 줘서 중복이었다면 0, 중복이 아니었다면 1이 들어가게 작성해보겠습니다.
class Solution {
public int[] twoSum(String o, String a) {
int[] arrTemp = new int[26];
for(int i=0-;i<o.length();i++){
arrTemp[o.charAt(i)-'a']++;
arrTemp[a.charAt(i)-'a']--;
}
return true;
}
}자 위와 같은 로직이 완성되었습니다.
arrTemp[o.charAt(i)-'a']++; // o의 알파벳에 따라 해당 인덱스에 1을 증가해줘!
arrTemp[a.charAt(i)-'a']--; // a의 알파벳에 따라 해당 인덱스에 1을 증가해줘!
o의 알파벳 갯수만큼 인덱스는 증가할것이고, a의 알파벳 갯수만큼 인덱스는 감소할것입니다.
o = aabc라면
arrTemp[0]번째에 2
a = abc라면
arrTemp[0]번째에 1
그럼 a와 o가 같지않다는것을 알수있습니다. (arrTemp[0]번째에 2/arrTemp[0]번째에 1 왜 인덱스번호가 지정되었는지 확인하실 분들은 맨아래 글을 읽어주세요.)
그럼 마지막으로 arrTemp에 1이 라는값이 존재하는지 확인해야 합니다.
1이라는 값이 존재한다면? 중복된 데이터가 없었다는 뜻이므로 false를 반환하게 됩니다.
class Solution {
public int[] twoSum(String o, String a) {
int[] arrTemp = new int[26];
for(int i=0-;i<o.length();i++){
arrTemp[o.charAt(i)-'a']++;
arrTemp[a.charAt(i)-'a']--;
}
for(int j : arrTemp){
if(j!=0){
return false;
}
}
return true;
}
}그럼 위와 같은 코드가 완성되게 됩니다.
이로써 우리는 알고리즘 문제를 해결하게 되었습니다.
하.지.만.
만약!
o = abc
a = abcd
라면 ? 굳이 저 for문들을 돌아야할까요?
아니죠, 우리는 이것이 애너그램인지 아닌지는 하나하나 보지않고도 알수 있습니다.
바로 길이로 말이죠.
위 예제2를 가져와볼까요?
case 2.
입력: samsung, nanssug
출력: false
길이가 같다면 틀린 알파벳이있는지 하나하나 봐야하는게 맞습니다.
하지만 예제가 아래와 같다면?
case 2.
입력: samsung, nanssugsnm
출력: false
길이가 다르기 때문에 단번에 애너그램이 아니라는 것을 알수있습니다.
for문을 사용하지도 않구요! 그럼 더 프로그램이 간단하고 빨리 끝나겠죠?
그래서 코드를 아래와 같이 수정해줍니다.
class Solution {
public int[] twoSum(String o, String a) {
if(o.length()!=a.length()){
return false
}
int[] arrTemp = new int[26];
for(int i=0-;i<o.length();i++){
arrTemp[o.charAt(i)-'a']++;
arrTemp[a.charAt(i)-'a']--;
}
for(int j : arrTemp){
if(j!=0){
return false;
}
}
return true;
}
}이로써, 위 코드로 우리가 구현하고자 하는 알고리즘을 구현함과 동시에 최적의 코드를 만들었습니다.
변수를 지정하는것도 메모리에 올라가게 되는데, 우리는 변수를 지정하기전 if문을 넣음으로써 if조건이 된다면
메모리를 사용하지않고 프로그램을 종료하게 됩니다.
[o.charAt(i)-'a'] 부연 설명
[o.charAt(i)-'a'] 는 아스키코드가 사용되어 - 연산을 하게 됩니다.
o가 abc라면
o.charAt(0) = a
o.charAt(1) = b
o.charAt(2) = c
가 됩니다. 그럼 최종적으로 인덱스 안에는 ['a'-'a'], ['b'-'a'], ['c'-'a']가 됩니다.
아스키코드는 부호체계로 흔히 사람들의 언어를 숫자로 표현한 체계입니다.
다시 돌아와서 ['a'-'a'], ['b'-'a'], ['c'-'a'] 는 코드로 변환되어 컴퓨터는 [97-97], [98-97], [99-97]로 인식을 하게됩니다.
우리는 인덱스를 지정하지 않고, 알고있는 정보는 알파벳하나 밖에 모르지만 인덱스가 계산되어 들어가는걸 볼수있습니다.