[ 백준 ] 3986 - 좋은 단어(with.Java)

💡문제 분석 요약

-- 문제 --

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

입력 : 첫째 줄에 단어의 수 N이 주어진다. (1 ≤ N ≤ 100), 다음 N개 줄에는 A와 B로만 이루어진 단어가 한 줄에 하나씩 주어진다

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

💡알고리즘 설계

1. Stack : peek로 확인 후 다르면 넣고 같으면 빼기 → 스택 size가 0이면 좋은 단어

💡코드

package backjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.charset.Charset;
import java.util.Stack;

public class BackJoon3986 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int count=0;
        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            Stack<Character> stack = new Stack<>();
            for (int j = 0; j < s.length(); j++) {
                char c = s.charAt(j);
                if (stack.isEmpty()) {
                    stack.push(c);
                } else if (stack.peek() == c) {
                    stack.pop();
                }else {
                    stack.push(s.charAt(j));
                }
            }
            if (stack.isEmpty()) {
                count++;
            }
        }
        System.out.println(count);
    }

}

💡시간복잡도

O(N*N)

💡틀린 이유

💡틀린 부분 수정 or 다른 풀이

💡느낀점 or 기억 할 정보

1. charAt : 문자열을 문자로 바꿔주는 함수