Algorithm
숫자와 하이픈 패턴으로 같은 패턴 찾기 알고리즘
태인킴
2020. 10. 26. 17:32
반응형
1. 문제
| "010-1234-1234" | 휴대폰 번호 |
| "02-123-1234" | 전화 번호 |
| "1234-1234" | A 자격증 번호 |
| "123456-1234567" | 주민번호 |
| 입력 | 출력 |
| { "02-123-1234", "010-1234-1234", "010-2222-2222", "1234-1234"} | {1, 1, 2} |
예를 들어, 위와 같이 숫자의 개수가 같고, 하이픈(-)의 위치가 같으면, 같은 패턴으로 가정하고, 문자열 배열이 주어졌을 때, 같은 패턴 끼리의 개수를 오름차순 배열로 출력 하시오.
2. 2개의 문자열이 같은 패턴인지 비교 로직
import java.util.*;
import java.util.stream.Collectors;
public class One {
public static void main(String[] args) {
final String s1 = "031-43-2345";
final String s2 = "02-39-1643";
CorrectPatternFinder correctPatternFinder = new CorrectPatternFinder();
boolean isCorrectPattern = correctPatternFinder.isCorrectPattern(s1, s2);
System.out.println(isCorrectPattern);
}
}
class CorrectPatternFinder {
/*
* "234-43-2345"
* [3, 2, 4]
* "123-33-5645"
* [3, 2, 4]
* 이 2개의 문자열은 같다고 한다. 2개의 문자열이 주어졌을 때, 같은지, 아닌지 판별하는 메서드
* */
public boolean isCorrectPattern(String s1, String s2) {
int[] s1ToIntArray = Arrays.stream(s1.split("-"))
.mapToInt(String::length)
.toArray();
int[] s2ToIntArray = Arrays.stream(s2.split("-"))
.mapToInt(String::length)
.toArray();
return isSameArrayElements(s1ToIntArray, s2ToIntArray);
}
/*
* [3, 2, 4]
* [3, 2, 4]
* 두 배열은 같은 배열 이다.
* [3, 2, 4]
* [3, 2, 5]
* 두 배열은 다른 배열 이다.
* */
private boolean isSameArrayElements(int[] arr1, int[] arr2) {
int arr1Len = arr1.length;
int arr2Len = arr2.length;
if (arr1Len != arr2Len) return false;
for (int i = 0; i < arr1Len; i++) {
int arr1Value = arr1[i];
int arr2Value = arr2[i];
if (arr1Value != arr2Value) return false;
}
return true;
}
}출력값
boolean isCorrectPattern(String s1, String s2) 메서드를 확인하면, String을 하이픈("-")을 기준으로 stream을 이용해서 int[]를 만들어 냅니다. boolean isSameArrayElements(int[] arr1, int[] arr2) 메서드는 arr1을 기준으로 반복문을 돌면서, arr2와 원소값이 모두 같은지 판별 합니다. 그런데 이 로직은 java API를 이용해서 더 쉽게 구현 할수 있습니다.
3. List.equals(List) 를 통한 비교
/**
* List.equals(List)
* equals API 를 이용해서
* 두 List 간에 인덱스 별 원소 값을 비교하여, 같은 패턴인지 판단
*/
public boolean isCorrectPattern2(String s1, String s2) {
List<Integer> s1ToIntList = Arrays.stream(s1.split("-"))
.mapToInt(String::length)
.boxed()
.collect(Collectors.toList());
List<Integer> s2ToIntList = Arrays.stream(s2.split("-"))
.mapToInt(String::length)
.boxed()
.collect(Collectors.toList());
return s1ToIntList.equals(s2ToIntList);
}위의 로직에서 isSameArrayElements(int[] arr1, int[] arr2) 메서드 대신에 List.equals(List)로 인덱스별 원소의 값을 비교 할 수 있습니다. 훨씬 던 간결해 줬습니다.
4. 문제의 대한 답
이번에는 시그니처를 좀 변경하여 보겠습니다. 실제 문제에서 주어진 입력 처럼, 패턴 문자열 배열을 입력으로 받고, 반환값을 그룹핑된 패턴의 사이즈를 오름차순으로 정렬한 리스트를 반환하도록 변경해 보겠습니다.
import java.util.*;
import java.util.stream.Collectors;
public class One {
public static void main(String[] args) {
CorrectPatternFinder correctPatternFinder = new CorrectPatternFinder();
// [4, 2, 4], [4, 2, 4], [3, 2, 4], [1], [1], [1]
final String[] strs = {"2123-33-5645", "1123-11-5645", "123-33-5645", "2", "1", "2"};
List<Integer> results = correctPatternFinder.getSamePatternSizeList(strs);
results.forEach(value -> System.out.printf("%d ", value));
}
}
class CorrectPatternFinder {
/**
* strs = {"234-43-2345", "134-43-2345", "3134-43-2345"}
* [3, 2, 4](0, 1번째 같은 원소), [3, 2, 4](0, 1번째 같은 원소), [4, 2, 4](같은 원소가 없다)
* 같은 원소의 사이즈를 오름차순 반환
* 반환 {2, 1}
*/
public List<Integer> getSamePatternSizeList(String[] strs) {
// key : 패턴([3, 2, 3]), value : 패턴의 개수
HashMap<List<Integer>, Integer> strPatternMap = new HashMap();
int n = strs.length;
for (int i = 0; i < n; i++) {
List<Integer> list = getListFromStringByHyphen(strs[i]);
if (strPatternMap.containsKey(list)) {
strPatternMap.put(list, strPatternMap.get(list) + 1);
} else {
strPatternMap.put(list, 1);
}
}
// 오름차순 정렬, map to list
return strPatternMap.values().stream()
.sorted(Integer::compare)
.collect(Collectors.toList());
}
private List<Integer> getListFromStringByHyphen(String str) {
return Arrays.stream(str.split("-"))
.mapToInt(String::length)
.boxed()
.collect(Collectors.toList());
}
}출력값
5. List를 HashMap의 key로 사용
/**
* strs = {"234-43-2345", "134-43-2345", "3134-43-2345"}
* [3, 2, 4](0, 1번째 같은 원소), [3, 2, 4](0, 1번째 같은 원소), [4, 2, 4](같은 원소가 없다)
* 같은 원소의 사이즈를 오름차순 반환
* 반환 {2, 1}
*/
public List<Integer> getSamePatternSizeList(String[] strs) {
// key : 패턴([3, 2, 3]), value : 패턴의 개수
HashMap<List<Integer>, Integer> strPatternMap = new HashMap();
int n = strs.length;
for (int i = 0; i < n; i++) {
List<Integer> list = getListFromStringByHyphen(strs[i]);
if (strPatternMap.containsKey(list))
strPatternMap.put(list, strPatternMap.get(list) + 1);
else
strPatternMap.put(list, 1);
}
// 오름차순 정렬, map to list
return strPatternMap.values().stream()
.sorted(Integer::compare)
.collect(Collectors.toList());
}
private List<Integer> getListFromStringByHyphen(String str) {
return Arrays.stream(str.split("-"))
.mapToInt(String::length)
.boxed()
.collect(Collectors.toList());
}위 로직에서, List의 equals는 우리가 원하는로직(인덱스별 값이 같은지 판별) 으로 잘 구현되어 있습니다. 따라서 List를 HashMap의 key로 사용하여 원하는 패턴 끼리 그룹핑을 할수 있습니다.
// key : 패턴([3, 2, 3]), value : 패턴의 개수
if (strPatternMap.containsKey(list))
strPatternMap.put(list, strPatternMap.get(list) + 1);
else
strPatternMap.put(list, 1);이 로직을 보시면, [3, 2, 3](예:"010-23-234") 같은 이미 패턴이 존재 하면, [3, 2, 3] 패턴의 size를 +1 시켜주어 value를 갱신 합니다. 만약 key([3, 2, 3])가 존재 하지 않으면, value를 1로 세팅해 줍니다. 이 로직은 아래와 같이 변경이 가능 합니다.
6. Map.computeIfPresent, Map.putIfAbsent
strPatternMap.computeIfPresent(list, (key, value) -> strPatternMap.get(key) + 1);
strPatternMap.putIfAbsent(list, 1);Map.computeIfPresent()는 메서드 네이밍 처럼, 해당 key가 존재 하면, 연산을 진행 합니다. 여기서 연산은 두번째 파라미터, BiFunction을 통해 key, value를 통한 연산이 가능 합니다. 이 BiFunction의 return 값이 value로 세팅 되는 것 입니다. Map.putIfAbsent()는 메서드 네이밍 처럼, 해당 key가 존재 하지 않으면, value를 1로 세팅 하는 메서드 입니다. Map.computeIfAbsent() 메서드 또한 존재 합니다. 역시, key가 존재 하지않으면, value를 제공 합니다. 두번째 파라미터는 Function(함수형 인터페이스) 입니다. key를 통해 value를 반환 합니다.
7. 전체 소스
import java.util.*;
import java.util.stream.Collectors;
public class SamePatternFinderByTwoString {
public static void main(String[] args) {
final String s1 = "031-43-2345";
final String s2 = "02-39-1643";
CorrectPatternFinder correctPatternFinder = new CorrectPatternFinder();
boolean isCorrectPattern = correctPatternFinder.isCorrectPattern(s1, s2);
System.out.println(isCorrectPattern);
}
}
class CorrectPatternFinder {
/**
* List.equals(List)
* equals API 를 이용해서
* 두 List 간에 인덱스 별 원소 값을 비교하여, 같은 패턴인지 판단
*/
public boolean isCorrectPattern(String s1, String s2) {
List<Integer> s1ToIntList = getListFromStringByHyphen(s1);
List<Integer> s2ToIntList = getListFromStringByHyphen(s2);
return s1ToIntList.equals(s2ToIntList);
}
private List<Integer> getListFromStringByHyphen(String str) {
return Arrays.stream(str.split("-"))
.mapToInt(String::length)
.boxed()
.collect(Collectors.toList());
}
}출력값
위 소스는 두개의 String을 가지고 패턴 비교를 하는 최종 소스 입니다.
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.stream.Collectors;
/**
* strs = {"234-43-2345", "134-43-2345", "3134-43-2345"}
* [3, 2, 4](0, 1번째 같은 원소), [3, 2, 4](0, 1번째 같은 원소), [4, 2, 4](같은 원소가 없다)
* 같은 원소의 사이즈를 오름차순 반환
* 반환 {2, 1}
*/
public class SamePatternFinder {
public static void main(String[] args) {
// [4, 2, 4], [4, 2, 4], [3, 2, 4], [1], [1], [1]
final String[] strs = {"2123-33-5645", "1123-11-5645", "123-33-5645", "2", "1", "2"};
List<Integer> results = getSamePatternSizeList(strs);
results.forEach(value -> System.out.printf("%d ", value));
}
public static List<Integer> getSamePatternSizeList(String[] strs) {
// key : 패턴([3, 2, 3]), value : 패턴의 개수
HashMap<List<Integer>, Integer> strPatternMap = new HashMap();
int n = strs.length;
for (int i = 0; i < n; i++) {
List<Integer> list = getListFromStringByHyphen(strs[i]);
strPatternMap.computeIfPresent(list, (key, value) -> strPatternMap.get(key) + 1);
strPatternMap.putIfAbsent(list, 1);
}
// 오름차순 정렬, map to list
return strPatternMap.values().stream()
.sorted(Integer::compare)
.collect(Collectors.toList());
}
private static List<Integer> getListFromStringByHyphen(String str) {
return Arrays.stream(str.split("-"))
.mapToInt(String::length)
.boxed()
.collect(Collectors.toList());
}
}출력값
위 소스는 패턴 문자열 배열에서 같은 패턴끼리 그룹핑한 사이즈 값을 오름차순으로 출력하는 최종 소스 입니다.
반응형