https://www.acmicpc.net/problem/1874
1874번: 스택 수열
1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.
www.acmicpc.net
분류 : 스택
더보기
import java.io.*;
import java.math.*;
import java.util.*;
public class Main {
static Myscanner sc = new Myscanner();
static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
public static void main(String[] args) throws IOException {
int N = sc.nextInt();
StringBuilder sb = new StringBuilder();
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = sc.nextInt();
}
int index = 0;
boolean check = true;
Stack<Integer> st = new Stack<>();
int num = 1;
while (index < arr.length) {
if (num <= arr[index]) {
st.push(num++);
sb.append("+" + "\n");
} else if (st.peek() == arr[index]) {
index++;
st.pop();
sb.append("-" + "\n");
} else {
check = false;
break;
}
}
if (!check) {
out.println("NO");
} else {
out.println(sb);
}
out.close();
}
}
class Myscanner {
BufferedReader br;
StringTokenizer st;
Myscanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine() {
String str = "";
try {
str += br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
문제 이름부터 스택을 써야 할 것 같은 문제이다.
그동안 문제 이해가 되지 않아서 계속 넘겨왔었는데 마음 잡고 풀어보자 하고서 시간 투자를 하였다.
index를 지정해놓고 num을 1부터 array [index] 보다 작거나 같을 때까지만 stack에 push를 하고
같을 경우에는 pop을 해주고 해당 인덱스는 더 이상 필요 없으니 index를 늘려준다.
특히, 시간 초과를 2번이나 당했는데 처음에는 q에 stack 처럼 넣고 나중에 출력하는 방식 -> 시간 초과,
두 번째는 String에 이어 붙여서 출력하는 방식 => 시간 초과, String을 이어 붙이는 방식은 O(N^2)이기 때문에
StringBuilder를 활용해야 한다.
'PS' 카테고리의 다른 글
[BOJ]1890번 : 점프 (0) | 2017.04.20 |
---|---|
[BOJ]1620번: 나는야 포켓몬 마스터 이다솜 (0) | 2017.04.19 |
[BOJ]1931번 : 회의실 배정 (0) | 2017.04.17 |
[BOJ]1600번 : 말이 되고픈 원숭이 (0) | 2017.04.14 |
[BOJ]9373번 : 복도 뚫기 (0) | 2017.04.06 |