[백준(Baekjoon)] 2493. 탑

 

[백준(Baekjoon)] 2493. 탑

 

2493번: 탑

 

 

 

[입력]

 

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.

 

 

[출력]

 

첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.

 

[풀이]

 

배열로 코드를 짜게 되면 시간초과가 발생하므로 스택을 이용해준다.

스택을 두개이용해서 하나는 탑 층을 저장, 하나는 그 탑의 인덱스(몇번째탑인지) 저장했다.

처음에 빈 스택에는 <6, 1> 이 들어간다.

그후 <9, 2> 이 들어가려면 스택이 비었는지 검사하고 안비어있으면 peek하여 제일 위에 있는 6과 현재 9를 비교한다.

9가 더 크므로 스택에 있는 6을 pop한다. 또 비교하여 9보다 작은것은 모두 pop한다.

이 과정을 거친 후 스택에 아무것도 남아 있지 않으면 모두 9보다 작아서 없어진 것이므로 0을 출력하고,

스택에 무엇이라도 남아있으면 그것은 9보다 큰 탑이므로 그것의 인덱스를 출력한다.

그럼 스택에는 <9, 2>만 남는데 여기서 <5, 3>이 들어가려면

9와 비교후 5가 더 작으니까 peek하여 (pop X) 9의 인덱스만 출력하고 <5, 3>을 push한다.

 

 

 

 

public class algo2493 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //Scanner 대신 실행시간이 적은 BufferedReader 사용.
        
		Stack<Integer> s = new Stack<>(); //탑의 높이
		Stack<Integer> sidx = new Stack<>(); //탑의 인덱스
		
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		for (int i = 0; i < n; i++) {
			int data = Integer.parseInt(st.nextToken());
			if(s.isEmpty()) { //비어 있으면 비교 대상 없으므로 push후 0 출력
				s.push(data);
				sidx.push(i+1);
				System.out.print("0 ");
			}else {
            	// 현재 탑보다 스택에 있는 탑이 더 작으면 작은 탑들 pop하고 큰 탑 push
				if(s.peek() < data) { 
					while(!s.isEmpty() && s.peek() < data) {
						s.pop();
						sidx.pop();
					}
					System.out.print((sidx.isEmpty()?"0":sidx.peek()) + " ");
					s.push(data);
					sidx.push(i+1);
                    
                // 스택에 있는 탑이 현재탑보다 크면 그 탑 인덱스 출력 후 현재탑 push
				}else if(s.peek() >= data){
					System.out.print(sidx.peek() + " ");
					s.push(data);
					sidx.push(i+1);
				}
			}
		}
		
		
	}

}

 

 

메모리	시간	언어	코드 길이
149256	3840	Java 11	1058