-
문자열 찾기
1) longest-substring-without-repeating-characters
문제 : https://leetcode.com/problems/longest-substring-without-repeating-characters/
1. 슬라이딩 윈도우
반복되지 않는 가장 긴 문자열의 길이를 반환하는 문제다.
(풀고 보니 슬라이딩 윈도우와 비슷한 방식으로 풀었다.)
n = 문자열길이, k = 현재 윈도우 길이 (최대 n)이라고 가정할때,
temp.contains(), temp.indexOf(), temp.substring(...) + s[i] 모두 O(k)의 시간복잡도를 갖고, 이 연산이 최대 n번 반복될 수 있다.
시간복잡도 : O(n^2)
문자열 연산이 계속 일어나므로 새로운 문자열이 계속 생성될 수 있다.
공간복잡도 : O(n)
class Solution { fun lengthOfLongestSubstring(s: String): Int { if(s.length == 0 || s.length ==1) return s.length var temp = "" var answer = 0 for(i in 0 until s.length) { if(temp.contains(s[i])) { answer = max(temp.length, answer) val idx = temp.indexOf(s[i]) temp = temp.substring(idx +1) + s[i] } else { temp += s[i] } } return max(answer, temp.length) } }2. 슬라이딩 윈도우 + HashSet
HashMap (or Set) + Two Pointer로 O(n)의 풀이도 가능하다.
각 문자는 최대 두번만 확인되므로
시간복잡도 : O(n)
문자 Set에 최대 n개를 저장하므로
공간복잡도 : O(n)
class Solution { fun lengthOfLongestSubstring(s: String): Int { val set = mutableSetOf<Char>() var left = 0 var right = 0 var answer = 0 while (right < s.length) { if(set.contains(s[right]).not()) { set.add(s[right]) answer = max(answer, right-left +1) right ++ }else { set.remove(s[left]) left ++ } } return answer } }2) longest-repeating-character-replacement
k개의 문자열을 대체했을때 가장 긴 중복 문자열의 길이를 찾는 문제다.
문제 : https://leetcode.com/problems/longest-repeating-character-replacement
슬라이딩 윈도우를 하면서 문자열 내에서 교체 가능한 윈도우를 찾고, 그 길이를 측정하는 방식으로 진행할 수 있다.
시간 복잡도 : O(n) -> right 포인터는 한번씩, left 포인터도 한번씩만 이동
공간 복잡도 : O(1) -> 고정 배열 크기 26개(알파벳 대문자)만 사용
class Solution { fun characterReplacement(s: String, k: Int): Int { // 슬라이딩 윈도우 + 문자 카운팅 val count = IntArray(26) var left = 0 var maxLen = 0 var maxFreq = 0 for( right in s.indices) { val idx = s[right] - 'A' count[idx] ++ maxFreq = max(maxFreq, count[idx]) val windowSize = right-left +1 if(windowSize - maxFreq >k) { count[s[left] - 'A'] -- left ++ } maxLen = max(maxLen, right-left + 1) } return maxLen }3) minimum-window-substring
문제 : https://leetcode.com/problems/minimum-window-substring/
s, t 두개의 문자열이 주어졌을때, s가 t의 알파벳을 모두 포함할 수 있는 최소 문자열을 구하는 문제다.
슬라이딩 윈도우 + 해시맵 비교를 통해서 해결할 수 있다.
시간 복잡도 : O(n) -> 문자열 s의 left, right 포인터가 한번씩 이동(O(n)) + 맵에 데이터를 넣고 비교/ 카운트 하는 작업(O(1))
공간 복잡도 : O(1) -> s, t에 대한 카운트 저장 맵 2개, 가능한 문자열은 최대 128가지로 고정상수이므로 O(1)
class Solution { fun minWindow(s: String, t: String): String { val tCount = mutableMapOf<Char, Int>() val windowCount = mutableMapOf<Char, Int>() for(c in t) { tCount[c] = tCount.getOrDefault(c, 0) +1 } var left = 0 var have = 0 val need = tCount.size var minLen = Int.MAX_VALUE var answer = "" for (right in s.indices) { val c = s[right] windowCount[c] = windowCount.getOrDefault(c, 0) + 1 if(tCount.containsKey(c) && windowCount[c] == tCount[c]) { have ++ } while(have == need) { if(right-left + 1<minLen) { minLen = right - left + 1 answer = s.substring(left, right+1) } val leftChar = s[left] windowCount[leftChar] = windowCount[leftChar]!! -1 if(tCount.containsKey(leftChar) && windowCount[leftChar]!! < tCount[leftChar]!!) { have -- } left ++ } } return answer } }4) Valid Anagram
문제 : https://leetcode.com/problems/valid-anagram/
두개의 문자열이 주어지면 같은 알파벳으로 이루어져있는지 찾는 문제다.
class Solution { fun isAnagram(s: String, t: String): Boolean { val alpha = IntArray(26) for(char in s) { alpha[char-'a'] ++ } for(char in t) { val idx = char-'a' alpha[idx] -- if(alpha[idx]<0) { return false } } if(alpha.sum()>0) { return false } return true } }5) Group Anagrams
문제 : https://leetcode.com/problems/group-anagrams/
여러개의 문자열이 주어지면, 같은 알파벳으로 이루어진 문자열들을 리스트로 묶어 반환하는 문제다.
n = 문자열 개수, k = 각 문자열의 길이일때,
sorted()를 사용하므로 시간 복잡도는 O(n * klogk)로 리스트가 길어질수록 병목이 될 수 있다 .
공간복잡도는 O(n*k) 다. (모든 문자열 저장 + 그룹화 저장)
class Solution { fun groupAnagrams(strs: Array<String>): List<List<String>> { val map = mutableMapOf<String, MutableList<String>>() for(str in strs) { val sorted = str.toCharArray().sorted().joinToString("") if(map.contains(sorted)) { map[sorted]!!.add(str) }else { map[sorted] = mutableListOf(str) } } val answer = mutableListOf<List<String>>() for(result in map.values) { answer.add(result.toList()) } return answer } }정렬을 사용하지 않고, 갯수 자체를 기록하는 방법을 사용하면 시간을 단축할 수 있다.
시간 복잡도 = O(n*k)
공간 복잡도 = O(n*k)
class Solution { fun groupAnagrams(strs: Array<String>): List<List<String>> { val map = mutableMapOf<String, MutableList<String>>() for (str in strs) { val count = IntArray(26) for (c in str) { count[c - 'a']++ } // 배열을 문자열로 변환 (ex: "1#0#0#..." 식으로 고유 키 생성) val key = count.joinToString("#") map.getOrPut(key) { mutableListOf() }.add(str) } return map.values.toList() } }6) Valid Parentheses
문제 : https://leetcode.com/problems/valid-parentheses/
올바른 괄호 형식을 가지는지 찾는 전형적인 스택 문제다.
class Solution { fun isValid(s: String): Boolean { if(s.length %2 != 0) { return false } val input = listOf('(', '{', '[') val queue = Stack<Char>() for(char in s) { if(input.contains(char)) { queue.push(char) }else if(queue.isEmpty()){ return false }else { val pop = queue.pop() if((pop == '(' && char != ')') || (pop == '{' && char != '}') || (pop == '[' && char != ']') ) { return false } } } if(queue.isNotEmpty()) { return false } return true } }맵을 활용하면 더 간결하게도 가능하다.
class Solution { fun isValid(s: String): Boolean { val stack = Stack<Char>() val pairs = mapOf(')' to '(', '}' to '{', ']' to '[') for (char in s) { if (char in pairs.values) { stack.push(char) } else { if (stack.isEmpty() || stack.pop() != pairs[char]) return false } } return stack.isEmpty() } }Palindrome
1) valid-palindrome
문제 : https://leetcode.com/problems/valid-palindrome
주어진 문자열이 역순으로도 동일한 단어임을 구분한다.
먼저 단순하게 최종 문자열을 구한뒤 역순으로 정렬한 값과 비교했다.
시간복잡도 : O(n)
공간복잡도 : O(n)
class Solution { fun isPalindrome(s: String): Boolean { var str = StringBuilder() for (c in s) { if(c.isLetterOrDigit()) { str.append(c.lowercaseChar()) } } var result = str.toString() return result.reversed() == result } }미리 문자열을 모두 순회하지 않고, 투포인터 기법으로도 문제를 해결할 수 있다.
시간복잡도 : O(1)
공간복잡도 : O(1)
class Solution { fun isPalindrome(s: String): Boolean { var left = 0 var right = s.length - 1 while(left < right) { while(left < right && !s[left].isLetterOrDigit()) left++ while(left < right && !s[right].isLetterOrDigit()) right-- if(s[left].lowercaseChar() != s[right].lowercaseChar()) { return false } left++ right-- } return true } }2) Longest Palindromic Substring
문제 : https://leetcode.com/problems/longest-palindromic-substring/
문자열을 순회하면서 중심 지점을 선정하고 최대 길이를 가질 수 있는 문자열을 출력한다.
시간복잡도 : O(n^2)
공간복잡도 : O(1)
class Solution { fun longestPalindrome(s: String): String { if(s.length < 2) return s var start = 0 var end = 0 for(i in s.indices) { // 현재 시작점 i val len1 = expand(s, i, i) // 홀수 개라고 가정하고 최댓값 계산 val len2 = expand(s, i, i+1) // 짝수 개라고 가정하고 최댓값 계산 val len = maxOf(len1, len2) if(len>end-start) { // 최댓값 발생으로 정답 갱신 (홀수와 짝수에서 모두 정답을 낼 수 있는 인덱스 값 확인) start = i - (len-1)/2 end = i + len/2 } } return s.substring(start, end+1) } private fun expand(s:String, left:Int, right:Int): Int{ var l = left var r = right while(l>=0 && r<s.length && s[l]==s[r]) { l-- r++ } return r-l-1 } } var start = 0 var answer = 0 fun longestPalindrome(s: String): String { if(s.length <2) return s for(i in 0..s.length) { isPalindrome(s, i, i+1) isPalindrome(s, i, i+2) } return s.substring(start, start+answer) } fun isPalindrome(s: String, left: Int, right: Int) { var l = left var r = right while(l>=0 && r <s.length && s[l] == s[r]) { l -- r ++ } if(answer < r-l-1) { answer = r-l-1 start = l+1 } }3) palindromic-substrings
문제 : https://leetcode.com/problems/palindromic-substrings/submissions/1628517953/
palindromic의 갯수를 세는 문제로 상단의 문제를 응용해서 풀 수 있다.
시간복잡도 : O(n^2)
공간복잡도 : O(1)
class Solution { fun countSubstrings(s: String): Int { var count = 0 for(i in s.indices) { count += expand(s, i, i) count += expand(s, i, i+1) } return count } private fun expand(s: String, left: Int, right:Int): Int { var cnt = 0 var l = left var r = right while(l >=0 && r <s.length && s[l] == s[r]) { l-- r++ cnt++ } return cnt } }4) string-encode-and-decode
문제 : https://neetcode.io/problems/string-encode-and-decode
문자열을 encode하고 decode 하는 함수를 만든다.
이때, 문자열을 누락하지 않고 그대로 encode, decode할 기준점을 잡아야 한다.
class Solution { public String encode(List<String> strs) { StringBuilder sb = new StringBuilder(); for(int i =0; i < strs.size() ; i++) { sb.append(strs.get(i).length()).append("#").append(strs.get(i)); } return sb.toString(); } public List<String> decode(String str) { List<String> result = new ArrayList<String>(); int i = 0 ; while(i < str.length()) { int j = str.indexOf('#', i); // i 부터 찾는다 int len = Integer.parseInt(str.substring(i, j)); // 문자열 사이즈 String s = str.substring(j+1, j+1 + len); // 문자열 result.add(s); i = j+1 + len ; } return result ; } }5) valid palindrome 2
문제 : https://leetcode.com/problems/valid-palindrome-ii/
class Solution { fun validPalindrome(s: String): Boolean { var left = 0 var right = s.length -1 while (left < right) { if(s[left] != s[right]) { return isPalindrome(s, left+1, right) || isPalindrome(s, left, right-1) } left ++ right -- } return true } private fun isPalindrome(s: String, l: Int, r:Int): Boolean{ var left = l var right = r var moved = false while (left < right) { if(s[left] != s[right]) { return false } left ++ right -- } return true } }reverse string
문제 : https://leetcode.com/problems/reverse-string/
class Solution { fun reverseString(s: CharArray): Unit { var left = 0 var right = s.size - 1 while (left < right) { val temp = s[left] s[left] = s[right] s[right] = temp left ++ right -- } } }Reorder data log
문제 : https://leetcode.com/problems/reorder-data-in-log-files/
1. 로그 분리 (digit/letter):
- for 루프에서 각 로그에 대해 split(" ")[1][0].isDigit() 평가
- split은 최대 한 번만 하므로, O(n * m)
- n = 로그 개수
- m = 평균 로그 길이
2. 문자로그 정렬:
- sortWith는 일반적인 비교 기반 정렬이므로 O(k log k)
- k = 문자 로그 개수 (k ≤ n)
- 비교 시마다 split(" ", limit = 2)를 호출 → 문자열 복사 연산 포함
- 각 비교는 O(m)
- 전체 정렬: O(k log k * m)
3. 리스트 합치기 (addAll, toTypedArray):
- addAll: O(d) (숫자로그 개수 d ≤ n)
- toTypedArray: O(n)
총 시간 복잡도
O(n * m) + O(k log k * m) + O(n)
= O(n * m + k log k * m) = 최악의 경우 (k = n)O(nlogn*m)공간복잡도
= O(n)
class Solution { fun reorderLogFiles(logs: Array<String>): Array<String> { val digitLogs = mutableListOf<String>() val letterLogs = mutableListOf<String>() for(log in logs) { if(log.split(" ")[1][0].isDigit()) { digitLogs.add(log) }else { letterLogs.add(log) } } letterLogs.sortWith(Comparator {s1: String, s2:String -> val s1Log = s1.split(" ", limit = 2) val s2Log = s2.split(" ", limit = 2) val compared = s1Log[1].compareTo(s2Log[1]) if(compared == 0) { s1Log[0].compareTo(s2Log[0]) } else { compared } }) letterLogs.addAll(digitLogs) return letterLogs.toTypedArray() } }Most common word
문제 : https://leetcode.com/problems/most-common-word/
class Solution { fun mostCommonWord(paragraph: String, banned: Array<String>): String { val countWord = mutableMapOf<String, Int>() val originalWords = paragraph.replace("\\W+".toRegex(), " ").lowercase() val words = originalWords.trim().split(" ") for(word in words) { if(banned.contains(word)) { continue } countWord[word] = countWord.getOrPut(word, {0}) + 1 } return countWord.maxBy {it.value}.key } }지그재그 문자열 만들기
문제 : https://leetcode.com/problems/zigzag-conversion/?envType=problem-list-v2&envId=string
간단하게 위 아래 방향성으로만 생각하면 된다.
class Solution { fun convert(s: String, numRows: Int): String { if(s.length <= numRows || numRows == 1) { return s } var answer = Array(minOf(numRows, s.length)) {StringBuilder()} var curRow = 0 var isDowning = false for (c in s) { answer[curRow].append(c) if(curRow == 0 || curRow == numRows -1) { isDowning = !isDowning } curRow += if(isDowning) 1 else -1 } return answer.joinToString("") {it.toString()} } }logest palindrome by concatenating two letter words
문제 : https://leetcode.com/problems/longest-palindrome-by-concatenating-two-letter-words
두글자로 이루어진 문자열 배열에서 가장 긴 palindrome을 찾는 문제다.
여기서 구분해야 하는 것은 같은 문자로 이루어진 단어와, 다른 문자로 이루어진 단어가 다르게 취급되어야 한다는 것이다.
하나의 문자로 이루어진 경우 -> 짝수개라면 모두다 사용이 가능, 홀수개로 이루어지면 가운데에만 위치 가능
두개의 문자로 이루어진 경우 -> 반대 문자열이 존재하는 경우 사용이 가능
시간 복잡도 : O(N) (처음 배열 루프) + O(1) (문자기준으로 두글자로 이루어진 map순회 = 26*26) = O(N)
공간 복잡도 : O(1) (단어길이가 두글자고, 맵의 최대 크기는 26*26)
class Solution { fun longestPalindrome(words: Array<String>): Int { val cnt = mutableMapOf<String, Int>() var result = 0 var hasCenter = false for(word in words) { cnt[word] = cnt.getOrDefault(word, 0) + 1 } for((word, freq) in cnt) { val reversed = word.reversed() if(word == reversed) { // 같은 문자 두글자는 짝수이면 두개 다 넣기 가능 result += (freq/2) * 4 // 만약 홀수개가 있다면 센터에 위치시킬 수 있음 if(freq % 2 == 1) { hasCenter = true } // 중복 계산 방지 } else if (word<reversed) { val pairCnt = minOf(cnt.getOrDefault(word, 0), cnt.getOrDefault(reversed, 0)) result += pairCnt *4 } } if(hasCenter) result += 2 return result } }