백준 3986 좋은 단어

평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 평석이가 '좋은 단어' 개수를 세는 것을 도와주자.

입력

첫째 줄에 단어의 수 N이 주어진다. (1 ≤ N ≤ 100)

다음 N개 줄에는 A와 B로만 이루어진 단어가 한 줄에 하나씩 주어진다. 단어의 길이는 2와 100,000사이이며, 모든 단어 길이의 합은 1,000,000을 넘지 않는다.

출력

첫째 줄에 좋은 단어의 수를 출력한다.

 

 

 

처음 풀이

좋은 단어의 조건 : 한글자와 한글자 사이에는 짝수개가 있어야 한다. 홀수개이면 안된다.

 

1. 한줄씩 검사하면서 다음의 그 같은 단어가 나올때까지 몇칸인지 검사한다. 홀수면 false.

2. 그다음 문자부터 동일하게 반복.

 

현단어와 같은 인덱스가 처음으로 나오는걸 찾고, 그 길이를 체크.

단어 1개에 대해서만 그다음 인덱스까지의 간격이 0이거나 짝수인지만 본다면 되지 않을까?

 

대칭이 되야 된다고 생각한다면?

계속 양끝단 인덱스를 구해서 차이를 구한다면?

 

 

마지막 아이디어는

서로 대칭이 되어야 될 것이므로

절반을 잘라서 절반에 대해 AB 위치만 바꾼다면 나머지 절반과 같을 것이다라는 생각이었다.

import java.io.*;

public class GoodWord3986 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int wordNumber = Integer.parseInt(br.readLine());
        int count = 0;
        for (int i = 0; i < wordNumber; i++) {
            String a =br.readLine();
            String b = a.substring(0, a.length()/2);
            String c = a.substring(a.length()/2);

            b = b.replaceAll("A","_");
            b = b.replaceAll("B","A");
            b = b.replaceAll("_","B");

            if(b.equals(c)) {
                count++;
            }
        }
        bw.write(count);
        bw.flush();
        bw.close();
        br.close();
    }
}

 

그러나 시간초과로 실패.

 

 

 

2번째 풀이

다른 풀이를 보니 스택 문제라고 한다.

첫단어를 스택에 넣고

스택의 peek와 같으면 pop, 다르면 push 하는 식.

 

왜 이게 스택문제일까?

 

gpt를 같이 보니 

아래와 같이 좋은 답변이 많다.

 

이번 문제는 대칭을 이루는 구조였기 때문이다.

생각해보면 같은 2개의 문자 안에는 0이거나 짝수만 들어가야 되기 때문에.

✅ 스택 문제로 의심할 수 있는 전형적인 패턴

1. 최근에 들어온 값부터 처리해야 할 때 (LIFO)
   → "가장 나중에 들어온 것"을 먼저 꺼내야 할 경우
   → 예: 괄호 검사, 수식 계산, 되돌리기(undo), 이전 상태 복원 등
2. 중첩 구조 or 쌍을 이루는 구조 → 괄호 짝 맞추기 (()()), HTML/XML 태그 짝 확인 등
   → 열린 기호가 닫히는 시점을 정확히 알고 싶을 때
3. "이전보다 큰/작은 값"을 찾을 때 (단조 스택 활용)
   → 오큰수, 오르막길, 주식 가격, 히스토그램에서 최대 직사각형 면적
   → "이전 값들과 비교해서 조건에 맞는 걸 찾아야 할 때"
4. 재귀를 반복문으로 바꿔야 할 때 → DFS 구현 시 스택을 사용할 수 있음
   → 수식 파싱, 컴파일러 구현 문제 등
5. 문자열 또는 배열의 순서를 바꾸거나 꺼내서 다시 넣을 때 → 문자 제거 문제 (e.g., 폭발 문자열), 반복 제거 문제 등

---

🧠 스택 여부를 판단하는 실전 체크리스트

• ⬜️ "최근에 넣은 값을 먼저 처리해야 한다"는 조건이 있나?
• ⬜️ 쌍을 이루는 요소(열고 닫기)가 있나?
• ⬜️ 이전 값들과 비교하면서 순서를 유지해야 하나?
• ⬜️ 중간 계산 결과를 저장해뒀다가 나중에 써야 하나?
• ⬜️ 재귀적인 구조를 반복문으로 바꿔야 하나?

 

 

 

https://propercoding.tistory.com/20

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int wordNumber = Integer.parseInt(br.readLine());

        for (int i = 0; i < wordNumber; i++) {
            String word = br.readLine();
            wordCheck(word);
        }
        System.out.println(count);
        br.close();
    }

    private static void wordCheck(String word) {
        if (word.length() % 2 == 1) {
            return;
        }
        Character firstWord = word.charAt(0);
        Stack<Character> stack = new Stack<>();
        stack.push(firstWord);
        for (int i = 1; i < word.length(); i++) {
            if (stack.isEmpty()) {
                stack.push(word.charAt(i));
            } else if(word.charAt(i) == stack.peek()) {
                stack.pop();
            } else {
                stack.push(word.charAt(i));
            }
        }
        if (stack.isEmpty()) {
            count++;
        }
    }
}