문자열
- 팰린드롬을 검사하는 간단한 문제이다.
- 단 문자열과 숫자만 비교해야한다.
> Leetcode (125) - 유효한 팰린드롬
나의 풀이 (13ms)
public boolean isPalindrome(String s) {
s = s.toLowerCase();
s = s.replaceAll("[^a-z0-9]","");
int left = 0;
int right = s.length()-1;
for(int i=0; i<s.length();i++ ){
if(left > right){
return true;
}
if(s.charAt(left) == s.charAt(right)){
left++;
right--;
}else{
return false;
}
}
return true;
}
1. 문자 단위로 추출해서 처리 (2ms)
public boolean isPalindrome(String s) {
int start =0;
int end = s.length() - 1;
while(start < end){
if(!Character.isLetterOrDigit(s.charAt(start))){
start++;
}else if(!Character.isLetterOrDigit(s.charAt(end))){
end--;
}else{
if(Character.toLowerCase(s.charAt(start))!=Character.toLowerCase(s.charAt(end))){
return false;
}
start++;
end--;
}
}
return true;
}
2. 문자바로비교 (16ms)
public boolean isPAlindrome(String s){
String s_filtered = s.replaceAll("[^A-Za-z0-9]","").toLowerCase();
String s_reversed = new StringBuilder(s_filtered).reverse().toString();
return s_filtered.equals(s_reversed);
}
- 배운 것
Chracter.isLetterOrDigit으로 숫자와 문자만 검사할 수 있다.
[^A-Za-z0-9] 정규식을 통한 제거
left,right로 하는 것은 좋았으나, 검사를 다르게 하는게 더 빨랐을 것 같다.
> 문자열 뒤집기 LeetCode(344)
1. 나의 풀이 (0ms)
public void reverseString(char[] s) {
int len = s.length;
for(int i=0; i<len/2;i++){
char temp = s[i];
s[i] = s[len-1-i];
s[len-1-i] = temp;
}
}
2. 풀이 스타일이 비슷하다!
int start = 0;
int end = s.length - 1;
while(start < end){
char temp = s[start];
s[start] = s[end];
s[end] = temp;
start++;
end--;
}
- 배열 반만 도는 것 while문으로 표현하면 start<end로 start++, end-- 생각할 수 있다. (시작과 끝에서 한칸씩 오는경우)
> 가장 흔한 단어 (819)
1. 나의 풀이 (26)
public String mostCommonWord(String paragraph, String[] banned) {
//a-z말고 다른 단어 모두 제거
paragraph = paragraph.toLowerCase().replaceAll("[^a-z]"," ");
//띄어쓰기 두개이상인것 하나로 만들고 trim
paragraph = paragraph.replaceAll("\\s+"," ").trim();
//split로 쪼개기
String[] arr = paragraph.split(" ");
List<Integer> idxarr = new ArrayList<>();
for(int i=0; i<arr.length;i++){
int cnt =0;
if(bannedString(arr[i],banned)){
idxarr.add(0);
continue;
}else{
for(int j=i+1; j<arr.length; j++){
//공백이 아니고 같은 단어일 경우 cnt++
if(!arr[i].isBlank()&&arr[i].compareTo(arr[j]) ==0){
cnt++;
}
}
idxarr.add(++cnt);
}
}
int MaxIdx = maxIdx(idxarr);
return arr[MaxIdx];
}
//금지단어일 경우 저장안함
private static boolean bannedString(String ar,String[] bad) {
for(int i =0; i<bad.length;i++){
if(ar.equals(bad[i])){
return true;
}
}
return false;
}
//배열에서 가장 큰 인덱스 찾기
public static int maxIdx(List<Integer> arr){
int maxIdx=0;
for(int i=0; i<arr.size();i++){
if(arr.get(maxIdx) < arr.get(i)){
maxIdx=i;
}
}
return maxIdx;
}
2. HashMap 이용한 풀이
public String mostCommonWord(String paragraph, String[] banned) {
Set<String> ban = new HashSet<>(Arrays.asList(banned));
Map<String,Integer> counts = new HashMap<>();
String[] words = paragraph.replaceAll("\\W+"," ").toLowerCase().split(" ");
for(String w : words){
if(!ban.contains(w)){
counts.put(w,counts.getOrDefault(w,0)+1);
}
}
return Collections.max(counts.entrySet(),Map.Entry.comparingByValue()).getKey();
}
- \W는 문자가 아닌 것을 의미 \W같은 것 사용하려면 replaceAll에선 \\으로 처리해야함
- set에 담은 이유는 contains사용하려고 Array를 List로 만들어서 Set에 담기 (Collection끼리 가능 생성자에 넣기 가능!)
- Map에 getOrDefault가 재밌다 value를 추출했을 때 있으면 값나오고 없으면 default 나옴!
- Collections.max는 가장 큰 값을 찾는다. (entrySet > [키=값, 키=값,키=값] -> map을 약간 배열화), 뒤에는 comp기준 담는다. Map.Entry.comparingByValue()로하면, Entry에 Value를 기준으로 값을 비교한다!
-> 해당메서드의 파라미터값이 객체면 가장 큰 객체 반환해준다!
-> Collection인 List와 Set에서만 사용 가능한듯!
*Collections.max 결과 Map.Entry<String,Integer>로 map에 저장된 엔트리 중 value제일 큰 것 하나 나옴!
=> 주말에 람다쓴 것 적어두기
- 그룹 애너그램 (리트코드 49)
1. 내풀이 (644ms)
public List<List<String>> groupAnagrams(String[] strs) {
//애너그램이란 단어를 다시 조합했을 때 만들 수 있는 단어 의미
List<List<String>> stringList = new ArrayList<>();
for(int i=0; i<strs.length; i++){
if(!"-".equals(strs[i])) {
List<String> ana = new ArrayList<>();
ana.add(strs[i]);
for (int j = i + 1; j < strs.length; j++) {
if (strs[i].length() == strs[j].length()) {
if (isAna(strs[i], strs[j])) {
ana.add(strs[j]);
strs[j] = "-";
}
}
}
stringList.add(ana);
}
}
return stringList;
}
public static boolean isAna(String a, String b){
StringBuilder sb = new StringBuilder(b);
for(char c : a.toCharArray()){
if(b.indexOf(c) == -1){
return false;
}else{
char[] barr = b.toCharArray();
barr[b.indexOf(c)]='?';
b=new String(barr);
}
}
return true;
}
-> 진짜 구리다..무슨생각으로 푼건지 모르겠음 이러지말자!
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> results = new HashMap<>();
for(String s : strs){
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = String.valueOf(chars);
if(!results.containsKey(key)) {
results.put(key,new ArrayList<>());
}
results.get(key).add(s);
}
return new ArrayList<>(results.values());
}
- String을 CharArray로 만든 후 -> sorting해서 키로 사용 -> 해당 키를 이용해서 문자열 값을 담아두기
- 같은 값임을 비교해서 저장해두어야 할 때 위와 같은 생각 떠올려보자. map과 List를 사용해서 저장하는 방법
- 가장 긴 팰린드롬 부분 문자열 (리트코드 5번)
- 내풀이 (283ms)
class Solution {
public String longestPalindrome(String s) {
char[] charArr = s.toCharArray();
TreeMap<Integer,String> paMap = new TreeMap(new Comparator<Integer>(){
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
int left = 0;
int right;
String target="";
int len = charArr.length;
for(; left<len;left++){
right = len-1;
while(left < right){
if(charArr[left] == charArr[right]){
target = s.substring(left,right+1);
if(isPalindro(target)){
if(target.length() == len || len - target.length() < target.length()){
return target;
}
paMap.put(target.length(),target);
}
}
right--;
}
}
if(paMap.isEmpty()){
return String.valueOf(charArr[0]);
}
return paMap.get(paMap.firstKey());
}
public static boolean isPalindro(String target){
int end = target.length()-1;
for(int i=0; i<(end+1)/2;i++){
if(target.charAt(i) != target.charAt(end-i)){
return false;
}
}
return true;
}
}
- 팰린드롬이 무조건 처음과 끝 글자가 같아야하고, 배열은 반만 돌아도 된다는 점
- 맨 왼쪽 단어와 맨 오른쪽 단어 계속 비교해가는 과정으로 작성했음 (left,right)
- 만약 맨 오른쪽 단어와 왼쪽단어가 팰린드롬일 때 두 길이의 합이 전체 길이이거나, 전체 길이에서 팰린드롬을 뺀 길이가
팰린드롬 문자열 길이보다 작다면, 더 긴 필랜드롬이 나올 수 없음으로 return했다.
2. 투포인터 사용하기 (13ms..뮈친)
-> 최장 공통 부분 문자열 (DP)로 푸는 전형적인 문제이지만, 속도가 안나온다! 따라서 투포인터를 사용하셨다한다
int left;
int maxLen;
public String longestPalindrome(String s){
int len = s.length();
if(len < 2) return s;
for(int i = 0; i < len -1; i++){
//0,1-> 1,2 2칸씩 확장하는 투포인터
extendPalindrome(s,i,i+1);
//3칸씩 확장하는 투포인터
extendPalindrome(s,i,i+2);
}
return s.substring(left,left + maxLen);
}
public void extendPalindrome(String s, int j, int k){
while(j >= 0 && k <s.length() && s.charAt(j) == s.charAt(k)){
j--;
k++;
}
if(maxLen < k-j-1){
left = j +1;
maxLen = k - j -1;
}
}
> 팰린드롬을 발견하면, 확장하는 형태의 풀이
> 처음에 주어진 값에 따라 팰린드롬으로 판별된다면, 왼쪽, 오른쪽으로 퍼지면서 중앙에서부터 판별!
> 두개의 포인터가 2칸 3칸으로 (2>4>6),(1>3>5)형태로 확장된다.
ex) dcbabcdd
> 2개의 투 포인터가 우측으로 이동하다 3칸짜리 투포인터는 bab에서 팰린드롬으로 매칭되어, 양옆으로 확장하면서
가장 긴값을 가진다. 두개짜리 투포인터는 dd가 매칭되지만 더 확장을 못함!
> 마지막에 k-j-1을 해주는 이유는 조건식에 따라 마지막으로 검사하면서 k는 팰린도룸보다 1커질 수 있음!
scbabkl 길이 3,start는 2,end 4 > 이때 k는 5,j는 1 길이는 5로 측정됨
따라서 left는 j+1, maxlen은 k-j-1해주어야함! (위치뺀거랑 길이 다르다~)
- 투포인터 알고리즘
> 두개의 포인터를 사용해서 리스트나 1차원 배열을 탐색하는 알고리즘을 의미한다.
> 순차적으로 접근하며, 위치를 기록해두어야할 때 좋다. 또한 정렬되어있을 때 성능이 좋다.
> 연속된 배열 혹은 리스트에서 부분을 찾아야할 때 많이 사용되는 것 같다!
> 보통 left,right 혹은 start, end를 사용한다.
> 보통 left(start) <= right(end) 조건을 많이 사용한다.
> 시작과 끝을 가리키는 경우가 많다. (위의 팰린드롬 문제는 그렇게 하지않긴함)