글 읽기 - [java] Queue 와 Stack

haseok1020 3년 전 0

코딩초보라 저한테 익숙한 Stack으로 시도했다가 시간초과나와서 Queue 로 시도하니 되더라고요....구성은 크게 차이없는거 같은데 왜 Stack은 안되고 Queue는 되는지 궁금합니다! 도와주세요!!!

위에가 Stack 아래가 Queue 입니다.

//Stack
public class code2164 {
	public static void main(String[] args) {
		Stack<Integer> card=new Stack();
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		for(int i=N;i>=1;i--) {
			card.push(i);
		}
		while(card.size()!=1) {
				card.pop();
				card.add(0, card.pop());
		}
		System.out.println(card.pop());
	}
}

//Queue
public class code2164 {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		Queue<Integer> Q=new LinkedList<Integer>();
		for(int i =1;i<=N;i++) {
			Q.offer(i);
		}
		while(Q.size()!=1) {
			Q.poll();
			Q.offer(Q.poll());
		}
		System.out.println(Q.poll());
	}
}

topgun0209 3년 전 1

add메소드는 해당 index~끝까지의 배열을 arraycopy로 옮겨 자리를 확보하고, 그 자리에 요소를 삽입하는 식으로 동작합니다

문제에서 input이 최대 50만이라 했으므로,

1개를 제거 - 49만~개를 복사 - 1개를 삽입

같은 작업이 반복해서 일어나게 되고, 시간초과가 발생합니다

haseok1020 3년 전 0

아하 그렇군요 ㅎㅎ 감사합니다!

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

문제

문제

출처

ICPC

[java] Queue 와 Stack

haseok1020 3년 전 0

topgun0209 3년 전 1

haseok1020 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말