티스토리 뷰
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 |
링크
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
TAG
- HTTP 완벽 가이드
- 가상 면접 사례로 배우는 대규모 시스템 설계 기초
- 이펙티브자바 아이템60
- js array
- 백준
- 백기선 스터디
- HTTP 완벽가이드
- JPA 연관관계 매핑
- 이펙티브자바 아이템59
- java
- js api
- BOJ
- Spring Security
- JS 딥다이브
- 모던자바스크립트
- 프로그래머스 SQL
- 김영한 JPA
- 이펙티브자바
- dreamcoding
- 김영한 http
- GCP
- js promise
- 드림코딩
- 이펙티브자바 스터디
- 킹수빈닷컴
- REST API
- 프로그래머스
- http
- ㅇㄷㅇㅈ
- 패스트캠퍼스 컴퓨터공학 완주반
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |
글 보관함