오늘의 키워드
•
스택
•
단순 구현
문제 파악 및 풀이
•
문제를 읽고 스택을 활용해야 한다는 사실을 미리 알게 되어 스택 기반으로 풀었다.
•
')'를 만나면 레이저인지 막대기의 끝인지 판단해야 한다.
•
레이저(())를 만나면 현재 쌓여 있는 막대기의 수만큼 조각이 추가된다.
•
막대기의 끝()))을 만나면 조각이 하나 추가된다.
풀이 코드
import java.io.*;
import java.util.*;
class Main {
public static final int MAX_CNT = 100000;
public static int ans;
public static Stack<Character> stack = new Stack<>();
public static void main(String[] args) throws IOException {
// 입력
init();
int cnt = 0;
while (!stack.empty()) {
char c = stack.pop();
if (c == ')') {
// 막대기의 끝인 경우
if (stack.peek() == ')') {
cnt++;
} else {
// 레이저인 경우
stack.pop();
ans += cnt;
}
} else {
// 막대기의 시작
cnt--;
ans++;
}
}
System.out.println(ans);
}
public static void init() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
stack.push(c);
}
}
}
Java
복사
시간 복잡도
•
O(N)
•
입력 문자열을 한 번만 순회하고, 스택 연산(삽입/삭제)도 O(1) 시간 내에 처리되기 때문에 전체 시간 복잡도는 O(N)이다.
오늘의 회고
어려웠던 점
•
문제를 풀기 전에 이미 스택을 사용해야 한다는 정보를 알아버려서 순수한 사고로 접근하지 못한 점이 조금 아쉬웠다.
•
막대기의 시작과 끝, 레이저를 구분하는 조건을 처음에 헷갈릴 수 있었다.
개선점
•
스택이 아닌 큐로도 풀 수 있지 않을까? 하는 의문이 들었는데, 막대기의 구조를 '가장 마지막에 들어온' 괄호와 바로 비교해야 하므로 스택이 훨씬 자연스럽다.
•
큐는 FIFO(First-In-First-Out) 구조라 현재 필요한 LIFO(Last-In-First-Out) 상황과 맞지 않는다.
•
앞으로도 문제를 읽었을 때 자료구조를 유추할 수 있는 직관력을 꾸준히 키우고, 가능하다면 다른 방식(예: 스택 없이 단순 카운팅)으로도 풀이를 시도해보자.