[leetcode] Make The String Great

문제

• 문제 링크
• 영어 대소문자로 이루어진 문자열 s가 주어진다. s를 Good string으로 바꿔서 반환해야 한다. Good string이란 서로 근접한 문자가 대소문자인 경우가 없는 문자열이다.
• 제약 조건
  • 문자열 길이: 1 <= s.length <= 100

풀이

풀기 전

• 제약 조건이 널널하다. 무식하게 풀어도 풀릴 거 같다.
• 처음에 무식하게 풀어서 풀리긴 했는데 영 마음에 안 들었다. 그래서 스택을 사용해서 다시 풀었다. 문자열 s를 순회하면서 stack의 peek 값과 비교하면 된다. stack에는 반환될 수 있는 후보 문자들이 들어가 있다. peek 값과 현재 순회 중인 값이 Bad 관계라면 peek 값을 날리면 되고, Good 관계라면 현재 값을 stack에 넣어주면 된다.

코드

class Solution {
	// 두 문자가 Bad 한지 확인하는 함수이다.
    private boolean isBad(char ch1, char ch2) {
        return Math.abs(ch1 - ch2) == ('a' - 'A');
    }

    public String makeGood(String s) {
        Stack<Character> stack = new Stack<>();

        for (char ch : s.toCharArray()) {
        	// 스택이 비어있으면 값을 그대로 넣어준다.
            if (stack.isEmpty()) {
                stack.add(ch);
                continue;
            }

            char peek = stack.peek();
            if (isBad(peek, ch)) {  // 두 문자가 Bad 관계면 스택에서 Bad한 문자를 뺀다.
                stack.pop();
            } else {  // 두 문자가 Good 관계면 현재 문자를 스택에 넣는다.
                stack.add(ch);
            }
        }

		// 스택에 있는 값을 StringBuilder에 넣어준다.
        StringBuilder ans = new StringBuilder();
        while (!stack.isEmpty()) {
            ans.append(stack.pop());
        }
        // 스택으로 넣어서 문자가 반대로 들어갔으므로, reverse() 해서 반환한다.
        return ans.reverse().toString();
    }
}

푼 후

• 자료구조 쓸 생각을 처음부터 했으면 좋았겠다.
• 문자열을 한 번만 순회하기 때문에 시간 복잡도는 O(s.length)이고, stack을 문자열만큼만 사용하기 때문에 공간 복잡도도 O(s.length)이다.