728x90
문제
A와 B로만 이루어진 문자열이 주어졌을 때
같은 글자끼리 선을 그어 교차하지 않고 모두 맞아떨어지는 경우
주어진 문자열을 좋은 단어라고 판단하고
좋은 단어가 몇개인지 출력하는 문제
접근 방식
좋은 단어에 대한 설명이 헷갈릴 수 있는데 아래와 같다.
AABB (O)
ABBA (O)
ABAB (X)
알 수 있는 사실은 연속해서 존재하거나 중간에 다른 단어의 선과 겹치면 안 된다는 건데
같은 경우 빼주고 같지 않은 경우는 넣어주면 되므로 스택을 사용하면 쉽게 풀 수 있다.
ABBA 같은 경우만 신경 써서 풀면 되는 문제로
아래와 같은 순서로 실행되는 코드를 짜면 된다.
Stack<Character> stack = new Stack<>();
// ABBA
stack.push('A'); // stack(A)
peek() == 'B'; // 'A' == 'B'
stack.push('B'); // stack(A, B)
peek() == 'B'; // 'B' == 'B'
stack.pop(); // stack(A)
peek() == 'A'; // 'A' == 'A'
stack.pop(); // stack()
위와 같은 과정을 거치면 좋은 단어인 경우에는
스택에 아무런 값도 남지 않기 때문에
스택이 비었을 때 좋은 단어의 카운트를 1씩 증가시켜 주면 된다.
풀이
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int result = 0;
for (int i = 0; i < n; i++) {
char[] word = br.readLine().toCharArray();
Stack<Character> stack = new Stack<>();
for (char c : word) {
if (stack.isEmpty()) {
stack.push(c);
} else {
char top = stack.peek();
if (top == c){
stack.pop();
} else {
stack.push(c);
}
}
}
if (stack.isEmpty()) {
result++;
}
}
System.out.println(result);
}
}
'Java > Algorithms' 카테고리의 다른 글
[백준] 2504번 : 괄호의 값 (1) | 2023.10.08 |
---|---|
[백준] 10799번 : 쇠막대기 (0) | 2023.10.07 |
[백준] 4949번 : 균형잡힌 세상 (0) | 2023.10.05 |
[백준] 5430번 : AC (1) | 2023.10.04 |
[백준] 1021번 : 회전하는 큐 (0) | 2023.10.04 |