https://www.acmicpc.net/problem/3986
처음 봤을 때는 문자열 조작 문제로 생각했다.
그래서 일단 문제에서 원하는 패턴을 여러가지 생각해보았다.
가장 간단한 패턴으로 AABB / BBAA와 ABBA / BAAB 를 생각했다.
이 둘의 조합을 사용하여 ABAABA / BABAABABAA 와 같은 패턴을 만들어낼 수 있었다.
패턴을 가만히 살펴보니, 자료구조에서 배웠던 postfix, infix expression이 떠올랐다.
이는 stack을 이용해서 구현할 수 있었다.
그래서 2개의 stack을 이용해서 문제를 풀었다.
import java.io.*;
import java.util.Stack;
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 cnt = 0;
for (int i = 0; i < n; i++) {
Stack<Character> stack = new Stack<>();
Stack<Character> pairStack = new Stack<>();
for (byte val : br.readLine().getBytes()) {
stack.push((char) val);
}
for (int j = stack.size(); j > 0; j--) {
if ((!pairStack.empty()) && (pairStack.peek() == stack.peek())) {
pairStack.pop();
stack.pop();
} else {
pairStack.push(stack.pop());
}
}
if (pairStack.empty()) {
cnt++;
}
}
System.out.println(cnt);
}
}
그런데 다른 제출자들의 Java 실행시간을 보니, 300ms대가 아닌 200ms대가 나오는 경우도 있었다.
🤔🤔🤔🤔
Scanenr를 사용하지 않았기 때문에 IO의 문제가 아닌, 알고리즘 구조의 문제라고 판단했다.
내 코드를 천천히 다시 살펴보니 stack을 2개나 사용할 필요가 없다는 걸 깨달았다.
pairStack을 사용하는 대신, getBytes로 char을 하나씩 가져올 때, 비교를 해도 되기 때문이었다.
import java.io.*;
import java.util.Stack;
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 cnt = 0;
for (int i = 0; i < n; i++) {
Stack<Character> stack = new Stack<>();
for (byte val : br.readLine().getBytes()) {
Character ch = (char) val;
if ((!stack.empty()) && (stack.peek() == ch)) {
stack.pop();
} else {
stack.push(ch);
}
}
if (stack.empty()) {
cnt++;
}
}
System.out.println(cnt);
}
}
'1Day 1Algo' 카테고리의 다른 글
[백준/BOJ] 1931번 : 회의실 배정 - Java(자바) (0) | 2022.03.04 |
---|---|
[백준/BOJ] 9020번 : 골드바흐의 추측 - Java(자바) (0) | 2022.02.19 |
[1Day 1Algo] 백준 1065번 한수 (JAVA) (0) | 2022.01.10 |
[1Day 1Algo] 백준 1110번 더하기 사이클 (Python) (0) | 2022.01.05 |
[1Day 1Algo] 백준 12865번 평범한 배낭 (C++) (0) | 2021.11.21 |