1. 문제 링크 및 문제
문제요약
서로 다른 N개의 탑이 왼쪽으로 레이저를 쏠 때, 제일 먼저 만나는 단 하나의 탑에서만 수신 가능
탑들의 개수 N과 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지 구하라
앞이 자기보다 작을 때는 더 앞으로 가능, 더 크면 return
2. 해결 방법 생각해보자 ...
해결방법 ( 시간제한 1.5초, N은 1 이상 500,000 이하 , 탑들의 높이는 1 이상 100,000,000 이하)
- 이진탐색? 자신의 앞에 값이랑 비교해야하는데.. 이진탐색은 정렬되어 있는 알고리즘에서 특정한 값을 찾는 알고리즘..
- ✓ LIFO 스택 자료구조 활용
3. 코드
import java.util.*;
import java.io.*;
public class Main{
static int N ; // 탑의 수
public static void main(String args[]) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(br.readLine());
Stack<int[]> stack = new Stack<>();// 탑들의 높이를 저장할 스택
StringTokenizer st = new StringTokenizer(br.readLine());
for(int idx=1;idx<N+1;idx++){ // 자신의 왼쪽값만 비교하므로, 값을 입력받으며 풀이 가능
int h = Integer.parseInt(st.nextToken());
while(!stack.isEmpty()){
if(stack.peek()[1] >= h){
sb.append(stack.peek()[0] + " ");
break;
}
stack.pop();
}
if(stack.isEmpty()) sb.append("0 ");
stack.push(new int[] {idx,h}); // 현재 인덱스와 높이 삽입
}
System.out.println(sb.toString());
}
}상세설명
자신의 왼쪽에 있는 값만 비교하면 되므로 값을 받으면서 풀이하며,
값이 들어왔을 때 저희가 해야할 일은 2가지입니다.
1. 자신의 앞의 값들과 비교하여, 먼저 만나는 레이저 확인
- 1-1 저장해둔 값이 없을 때 == 0
- 1-2 저장해둔 값이 있을 때
- 1-2-1. 자신의 앞의 값의 높이 > 자신의 높이 라면 만난 것이므로, 앞의 값 인덱스를 출력
ex) 3,6,4 가 있고 5가 들어왔다고 가정했을 때, 6 이 더 크므로 5는 6과 만납니다. 6은 두번째에 있으므로 2 를 출력 - 1-2-2. 자신의 높이가 더 크다면, 앞의 값은 더 이상 사용될 일이 없습니다. -> 저장해둔 값에서 뺌
ex) 3,4,5 가 있고 6 이 들어왔다고 가정했을 때, 6에 부딪히면 3,4,5는 갈 수 없으므로 더 이상 사용될 일이 없습니다
- 1-2-1. 자신의 앞의 값의 높이 > 자신의 높이 라면 만난 것이므로, 앞의 값 인덱스를 출력
2. 다음 값이 들어왔을 때 비교해야하므로, 값을 저장해둠
해결 과정 끝입니다. 단순하지요?
이제 코드로 구현해야하는데, 자신의 앞의 값들을 사용한다.
즉, 마지막에 들어온 값들을 먼저 확인하는 것 입니다.
유명한 자료구조 Last In First Out 인 STACK 을 사용해줍니다.
따라서 코드는 이렇게 됩니다.
for(int idx=1;idx<N+1;idx++){ // 자신의 왼쪽값만 비교하므로, 값을 입력받으며 풀이 가능
int h = Integer.parseInt(st.nextToken());
while(!stack.isEmpty()){ // 1-2. 저장해둔 값이 있을 때 ?
if(stack.peek()[1] >= h){ // 1-2-1. 앞의 값이 더 크다면
sb.append(stack.peek()[0] + " "); // 만났으므로 출력하고
break; // 해당 while문을 나갑니다
}
stack.pop(); // 1-2-2. 자신의 높이가 더 크다면, 앞의 값은 제거해줍니다.
}
if(stack.isEmpty()) sb.append("0 "); // 1-1. 스택이 비었을 때
stack.push(new int[] {idx,h}); // 2. 현재 값을 저장
}역시나 말로만 보면 어렵지요.
백준예시1을 통해 stack 이 어떻게 작동되는 지 살펴봅시다.
- 예시값들을 이렇게 표현해보았습니다.
6, 9, 5, 7, 4 순서대로 들어오므로
1. 6 인 경우
현재 스택은 비어있으므로
- 0 을 출력하고
- stack에 현재 값을 저장해줍니다. (인덱스, 높이) (1,6)
(출력해야 하는 값이 만난 탑의 번호이므로, 인덱스도 함께 저장해줍니다 )
2. 9 인 경우
스택에 6이 있으므로
-
현재 높이 ( = 9 ) 와 , 스택의 마지막 높이 ( = 6 ) 를 비교합니다.
- 현재 높이가 더 크므로, 이제 9 라는 벽에 부딪혀 6은 아무도 만날 수 없습니다. 6을 제거합니다.
- 그럼 스택이 비었으므로, while 문을 빠져나가고 0 출력
-
자신의 값을 stack에 저장해줍니다 (인덱스, 높이) ( 2, 9 )
stack에서 6을 제거하였지만, 흐름을 보기 위하여 완전 삭제하지 않고, pop 표시를 해두었습니당
3. 5 인 경우
스택에 9 가 있으므로
- 현재 높이( = 5 )와, 스택의 마지막 높이 ( 9 ) 를 비교합니다.
- 스택의 높이( 9 ) 가 더 크므로, 스택의 인덱스 ( 2 ) 를 출력하고 while문을 빠져 나갑니다.
- 자신의 값을 stack에 저장해줍니다 (인덱스, 높이) (3,5)
4. 7인 경우
스택에 9,5 가 있으므로
- 현재 높이( = 7 )과 , 스택의 마지막 높이 ( = 5 ) 를 비교합니다.
- 현재 높이가 더 크므로, 이제 5 는 7 이라는 벽에 부딪혀 아무도 만날 수 없습니다. 5를 제거합니다.
- 이번에는 , 스택에 아직도 값이 남아있네요.
(while문 조건으로 stack이 빌 때 까지 진행하거나, break 를 만났을 때 동작을 멈춥니다.)
- 그럼 다시 현재 높이 ( = 7 ) 과, 스택의 마지막 높이 ( = 9 ) 를 비교합니다.
- 스택의 높이 ( 9 ) 가 더 크므로, 스택의 인덱스 ( 2 ) 를 출력하고 while문을 빠져 나갑니다.
- 자신의 값을 stack에 저장해줍니다 (인덱스, 높이) (4,7)
5. 4 인 경우
스택에 9,7 이 있으므로
- 현재 높이( = 4 )과 , 스택의 마지막 높이 ( = 7 ) 를 비교합니다.
- 스택의 높이 ( 7 ) 가 더 크므로, 스택의 인덱스 ( 4 ) 를 출력하고 while문을 빠져 나갑니다.
- 자신의 값을 stack에 저장해줍니다 (인덱스, 높이) (4,5)
끝났습니다.
출력한 순서대로 0 0 2 2 4 가 나왔습니다!
끝나니 STACK 밑에 출력값도 같이 적어두었으면 참 좋겠다 싶네요..
이해에 도움이 되었길 바라며~💡
