[BOJ] 백준 1316 그룹 단어 체커 (Swift)

문제

https://www.acmicpc.net/problem/1316

1316번: 그룹 단어 체커

풀이

Stack을 사용하면 쉽게 풀 수 있는 문제 입니다.
입력받은 단어에 대해 하나씩 확인하면서 스택에 넣어줍니다.

만약 Stack이 비어있지 않고, 스택의 꼭대기의 값이 현재 들어올 문자와 같다면 스택을 pop 해줍니다.

그 이후 스택에 현재 들어올 문자를 넣어줍니다.

그렇다면 ccazzzzbb 문자열이 들어온다면 어떤식으로 동작할까요?

스택이 비어있기 때문에 c가 stack에 들어오겠군요.

그 다음 문자인 c에 대해서 처리해주겠습니다.

지금 스택이 비어있지 않고, 스택의 꼭대기 값(c)이 현재 들어올 문자(c)와 같기 때문에 스택의 꼭대기 값을 삭제시켜줍니다.

그 이후 현재 들어올 문자(c)를 스택에 넣어줍니다.

다음 a를 처리해주겠습니다.

스택이 비어있지 않지만, 스택의 꼭대기 값(c)이 현재 들어올 문자(a)와 다르기 때문에

스택에는 a를 삽입합니다.

z도 마찬가지겠죠?

그 다음 다음... 최종적으로는 다음과 같이 스택에 값들이 들어있을 것입니다.

이제 이 스택을 집합 자료형으로 바꾼 것의 요소의 갯수와, 현재 스택의 요소의 갯수와 비교해주겠습니다.

만약 같다면 그룹 단어일 것이고, 다르다면 그룹 단어가 아닐 것이에요.

현재는 스택의 크기가 4이고, 집합 자료형으로 바꿔도 4이기 때문에 ccazzzzbb는 그룹 단어 입니다.

만약 여기서 c가 하나 더 들어온다면 어떻게 될까요?

스택의 크기는 5이고, 집합 자료형으로 바뀐다면 크기가 4가 됩니다.
따라서 그룹 단어가 아닌것을 판별할 수 있습니다.

이것을 코드로 구현해보겠습니다.

소스코드

후기

문제를 보고 연속된 문자열을 압축해야한다는 느낌이 들어서 스택 자료형을 떠올리게 되었습니다.
그 이후 떨어져서 나타나는 것을 확인하기 위해서 집합 자료형을 떠올렸습니다.

이 스택과 집합에 대해 떠올렸다면 쉽게 풀 수 있는 문제인 것 같습니다.