[LeetCode Top Interview 150]
[문제 링크]
[문제 설명]
모든 대문자를 소문자로 변환하고 영숫자가 아닌 문자를 모두 제거한 후 앞뒤로 동일하게 읽는 경우 구문은 회문
영숫자 문자에는 문자와 숫자가 포함
주어진 문자열이 회문이면 True를 반환하고 , 그렇지 않으면 False 반환
여기서 회문이란 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters)을 뜻한다.
[예시1]
Input: s = "A man, a plan, a canal: Panama" 출력: true 설명: "amanaplanacanalpanama"는 회문입니다.
[예시2]
입력: s = "race a car" 출력: false 설명: "raceacar"는 회문이 아닙니다.
[예시3]
입력: s = " " 출력: true 설명: s는 영숫자가 아닌 문자를 제거한 후의 빈 문자열 ""입니다. 빈 문자열은 앞뒤로 동일하게 읽으므로 회문입니다.
[제약]
- 1 <= s.length <= 2 * 105
- s consists only of printable ASCII characters. (s는 인쇄 가능한 ASCII 문자로만 구성)
[어떻게 풀지 고민해보기]
먼저 필요한 부분 정리해보기
1) 모든 대문자를 소문자로 변환하는 작업 → 대문자에서 소문자로 변환해주는 함수가 필요할 것
2) 영숫자가 아닌 문자를 모두 제거하는 작업 → 정규식이 필요할 것이다.
3) 소문자+영숫자 아닌 문자 제거한 문자열이 회문인지 검증하는 작업
1번과 2번에 대한 접근 방법은 문제를 처음 본 순간 감이 잡혔지만, 3번을 구체적으로 어떻게 풀어 나갈 지가 이 문제를 해결하는 데 있어서 가장 중요한 요소인 것 같았다.
[내가 생각해 본 방법들]
방법1
1번) 첫 문자와 마지막 문자를 비교
2번) 첫 문자+1과 마지막 문자-1을 비교
… 끝과 끝, 그 다음과 다음… 서로 대칭되는 문자열을 반복적으로 비교해서
회문이면 true, 아니면 false?
방법2
문자열을 절반으로 자름
변수 left에는 첫글자, 변수 right에는 마지막글자
이런 식으로 하나씩 단어를 쪼개 담아서 비교하는 방법..은 뭔가 배열에까지 접근해야 할 것 같은 느낌이 들고 복잡해질 것 같았다.
방법3
문자열이므로.. 글자수 개수(길이)를 가지고, 2로 나뉘면 → 짝수 / 아니면 홀수로 나눠서 뭔가 조건을 판단하여 처리하기?
내가 접근해볼 수 있는 방법 중에 방법 1이 해볼 만 한 것 같아서 도전해봤다.
아래는 시행 착오 코드들부터 최종 Accepted된 제출 코드까지이다.
[시행 착오 코드1]
class Solution {
public boolean isPalindrome(String s) {
// 대문자를 소문자로 변환
s = s.toLowerCase();
System.out.println("s toLowerCase = " + s);
// 영숫자가 아닌 문자를 모두 제거
String match = "[^\uAC00-\uD7A30-9a-zA-Z]";
s = s.replaceAll(match, "");
System.out.println("s replaceAll = " + s);
int j = 1;
// 문자열의 첫 글자
char first = s.charAt(0);
// 문자열의 마지막 글자
char last = s.charAt(s.length() - j);
String palindrome = "";
for (int i = 0; i < s.length(); ) {
if (first == last) {
i++;
j++;
first = s.charAt(i);
last = s.charAt(s.length() - j);
palindrome = "palindrome";
} else {
palindrome = "isNotpalindrome";
}
}
return palindrome == "palindrome";
}
}1) 모든 대문자를 소문자로 변환하기 위하여 Java String 관련 함수 중, toLowerCase() 함수를 사용하였다.
2) 영문자가 아닌 문자를 모두 제거하기 위하여 정규식을 사용하였다.
3) charAt 함수를 통해 문자열의 첫 글자와 마지막 글자를 구하고, for 반복문을 통해 두 글자가 같은지 비교해주었다.
- 사실 정규식과 charAt 함수는 구글 검색을 참고했다.
[시행 착오 코드2] - 그나마 근접하게 다가갔다고 생각한 코드1
class Solution {
public boolean isPalindrome(String s) {
// 1. 대문자를 소문자로 변환
s = s.toLowerCase();
// 2. 영숫자가 아닌 문자를 모두 제거
String regex = "[^A-Za-z0-9]";
s = s.replaceAll(regex, "");
System.out.println("s = " + s);
String palindrome = "";
int palindromeYesCnt = 0;
int palindromeNoCnt = 0;
for (int i = 0, j = 1; i < s.length() & j < s.length(); ) {
// 문자열의 첫 글자 (0부터 시작)
char first = s.charAt(i);
// 문자열의 마지막 글자 (문자열 길이 - 1)
char last = s.charAt(s.length() - j);
// 문자열의 첫 글자 == 문자열의 마지막 글자
// 문자열의 두번째 글자 == 문자열의 마지막에서 첫번째 글자 (끝에서 두번째..)
// for 반복문에 따라 first와 last 문자가 같은 경우
if (first == last) {
//flag를 yes로 정의
palindrome = "yes";
//yes flag의 개수
palindromeYesCnt = palindrome.length();
} else if (first != last) {
//flag를 no로 정의
palindrome = "no";
//no flag의 개수
palindromeNoCnt = palindrome.length();
}
j++; //j 증가
i++; //i 증가
}
// palindromeYesCnt가 0 초과, palindromeNoCnt가 0일때 true를 반환
// 아닌 경우 false 반환
if(palindromeYesCnt > 0 && palindromeNoCnt == 0){
return true;
}else {
return false;
}
}
}[시행 착오 코드3] - 그나마 근접하게 다가갔다고 생각한 코드2
class Solution {
public boolean isPalindrome(String s) {
// 1. 대문자를 소문자로 변환
s = s.toLowerCase();
// 2. 영숫자가 아닌 문자를 모두 제거
String regex = "[^A-Za-z0-9]";
s = s.replaceAll(regex, "");
System.out.println("s = " + s);
String palindrome = "";
int palindromeYesCnt = 0;
int palindromeNoCnt = 0;
for (int i = 0, j = 1; i < s.length() & j < s.length(); ) {
// 문자열의 첫 글자 (0부터 시작)
char first = s.charAt(i);
// 문자열의 마지막 글자 (문자열 길이 - 1)
char last = s.charAt(s.length() - j);
// 문자열의 첫 글자 == 문자열의 마지막 글자
// 문자열의 두번째 글자 == 문자열의 마지막에서 첫번째 글자 (끝에서 두번째..)
// for 반복문에 따라 first와 last 문자가 같은 경우
if (first == last) {
//flag를 yes로 정의
palindrome = "yes";
//yes flag의 개수
palindromeYesCnt = palindrome.length();
} else if (first != last) {
//flag를 no로 정의
palindrome = "no";
//no flag의 개수
palindromeNoCnt = palindrome.length();
}
j++; //j 증가
i++; //i 증가
}
// palindromeYesCnt가 0 초과, palindromeNoCnt가 0일때 true를 반환
// 아닌 경우 false 반환
if(palindromeYesCnt > 0 && palindromeNoCnt == 0){
return true;
// s가 "" 문자열일 때 || s의 길이가 1일 때
}else if(s == "" || s.length() == 1){
return true;
}else {
return false;
}
}
}
테스트 케이스에 palindrome sentence examples을 추가해서 돌릴 땐 Accepted가 낫지만..
palindrome sentence examples
"Mr. Owl ate my metal worm",
"Do geese see God?"
"Was it a car or a cat I saw?"
Submit 제출하고 나면 Output Limit Exceeded 발생
— 예상보다 많은 출력이 발생할 경우 / 무한 루프가 돌 때 발생하는 에러라고 한다.
이전에 작성했던 코드들을 테스트 할 때, for문에서 변수 i나 j가 증가되지 않는 등의 문제가 발생했던 것을 생각해보면 반복문에서 무한 루프가 도는가보다.. 하고 유추했다.
그래서 가장 중점적으로 개선했던 부분은 for 반복문이었다. 뭔가 이중 반복문을 사용하지 않아도 될 것 같아서 섞어서 썼던 것이 화근이 된 것 같아서 이중 반복문으로 코드를 수정하였다.
[최종 완성 코드] : 추가 개선 / 주석 정리
- 소요 시간 : 약 5시간 20분
- 추가적으로 해야할 부분들
- 시간 복잡도, 공간 복잡도 개선하기
- 다른 사람들이 풀이한 다양한 코드 확인 해보기
class Solution {
public boolean isPalindrome(String s) {
s = s.toLowerCase();
s = s.replaceAll("[^A-Za-z0-9]", "");
String palindrome = "";
int palindromeYesCnt = 0;
int palindromeNoCnt = 0;
for (int i = 0; i < s.length(); i++) {
for (int j = i + 1; j < s.length(); j++) {
char first = s.charAt(i);
char last = s.charAt(s.length() - j);
if (first == last) {
palindrome = "yes";
palindromeYesCnt = palindrome.length();
} else if (first != last) {
palindrome = "no";
palindromeNoCnt = palindrome.length();
}
i++;
}
}
if (palindromeYesCnt > 0 && palindromeNoCnt == 0) {
return true;
} else if(s == "" || s.length() == 1){
return true;
} else {
return false;
}
}
}