[201107] 짝지어 제거하기 - 2017 팁스타운(level2)

0. 문제유형 : 적절한 자료구조 선택(Stack)

1. 문제이해

programmers.co.kr/learn/courses/30/lessons/12973

코딩테스트 연습 - 짝지어 제거하기

(1) 주요 요구사항

- String s : 알파벳 소문자로 이루어진 문자열

- 짝지어 제거하기

: 같은 알파벳이 2개 붙어 있는 짝 : 제거한 뒤, 앞뒤로 문자열을 이어 붙임

- 위 과정을 반복해 s가 빈 문자열이 된다면 1, 더 이상 제거되지 않는다면 0 return

(2) 제한사항

- 문자열 길이 : 1,000,000 이하의 자연수

- 모두 소문자로 이루어짐 : 대소문자 처리에 신경쓰지 않아도 됨

 

 

2. 전략

(1) 문자열 순차적으로 탐색 & Stack 자료구조 이용

- Stack의 특징 : LIFO(Last In First Out) 구조로 바로 직전의 요소를 확인하기 유용

→ 현재 탐색 중인 문자와 이전의 문자가 같은지 여부를 체크할 수 있음!!!

[자료구조]
- Stack<Character> stack = new Stack<>() : 문자열의 한 문자를 char형태로 push

[프로세스]
- 문자열 순회
① stack이 비어있지 않고(empty), stack의 상단 요소(peek)가 target 문자와 같다면 : 상단 요소 제거(pop)
② 그렇지 않다면 : target 요소 추가(push)
- stack이 비어있으면 1, 아니면 0 return

 

3. 참고사항

(1) 자료 구조의 선택

- 처음 나의 시도 : String의 substring과 인덱스를 통해 수행

→ 과정 복잡 & 시간복잡도 문제 발생

- 직전의 문자와의 비교에 집중하여 Stack 자료구조를 생각할 수 있어야 된다!!!

 

(2) 시간복잡도 : O(n)

- 문자열의 길이만큼 1번만 순회하면 된다.

 

 

4. 코드

import java.util.*;
class Solution
{
    public int solution(String s)
    {
        int answer = 0;
        //중복되면 제거 __ 적절한 자료구조 쓰기 - Stack(같은면 제거)
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            char target = s.charAt(i);
            if(!stack.empty() && stack.peek() == target){
                stack.pop();
            }else{
                stack.push(target);
            }
        }
        if(stack.empty())   answer = 1;
        return answer;
    }
}