.leetcode(844. Backspace String Compare)

https://leetcode.com/problems/backspace-string-compare/

 

 

 

 

1. 2022.01.22 시도

소요시간: 28분(구상 3분, 풀이 25분)

class Solution {
    public boolean backspaceCompare(String s, String t) {
        char[] sa = new char[201];
        char[] ta = new char[201];
        
        int sl =convertAndGetLength(s, sa);
        int tl = convertAndGetLength(t, ta);

        if (sl == tl) {
            for (int x=0; x<sl; x++) {
                if (sa[x] != ta[x]) {
                    return false;
                }
            }
            return true;
        }
        
        
        return false;
    }
    
    private int convertAndGetLength(String word, char[] ca) {
        int cl=0;
        for(int x=0; x<word.length(); x++, cl++) {
            char c = word.charAt(x);
            if ( c == '#') {
                cl-=2;
                if (cl < 0) {
                    cl = -1;
                }
            } else {
               ca[cl]=c;
            }
        }
        return cl;
    }
}

풀이 접근 과정

각 단어를 백스페이스를 해결한 상태에서 비교해야겠다. 안그럼 꼬이겠다.
상수형 공간을 쓰려면 길이값을 저장해두자.
공간을 안쓰려면 글자를 변형해야할까? (아니었다.) 사실 상수형 공간이면 범위값만큼만 사용하면 되는 것이었다.( 근데 솔루션은 포인터를 이용한 것이었다 ㅠㅠ)

 

느낀점

• 상수형 공간에 사로잡혀 String을 변형하려고 했거만 String에서 제공해주는 메소드를 찾다보니 시간이 많이 갔다. 결국 없었다.
• 상수형 공간은 고정된 공간이기만 하면 된다. 사실 길이값이 1~200으로 한정적이므로 char[]을 진작 생각하면 되었는데 그걸 나중에 깨닫고 글자를 변형해야만 한다고 생각하니 생각이 막혔다.
• 넣다가 뺀다는걸 생각해보면 stack을 써줘도 되는데 아예 생각도 못했다.
• 앞에 것이 사라지는 스펙이라면 뒤에서부터 접근해볼만 했다. 포인터를 이용했어야했다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형