코딩테스트 풀이/JAVA
[LeetCode/Easy] 1047. Remove All Adjacent Duplicates In String
무지맘
2023. 4. 4. 22:45
1. Input
1) String s
2. Output
1) 다음과 같은 규칙으로 문자열을 지워나갈 때, 최종 문자열을 반환
- 인접한 2개의 문자가 같으면 지운다.
- 더이상 지울 문자가 없을 때까지 반복한다.
3. Constraint
1) 1 <= s.length <= 10^5
2) s는 영어 소문자로만 이루어져 있다.
4. Example
Input: s = "abbaca" -> Output: "ca"
Input: s = "azxxzy" -> Output: "ay"
5. Code
1) 첫 코드(2023/04/04)
for(int i=0 ; i<s.length()-1 ; i++){
if(s.charAt(i)==s.charAt(i+1)){
s = s.substring(0,i) + s.substring(i+2,s.length());
i = Math.max(-1,i-2);
}
}
return s;
- 느리다. 메모리는 그럭저럭
2) 스택으로 구현해본 코드(2023/04/04)
Stack<Character> st = new Stack<>();
for(int i=0 ; i<s.length() ; i++){
char c = s.charAt(i);
if(!st.empty() && st.peek()==c)
st.pop();
else
st.push(c);
}
s = "";
while(!st.empty())
s += st.pop();
return new StringBuffer(s).reverse().toString();
- 1번보다 약간 빨라짐. 메모리는 더 먹음