[Programmers] Lv2 짝지어 제거하기 Java

문제 출처

[프로그래머스 코딩 테스트 연습]

https://school.programmers.co.kr/learn/courses/30/lessons/12973

프로그래머스

 

문제 풀이

 

자료형 정하기

이 문제는 스택으로 풀 수 있다.

스택이란 다음그림과 같이 더하고 삭제할 수 있는 자료구조이다.

주의할 점은 한쪽 방향으로만 입력과 출력이 이뤄진다는 것이다.

!주의 4번째와 같이 underflow 즉 자료형에 없는데 출력을 하려는 경우가 생길 수 도 있다!

 

Stack의 기초적인 함수의 설명

 

스택을 왜 사용할까?

abaabaaa를 보자.

우선 같은 것을 찾아야 하니 처음부터 검사해야 한다.

1. a를 찾고 다음에 b를 비교한다. a와 b가 다르므로 넘김 → abaabaaa
2. b를 찾고 다음에 a를 비교한다. b와 a가 다르므로 넘김 → abaabaaa
3. a를 찾고 다음에 a를 비교한다. a와 a가 같으므로 제거!! → abbaaa

이때 다음은 무엇을 검사해야 할까?

파란색 문자열의 가장 오른쪽을 검사해야 한다.

즉 검사한 순서의 반대로 검사를 해야 한다.

이처럼 스택은 원래 있던 방향을 뒤집는데 유용하다.

그런 의미로 스택을 생성하자!

이때 자바의 스택을 이용해도 되지만 알고리즘 공부의 의미로 char형으로 스택을 만들었다.

char[] stack = new char[s.length()];
int sp = -1;

int sp는 스택의 쌓여 있는 정도를 의미하고

int sp = -1; 은 스택에 아무것도 없음을 의미한다.

스택의 크기는 검사할 때 최고 길이는 문자열의 길이이므로 s.length()로 한다.

스택의 최상단 요소의 접근은 stack[sp]로 가능하다.

스택의 추가는 stack[++sp] = 요소;로 가능하다.

스택의 최상단 요소를 제거는 stack[sp--] = ‘\0’;로 가능하다.

 

스택을 이용한 단계별 정리

위 그림을 단계별로 정리하면 다음과 같다.

1. 문자열 수만큼 다음 2와 3을 반복한다.
2. stack이 비어 있거나 스택의 가장 위에 있는 것과 검사대상과 다르면 스택에 검사 대상을 넣는다.
   → sp == -1 || stack[sp] ≠ 검사대상이면 stack[++sp] = 검사대상;
3. stack에서 하나를 가져와서 검사할것검사할 것이같다면 stack에서 값 하나를 뺀다.
   → stack[sp] == 검사대상이면 stack[sp--] = ‘\0’; ## ‘\0’는 null 문자를 의미 → 최상단 제거를 뜻함
4. 이후 stack에 아무것도 없으면 1을 stack에 값이 있다면 0을 반환한다.

 

스택을 이용한 단계별 그림

위에 대해 설명이 제대로 이해가 안 될 수 도 있으니 그림으로 정리했다.

 

단계별 예시에서는 “aaca”에 대해서 예시를 든다.

 

0. “aaca” 에서 index 0(a)를 가져온다. 그리고 스택이 비어있으므로 (sp 가 -1) 스택에 넣는다.

 

0번째 단계 그림

1. “aaca” 에서 index 1(a)를 가져온다. 그리고 스택의 가장 위가 a(stack[sp])로 a(index: 1)과 같으므로 스택에서 가장 최상단을 뺀다.

 

1번째 단계 그림

2. “aaca” 에서 index 2(c)를 가져온다. 그리고 스택이 비어있으므로 (sp 가 -1) 스택에 넣는다.

 

2번째 단계 그림

3. “aaca” 에서 index 3(a)를 가져온다. 그리고 스택의 가장 위가 c(stack[sp])로 a(index: 3)와 다르므로 스택에 넣는다.

 

3번째 단계 그림

4. stack이 남아 있므로 짝지어 제거하기가 되지 않는다.

 

소스 코드

public class Solution {

    public int solution(String s)
    {
        char[] stack = new char[s.length()];
        int sp = -1;

        char[] stack = new char[s.length()]; // 검사할때 최고 길이는 문자열의 길이, 모든 요소는 '\0'으로 초기화 됨
        int sp = -1;   // 스택의 쌓여진 정도 및 스택의 비어 있음을 의미

        for (int i = 0; i < s.length(); i++) // 검사할 문자열을 반복
            if (sp == -1 || stack[sp] != s.charAt(i)) // 스택이 비어있거나 스택요소와 검사 대상이 다를 경우
                stack[++sp] = s.charAt(i); // 스택 생성
            else if (stack[sp] == s.charAt(i)) // 스택요소와 검사 대상이 같을 경우
                stack[sp--] = '\\0'; // 스택 최상단 요소 제거

        return sp < 0 ? 1 : 0;
    }
}