boj)2493 - 탑
2020. 10. 12. 13:02ㆍPS/boj
import java.io.*;
import java.util.*;
public class boj_2493 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static Stack<Razer> waiting = new Stack<>();
static Stack<Razer> pending = new Stack<>();
static StringTokenizer st;
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n+1];
st = new StringTokenizer(br.readLine());
ArrayList<Integer> list = new ArrayList<>();
// 스택에 반대로 쌓기
for (int i = 1; i <= n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
for (int i = n; i > 0; i--) {
waiting.push(new Razer(arr[i], i));
}
// 초기값
pending.push(waiting.pop());
list.add(0);
while (!waiting.isEmpty()) {
if (waiting.peek().height > pending.peek().height) { // 레이저가 닿지 못하는 경우
while (!pending.isEmpty() && (pending.peek().height < waiting.peek().height)) {
pending.pop(); // 닿을때까지 작은놈은 무시
}
if (pending.isEmpty()) { // 끝까지 못 찾음
list.add(0);
} else { // 어딘가에 닿았음
list.add(pending.peek().index);
}
} else { // 레이저가 바로 닿음
list.add(pending.peek().index);
}
pending.push(waiting.pop());
}
// 출력
for (Integer i : list) {
bw.append(i + " ");
}
bw.flush();
bw.close();
}
}
class Razer {
int height;
int index;
public Razer(int height, int index) {
this.height = height;
this.index = index;
}
}
(1) 나의 풀이
import java.io.*;
import java.util.*;
public class boj_2493 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
int N = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
Stack<Top> s = new Stack<>();
for (int i = 1; i <= N; i++) {
int h = Integer.parseInt(st.nextToken());
if (s.isEmpty()) {
sb.append("0 ");
s.push(new Top(h, i));
} else {
while (true) {
if (s.isEmpty()) {
sb.append("0 ");
s.push(new Top(h, i));
break;
}
Top top = s.peek();
if (top.height > h) {
sb.append(top.index + " ");
s.push(new Top(h, i));
break;
} else {
s.pop();
}
}
}
}
System.out.println(sb.toString());
}
}
class Top {
int height;
int index;
public Top(int height, int index) {
this.height = height;
this.index = index;
}
}
(2) 다른 풀이
굳이 뒤로 할 필요없이 앞에서부터 이렇게 할 수 있었음
생각이 안났다 ...
생각
- n의 범위가 크니까 for문으로 도는건 시간초과 -> 다른 자료구조 사용, 생각하다 보니까 스택을
뒤에서부터 넣는다면 맨 앞 탑에서부터의 레이저가 닿는 곳을 구하기 좋을거같다고 생각
근데 출력할때는 index의 값이 필요하니 따로 class를 만들어서 스택에 담음
탐색하다가 만약 나보다 낮은 탑을 만나면 이건 제거해도 상관이없음
왜냐면 현재 탑의 높이가 더 높기때문에 다음 탑에서 레이저를 발사해도 걸리는건 현재의 탑임
이런식으로 레이저가 탑에 걸리던가 pending stack이 빌때까지 pop해준다.
- emptystack 에러때문에 계속 걸렸는데 해결했음.
while문 사용하는게 아직도 머리가 빨리 안돌아간다 ...
- 뭔가 더 다듬을 수 있을거 같은데 ...
'PS > boj' 카테고리의 다른 글
boj)6198 - 옥상 정원 꾸미기 (0) | 2020.10.13 |
---|---|
boj)2164 - 카드2 (0) | 2020.10.12 |
boj)10773 - 제로 (0) | 2020.10.12 |
boj)1748 - 수 이어쓰기 1 (0) | 2020.09.22 |
boj)6064 - 카잉 달력 (0) | 2020.09.22 |