문제
https://programmers.co.kr/learn/courses/30/lessons/12973
코딩테스트 연습 - 짝지어 제거하기
짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙
programmers.co.kr
풀이
처음엔 문자열의 문자에 대해 탐색을 돌리면서 문자열을 자르고 붙이고를 반복하며 풀었다가 정확성은 100점을 맞았지만 효율성에서 0점을 받아 이후 Stack을 통해서 해결할 수 있었다. Stack을 이용하면 O(n)으로 해결할 수 있다.
문자열의 모든 원소들에 대해 하나씩 확인해 주면서 Stack의 top과 이제 들어올 문자가 같으면 제거할 수 있으므로 해당 문자를 넣지 않고, Stack의 top을 제거해 준다. 이러면 연속되는 같은 두 문자를 제거할 수 있다.
하지만 Stack의 top과 다르다면 제거할 수 없으므로 그냥 Stack에 넣어주었다. 이러한 행위를 반복해서 Stack에 들어오는 연속되는 문자들은 계속 제거되고, 남아있는 문자는 또 다시 들어올 문자와 비교해 줄 수 있어 최종적으로 모든 짝을 제거할 수 있으면 Stack의 크기가 0이 되고, 아니면 1 이상이 될 것이다.
문제를 풀면서 주의할 점은 Stack에 아무것도 들어있지 않은데 Stack의 top을 참조하려 하면 Exception이 날 수 있으니 Stack의 크기가 0일 때는 무조건 Stack에 해당 문자를 넣어주도록 코드를 작성해야 한다.
정답 코드
import java.util.Stack;
class Solution
{
public int solution(String s)
{
int answer = -1;
Stack<Character> st = new Stack<>();
for(int i = 0; i < s.length(); i++) {
if(st.size() == 0) {
st.push(s.charAt(i));
continue;
}
if(st.peek() == s.charAt(i)) {
st.pop();
}
else {
st.push(s.charAt(i));
}
}
answer = st.size() == 0 ? 1 : 0;
return answer;
}
}
효율성 0점 코드
class Solution
{
public int solution(String s)
{
int answer = -1;
StringBuilder sb = new StringBuilder(s);
while (true) {
boolean flag = false;
for(int i = 0; i < sb.length() - 1; i++) {
if(sb.charAt(i) == sb.charAt(i + 1)) {
sb.deleteCharAt(i);
sb.deleteCharAt(i);
flag = true;
}
}
if(sb.length() == 0) {
answer = 1;
break;
}
if(flag == false) {
answer = 0;
break;
}
}
return answer;
}
}'프로그래머스' 카테고리의 다른 글
| [프로그래머스] 프로그래머스 Level3 네트워크 Java (0) | 2022.05.27 |
|---|---|
| [프로그래머스] 프로그래머스 Level2 JadenCase 문자열 만들기 Java (0) | 2022.05.26 |
| [프로그래머스] 프로그래머스 Level2 올바른 괄호 Java (0) | 2022.05.26 |
| [프로그래머스] 프로그래머스 Level2 소수 찾기 Java (0) | 2022.05.26 |
| [프로그래머스] 프로그래머스 Level2 더 맵게 Java (0) | 2022.05.26 |