[LeetCode] 1544. Make The String Great (java)

✏️ 문제

Given a string s of lower and upper case English letters.
A good string is a string which doesn't have two adjacent characters s[i] and s[i + 1] where:
0 <= i <= s.length - 2s[i] is a lower-case letter and s[i + 1] is the same letter but in upper-case or vice-versa.
To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can keep doing this until the string becomes good.
Return the string after making it good. The answer is guaranteed to be unique under the given constraints.
Notice that an empty string is also good.

 

 

🤖 알고리즘

 

#문자열  #스택

 

 

🤯 풀이 방법 / 👾 구현 코드 (자바)

 

시도 ①

 

class Solution {
    String check(String ss) {
        for (int i = 0; i < ss.length() - 1; i++) {
            if (Math.abs(ss.charAt(i) - ss.charAt(i + 1)) == 32) {
                return ss.substring(0, i) + ss.substring(i + 2);
            }
        }
        return "end";
    }
    
    public String makeGood(String s) {
        while (true) {
            String re = check(s);
            if (re == "end") {
                break;
            }
            s = re;
        }
        return s;
    }
}

 

 

for문으로 순서대로 앞뒤 아스키코드의 절대값(32 차이면 대소문자 차이임)을 비교해 가며 발견하면 그 부분을 빼고 새로운 문자열을 리턴하고, 다시 그 문자열로 반복문을 돌린다.

다 없어질 때까지 해야 하기 때문에 while 반복 일단 돌리고 return값이 문자열이니까 신호 넣어서 한바퀴 다 돌아도 없으면 그 신호 리턴 받고 종료

 

 

 

 

시간은 나쁘지 않은데 메모리 관리는 여전히 어렵다..

그래서 한번 돌았으면 최대한 그 다음 인덱스부터 하는 방법을 생각해봄 (메모리와 관련이 있는지는? 모름) 

 

 

 

 

시도 ②

 

class Solution {
    
    int check(int idx, String ss) {
        for (int i = idx; i < ss.length() - 1; i++) {
            if (Math.abs(ss.charAt(i) - ss.charAt(i + 1)) == 32) {
                // 아스키값 차이가 32인 것 -> 대소문자 인 관계 발견하면 둘 다 삭제
                return i;
            }
        }
        return -1;
    }
    
    public String makeGood(String s) {
        int idx = 0;

        while (true) {
            // 모두 없어질때까지 반복
            idx = check(idx, s);
            if (idx == -1) {
                break;
            }
            s = s.substring(0, idx) + s.substring(idx + 2);
            idx = Math.max(0, idx - 2);  // 인덱스 에러 방지

        }
        return s;
    }
}

 

 

문자열 리턴 대신 인덱스 값을 땨로 관리해봄..

파라미터에 인덱스도 같이 넣고 이번엔 함수에서 나와서 문자열을 수정하고,

인덱스가 반환되니까 그 인덱스를 다시 넣어주면 적어도 한 번 간 데는 덜 돌지 않을까 싶었다

그런데 두 자리를 빼고 다시 도는 인덱스니까 -2를 해 주고, 남은 문자열이 두 자리일 때도 돌아야 하니까 0과 비교해서 다시 파라미터로 넣어 주었음 

 

 

 

시간은 거의 비슷한데 메모리는 아주 조금 줄었다..

 

 

---

 

 

https://leetcode.com/problems/make-the-string-great/

 

언제까지 easy만 풀 셈이지 싶지만........ 그냥 머리 안 굳으려고 재미로 푸는 거니깐 더 어렵고 싶지가 않다 🫠 자바 어려와