백준 3986번: 좋은 단어 - Swift 풀이

오늘의 문제

3986번: 좋은 단어

요약) 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 함. 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'. 입력된 단어들 중에 '좋은 단어'가 몇 개 있는지 세서 출력하면 됨.

 

내 풀이

import Foundation

/// 단어의 수 입력
let N = Int(readLine()!)!
/// 좋은 단어의 개수
var result = 0
/// 교차점이 있는지 확인하기 위해 스택 사용
var stack: [Character]

for _ in 0..<N {
    // 단어 새로 받을 때마다 스택 초기화
    stack = []
    var letter = readLine()!
    // 1-1. 글자수가 홀수면 쌍이 맞을 수가 없다
    if letter.count % 2 == 0 {
    	// 1-2. A와 B로만 이루어진 글자이기 때문에 A끼리 쌍, B끼리 쌍이 맞으려면
        // A와 B의 개수도 각각 짝수 개여야 한다 -> A만 모아서 짝수가 맞는지 확인
        let ALetter = letter.filter { character in
            character == "A"
        }
        // 1-3. A 개수도 짝수, B 개수도 짝수면 일단 글자끼리의 쌍은 무조건 이룰 수 있다
        if ALetter.count % 2 == 0 {
            // 2-1. 이제 선끼리 교차하는지만 확인하면 됨 -> 스택 사용
            for l in letter {
            	// 스택의 탑과 현재 글자가 같은지 확인
                if stack.last == l {
                    // 같으면 스택의 탑 제거
                    stack.removeLast()
                } else {
                    // 다르면 해당 글자를 스택에 추가
                    stack.append(l)
                }
                // 현재 글자도 제거
                letter.removeFirst()
            }
            // 2-2. 글자 전부 확인했는데 스택이 비어있으면 교차점이 없다는 뜻이라서 좋은 단어로 인정
            if stack.isEmpty {
                result += 1
            }
        }
    }
}

print(result)

 

생각했던 로직

1. 모든 글자가 쌍이 존재하는지 확인 (쌍 없는 게 있으면 이미 좋은 단어에서 탈락)

2. 그 쌍들이 교차점이 없는지 확인

-> 1번 만족하는 것들 중에 2번까지 만족하는 것이 좋은 단어이다.

 

일단 1번은 모든 글자가 쌍이 있으려면 단어의 총 글자 수가 짝수여야 하고, 추가적으로 A도 짝수, B도 짝수여야 한다. 총 글자 수가 짝수여도 A 3개, B 3개 이러면 쌍이 안 맞아지기 때문이다.

여기까지는 코드로 구현을 했는데 2번 로직을 어떻게 구현하느냐가 문제였다. 잘 모르겠어서 알고리즘 분류를 확인했는데 '스택'이라고 적혀있었다. 스택...? 이게 교차하는지 아닌지를 스택으로 어떻게 검증하지.

 

핵심 포인트

나는 입력으로 들어온 letter 자체가 (이제 생각해보니 word가 더 적절한데 왜 저렇게 지었지) 문자'열', 즉 스택 구조로 보고 여기서 마지막 글자를 하나씩 pop하면서 확인할 생각을 갖고 계속 접근했는데 음... 이런 게... 스택...? 뭐 이런 생각이 들었고 교차하는 지점 찾는 과정에서 스택의 활용법을 전혀 모르겠어서 헤맸다. 다행히 친구가 좋은 아이디어를 줘서 풀 수 있었다.

 

바로... 스택에 글자를 하나씩 추가하는 방식으로 생각하는 것이다.

빼는 것이 아니라 stack 변수를 하나 두고 거기에 단어의 글자를 하나씩 추가한다.

스택의 top과 새로 추가된 글자가 쌍이 맞으면(= 같은 글자면) 그 쌍은 스택에서 제거한다.

쌍이 맞지 않으면 (= 다른 글자면) 그 두 글자는 스택에 보관된다. 마지막에 추가된 글자가 스택의 새로운 top이 된다.

이것을 단어의 모든 글자를 확인할 때까지 반복하면 된다.

모든 글자를 확인했을 때 스택이 비어있으면 '좋은 단어'이고, 글자가 쌓여있으면 '좋은 단어'가 아니다.

 

예시로 좋은 단어가 아닌 A B A B의 경우,

1. 단어의 첫 글자와 스택의 top이 다르면 스택에 첫 글자 추가

- 단어 첫 글자는 A, 스택의 top은 nil -> A를 스택에 추가

스택 : A

단어 : B A B

- 단어 첫 글자는 B, 스택의 top은 A  -> B를 스택에 추가

스택 : A B

단어 : A B

- 단어 첫 글자는 A, 스택의 top은 B  -> A를 스택에 추가

스택 : A B A

단어 : B

- 단어 첫 글자는 B, 스택의 top은 A  -> B를 스택에 추가

스택 : A B A B

단어 : 

-> 결국 단어의 모든 글자를 확인했지만, 스택은 비어 있지 않고 쌓여있다. 그럼 이 단어는 쌍이 존재는 하지만 선을 이었을 때 서로 교차되는 쌍으로(사이에 다른 단어가 있으니까), '좋은 단어'가 아닌 것이다.

 

좋은 단어인 A B B A로 해보자.

- 단어 첫 글자는 A, 스택의 top은 nil -> A를 스택에 추가

스택 : A

단어 : B B A

- 단어 첫 글자는 B, 스택의 top은 A -> B를 스택에 추가

스택 : A B

단어 : B A

- 단어 첫 글자는 B, 스택의 top은 B -> B-B 쌍이 맞기 때문에 둘 다 제거

스택 : A

단어 : A

 - 단어의 첫 글자는 A, 스택의 top은 A -> A-A 쌍이 맞기 때문에 둘 다 제거

스택 : 

단어 :

-> 모든 글자를 확인했고, 스택도 비어 있는 상태이다. 그렇기 때문에 이 단어는 교차되는 지점도 없는 '좋은 단어'인 것이다.

 

그래... 이런 게 바로 스택을 사용한 알고리즘 문제였지.

정말 알고리즘은 쉬면 다 까먹는 것 같다.

 

다시 기초부터 차근차근, 욕심내지 말고 한번에 몰아서 하지 말고 조금씩 꾸준히!

오히려 좋아 마인드 ON입니다.