문자열 처리 문제 해결 전략
문자열은 다양한 알고리즘 문제의 핵심 데이터 구조입니다. 다음은leetcode 기반의 대표적인 문자열 알고리즘 문제들에 대한 구현과 해설입니다.
1. 문자열 뒤집기
입력된 바이트 배열을 제자리에서 뒤집는 문제입니다. 투 포인터 기법을 사용해 앞뒤로 교환하며 처리합니다.
func reverseInPlace(data []byte) {
n := len(data)
for left := 0; left < n/2; left++ {
right := n - 1 - left
data[left], data[right] = data[right], data[left]
}
}2. 첫 번째 고유 문자 인덱스 찾기
문자열에서 처음으로 한 번만 등장하는 문자의 인덱스를 반환합니다. 빈도 카운팅 후 두 번째 순회로 확인합니다.
func firstUniqueCharIndex(text string) int {
freq := make(map[rune]int)
for _, ch := range text {
freq[ch]++
}
for idx, ch := range text {
if freq[ch] == 1 {
return idx
}
}
return -1
}3. 아나그램 판별
두 문자열이字母의 조합만 다를 뿐 동일한 문자 구성인지 확인하는 문제입니다. 두 가지 접근 방식이 가능합니다.
func areAnagrams_v1(a, b string) bool {
if len(a) != len(b) {
return false
}
countA := make(map[rune]int)
countB := make(map[rune]int)
for _, ch := range a {
countA[ch]++
}
for _, ch := range b {
countB[ch]++
}
for k := range countA {
if countA[k] != countB[k] {
return false
}
}
return true
}
func areAnagrams_v2(x, y string) bool {
if len(x) != len(y) {
return false
}
s1 := []byte(x)
s2 := []byte(y)
sort.Slice(s1, func(i, j int) bool { return s1[i] < s1[j] })
sort.Slice(s2, func(i, j int) bool { return s2[i] < s2[j] })
return string(s1) == string(s2)
}4. 팰린드롬 검증
문자열이 앞에서 읽으나 뒤에서 읽으나 동일한지 확인합니다. 특수문자는 제외하고 영문과 숫자만 고려합니다.
func isPalindromeSequence(input string) bool {
var clean []rune
for _, ch := range strings.ToUpper(input) {
if ('A' <= ch && ch <= 'Z') || ('0' <= ch && ch <= '9') {
clean = append(clean, ch)
}
}
reversed := make([]rune, len(clean))
copy(reversed, clean)
for i := 0; i < len(reversed)/2; i++ {
reversed[i], reversed[len(reversed)-1-i] =
reversed[len(reversed)-1-i], reversed[i]
}
return string(clean) == string(reversed)
}5. 부분 문자열 위치 탐색
하나의 문자열(mojin)에서 다른 문자열(needle)이 처음 등장하는 인덱스를 찾습니다.
func findSubstringIndex(source, target string) int {
srcLen, tgtLen := len(source), len(target)
if tgtLen > srcLen {
return -1
}
for i := 0; i <= srcLen-tgtLen; i++ {
if source[i:i+tgtLen] == target {
return i
}
}
return -1
}6. 중복 없는 가장 긴 부분 문자열
중복 문자 없이 연결된 가장 긴 부분문자열의 길이를 계산합니다. 슬라이딩 윈도우 기법을 사용해 효율적으로 해결합니다.
func lengthOfLongestSubstringUnique(s string) int {
charIndex := make(map[byte]int)
left := 0
maxLen := 0
for right := 0; right < len(s); right++ {
if idx, exists := charIndex[s[right]]; exists && idx >= left {
left = idx + 1
}
charIndex[s[right]] = right
if curLen := right - left + 1; curLen > maxLen {
maxLen = curLen
}
}
return maxLen
}7. 경로 교차 여부 판별
간단한 2차원 격자 상에서 이동 경로가 스스로 교차하는지 확인합니다. 좌표를 해시셋에 기록하면서 이전에 방문한 점이 있는지 검사합니다.
func doesPathSelfIntersect(path string) bool {
directions := map[byte][2]int{
'N': {0, 1},
'S': {0, -1},
'E': {1, 0},
'W': {-1, 0},
}
x, y := 0, 0
visited := make(map[string]bool)
visited["0,0"] = true
for _, step := range path {
dir := directions[byte(step)]
x += dir[0]
y += dir[1]
pos := fmt.Sprintf("%d,%d", x, y)
if visited[pos] {
return true
}
visited[pos] = true
}
return false
}