[반복문] LeetCode 125번 문제 학습

문제 설명

Valid Palindrome 문제는 주어진 문자열이 회문(Palindrome)인지 아닌지 판단하는 거임. 회문이 뭐냐면, 문자열을 뒤집어도 똑같은 거. 예를 들어, "racecar"는 회문이지만 "hello"는 아님.

근데 이 문제엔 조건이 좀 붙음:

• 대소문자 구분 안 함. 즉, 'A'랑 'a'는 같은 거로 취급.
• 특수문자, 공백, 기호는 무시. 알파벳이랑 숫자만 신경 쓰면 됨.
• 예를 들어, "A man, a plan, a canal: Panama"는 다 정리하고 나면 "amanaplanacanalpanama"가 돼서 회문이 맞음.
• 또 다른 예로, "race a car"는 "raceacar"가 돼서 회문이 아님.

결론적으로, 문자열을 정리한 다음에 회문인지 체크해야 함.

문제를 푼 과정

• 소문자를 대문자로 변환 (toUpperCase 함수):
  • 문자열을 하나씩 훑으면서 소문자('a'~'z')를 대문자로 바꿈.
  • 소문자면 ASCII 값에서 32를 빼서 대문자로 바꾸는 방식임. 예를 들어, 'a'(97) - 32 = 'A'(65).
  • 이 과정에서 문자열을 새로 조립하는데, str[:i] + string(str[i]-32) + str[i+1:] 이런 식으로 함.
  • 근데 솔직히 이 방식은 좀 비효율적임. 매번 문자열을 새로 만드는 거라 시간복잡도가 높아질 수 있음.
• 특수문자 제거 (removeSpecialChars -> removeChar 함수):
  • 알파벳('A''Z')이랑 숫자('0''9')만 남기고 나머지(공백, 쉼표, 기호 등)는 다 지움.
  • 문자열을 순회하면서 조건에 안 맞는 문자를 만나면 그 문자를 빼고 문자열을 새로 만듦.
  • 여기서도 문자열을 자꾸 잘라내고 붙이는 방식이라 비효율적인 면이 있음. 게다가 인덱스 조정(i--)도 필요해서 코드가 좀 복잡해 보임.
• 회문 체크 (isPalindrome 함수):
  • 정리가 끝난 문자열을 양쪽 끝에서부터 비교함.
  • for i := 0; i < len(s)/2; i++로 문자열 길이의 절반까지만 돌면서 s[i]랑 s[len(s)-i-1]이 같은지 확인.
  • 다르면 false, 끝까지 문제없이 돌면 true 리턴.
  • 이 부분은 깔끔함. 회문 체크는 보통 이렇게 투 포인터 방식으로 하면 됨.

---

알고리즘

 

• 문자열 전처리:
  • 대소문자 통일 + 특수문자 제거는 문자열을 "정규화"하는 과정임.
  • 소스코드에선 직접 문자열을 순회하면서 처리했지만, 다른 방법(정규표현식 같은 거)도 가능함. 근데 정규표현식은 느릴 수 있으니 이 정도 크기의 문제에선 직접 순회하는 게 나쁘진 않음.
• 투 포인터 (Two Pointers):
  • 회문 체크할 때 양쪽 끝에서 시작해서 가운데로 좁혀오는 방식임.
  • 시간복잡도는 O(n/2) ≈ O(n), 공간복잡도는 추가 메모리 안 쓰니까 O(1)임 (문자열 전처리 빼고).
  • 이건 회문 문제에서 표준적인 접근법임.
• 문자열 조작:
  • toUpperCase랑 removeChar에서 문자열을 자르고 붙이는 방식 썼음.
  • 근데 이 방식은 Go에서 문자열이 불변(immutable)이라 매번 새 문자열을 만들어야 해서 시간복잡도가 좀 높아짐. 최악의 경우 O(n^2)까지 갈 수도 있음.

package main

import "fmt"

func isPalindrome(s string) bool {
	s = toUpperCase(s)
	s = removeSpecialChars(s)

	for i := 0; i < len(s)/2; i++ {
		if s[i] != s[len(s) - i - 1] {
			return false
		}
	}

	return true
}

// 소문자를 대문자로
func toUpperCase(str string) string {
	for i := 0; i < len(str); i++ {
		if str[i] >= 'a' && str[i] <= 'z' {
			str = str[:i] + string(str[i]-32) + str[i+1:]
		}	
	}

	return str
}

// 문자 제거
func removeChar(str string) string {
	for i := 0; i < len(str); i++ {
		if str[i] >= 'A' && str[i] <= 'Z' || str[i] >= '0' && str[i] <= '9' {
			continue
		} else {
			str = str[:i] + str[i+1:]
			i--
		}
	}

	return str
}

// 공백, 쉼표, 기호, 특수문자 제거
func removeSpecialChars(str string) string {
	return removeChar(str)
}


func main() {
	input1 := "0P"

	fmt.Println("Output:", isPalindrome(input1)) // true
}