글 읽기 - 자바 stack에 관련된 질문입니다.

sange17 2년 전 0

스택을 배열로 직접 만들어 풀어보았지만 아래와 같이 입력에 대해서 옳바르지 않은 출력을 보입니다...

<입력1>

1 2 3 1 1 2 3

<출력1>

-1 1 1 1 -1 -1 -1

자바에서 제공하는 스택 클래스를 사용하여 풀어본 결과 위의 입력 예와 같이 입력하였을 때는 아래와 같이 옳바른 값이 출력됩니다.

<출력2>

-1 1 1 -1 -1 -1 -1

왜 직접 만든 스택과 스택 클래스에서 이러한 차이가 발생하는지 궁금합니다.

혹시 제가 틀리거나 놓치고 있는 부분이 있는 것인가요..?

아래 주석 처리되지 않은 코드는 스택을 배열로 직접 만들어 푼 것이고 주석 처리된 코드는 스택 클래스를 이용하여 푼 것입니다.

package DataStructure;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class DataStructure_17299 {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(br.readLine());
		int[] countArray = new int[1000001];
		int[] numArray = new int[n];
		int[] stack = new int[n];
		int[] result = new int[n];
		int top = -1;
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < n; i++) {
			int A = Integer.parseInt(st.nextToken()); 
			countArray[A]++;
			numArray[i] = A;
		}
		
		
		for(int i = 0; i < n; i++) {
			while(top != -1 && countArray[numArray[top]] < countArray[numArray[i]]) {
				result[stack[top]] = numArray[i];
				top--;
			}
			top++;
			stack[top] = i;
		}
		
		if(top != -1) {
			for(int i = top; i >= 0; i--) {
				result[stack[i]] = -1;
			}			
		}
		
		for(int i = 0; i < n; i++) {
			sb.append(result[i]).append(" ");
		}
		
		System.out.println(sb);
		br.close();
	}
}

//import java.io.BufferedReader;
//import java.io.InputStreamReader;
//import java.io.IOException;
//import java.util.Stack;
//import java.util.StringTokenizer;
//
//public class Main {
//	public static void main(String[] args) throws IOException{
//		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		StringBuilder sb = new StringBuilder();
//		
//		int n = Integer.parseInt(br.readLine());
//		int[] countArray = new int[1000001];
//		int[] numArray = new int[n];
//		Stack<Integer> stack = new Stack<>();
//		int[] result = new int[n];
//		
//		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
//		for(int i = 0; i < n; i++) {
//			int A = Integer.parseInt(st.nextToken()); 
//			countArray[A]++;
//			numArray[i] = A;
//		}
//		
//		
//		for(int i = 0; i < n; i++) {
//			if(stack.isEmpty()) {
//				stack.push(i);
//			}
//			while(!stack.isEmpty() && countArray[numArray[stack.peek()]] < countArray[numArray[i]]) {
//				result[stack.pop()] = numArray[i];
//			}
//			stack.push(i);
//		}
//		
//		if(!stack.isEmpty()) {
//			while(!stack.isEmpty()) {
//				result[stack.pop()] = -1;
//			}			
//		}
//		
//		for(int i = 0; i < n; i++) {
//			sb.append(result[i]).append(" ");
//		}
//		
//		System.out.println(sb);
//		br.close();
//	}
//}
//

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

자바 stack에 관련된 질문입니다.

sange17 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말