백준 28278 스택2

문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

1. 1 X: 정수 X를 스택에 넣는다. (1 ≤ X ≤ 100,000)
2. 2: 스택에 정수가 있다면 맨 위의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
3. 3: 스택에 들어있는 정수의 개수를 출력한다.
4. 4: 스택이 비어있으면 1, 아니면 0을 출력한다.
5. 5: 스택에 정수가 있다면 맨 위의 정수를 출력한다. 없다면 -1을 대신 출력한다.

입력

첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

둘째 줄부터 N개 줄에 명령이 하나씩 주어진다.

출력을 요구하는 명령은 하나 이상 주어진다.

출력

출력을 요구하는 명령이 주어질 때마다 명령의 결과를 한 줄에 하나씩 출력한다.

예제 입력 1 복사

9
4
1 3
1 5
3
2
5
2
2
5

예제 출력 1 복사

1
2
5
3
3
-1
-1

 

스택을 구현하는 문제이다.

 

Stack[]으로 인트 배열을 구성하고

ptr으로 포인터 역활을 했다.

 

틀린 코드

class Main {
	public static void main (String[] args) throws java.lang.Exception {
	    
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer st;
	    
	    int n = Integer.parseInt(br.readLine());
	    
	    int[] stack = new int[n];
	    int ptr = 0;
	    
	    for(int i=0; i<n; i++){
	        st = new StringTokenizer(br.readLine());
	        int sel = Integer.parseInt(st.nextToken());
	        
	        switch(sel){
	            case 1: 
	                stack[ptr++] = Integer.parseInt(st.nextToken());
	                break;
	            case 2:
	                if(ptr>0){
	                    System.out.println(stack[ptr-1]);
	                    ptr--;
	                }else{
	                    System.out.println("-1");
	                }
	                break;
	            case 3:
	                System.out.println(ptr);
	                break;
	            case 4:
	                if(ptr<=0){
	                    System.out.println("1");
	                }else{
	                    System.out.println("0");
	                }
	                break;
	            case 5:
	                if(ptr>0){
	                    System.out.println(stack[ptr-1]);
	                }else{
	                    System.out.println("-1");
	                }
	                break;
	                
	        }
	    }
	
	

	}
}

 

 

 

결과는 정답이랑 같게 나오나

시간 초과가 나왔다.

 

성공코드

class Main {
	public static void main (String[] args) throws java.lang.Exception {
	    
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); 
	    StringTokenizer st;
	    
	    int n = Integer.parseInt(br.readLine());
	    
	    int[] stack = new int[n];
	    int capacity;
	    int ptr = 0;
	    
	    for(int i=0; i<n; i++){
	        st = new StringTokenizer(br.readLine());
	        int sel = Integer.parseInt(st.nextToken());
	        
	          switch(sel){
                    case 1: 
                        stack[ptr++] = Integer.parseInt(st.nextToken());
                        break;
                    case 2:
                        if(ptr>0){
                            bw.write(stack[--ptr] + "\n"); 
                        }else{
                            bw.write("-1\n"); 
                        }
                        break;
                    case 3:
                        bw.write(ptr + "\n");
                        break;
                    case 4:
                        bw.write((ptr<=0 ? "1" : "0") + "\n");
                        break;
                    case 5:
                        bw.write((ptr>0 ? stack[ptr-1] : "-1") + "\n");
                        break;
                }
	    
	    }
	    
	    bw.flush();
	    
	    br.close();
	    bw.close();
	
	

	}
}

 

System.out.println으로 출력을 했기에 생긴 시간 문제였다.

BufferedWriter을 사용해서 시간을 줄여서 맞출 수 있었다.

 

코드 또한 삼항연산자로 보기 편하게 만들었다.

 

 

다른사람 풀이

import java.io.*;
import java.util.Stack;

public class Main {

    static Stack<Integer> stack = new Stack<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine()); 

        while(N --> 0){
            solution(br.readLine());
        }

        br.close();

        System.out.println(sb);
    }

    static void solution(String query){
        char c = query.charAt(0); //첫번째 문자는 명령어

        switch (c){
            //case 1의 경우 query.substring(2);를 한 이유는 공백도 문자로 포함하기 때문이다 1 X 형태이기 때문에 X의인덱스는 2다.
            case '1' : stack.push(Integer.parseInt(query.substring(2))); return;
            case '2' : sb.append(stack.isEmpty() ? -1 : stack.pop()).append("\n"); return;
            case '3' : sb.append(stack.size()).append("\n"); return;
            case '4' : sb.append(stack.isEmpty() ? 1 : 0).append("\n"); return;
            case '5' : sb.append(stack.isEmpty() ? -1 : stack.peek()).append("\n"); return;
            default: break;
        }
    }
}

 

 

확실히 다른 사람의 풀이를 보는게 재밌고 신기한 것 같다.

 

자바에서 제공하는 메소드를 사용해서 문제에 접근했다.

 

Stack<Integer> stack = new Stack<>(); 으로 스택을 구현한 뒤에 

메서드를 사용했다.

• pop(): 스택에서 가장 위에 있는 항목을 제거
• push(element): element 하나를 스택의 가장 윗 부분에 추가
• peek(): 스택의 가장 위에 있는 항목을 반환
• isEmpty(): 스택이 비어 있을 때에 true를 반환

 

나는 StringTokenizer을 사용해서 공백을 구분해서 

1 3

 

조건을 말하는 첫번째 숫자와 들어가는 두번째 글짜를 나눴다.

여기서 이 분은 subString()을 사용해서 공백을 건너띄워서 사용했다.

 

이런 방식의 접근은 생각해보지 못했는데 참신했다.

 

while(N -->) 

이 부분도 충격이였다. N을 받아서 -- 처리를 해준다. 그리고 0이 되면 false이기에 탈출하게 된다.

일정 갯수를 받아서 for문을 사용하는 방식이 아닌 while을 사용해서 하는 방식이라 놀랐다.

 

결과는 다음과 같다.

 

두번째가 내가 고안해서 만든 코드이고 

첫번째가 다른 사람의 풀이이다. 

 

확실히 기존 메서드를 사용해서 하는 경우 메모리가 많이 줄어드는 것을 볼 수 있었다.

또한 시간도 많이 빨라졌다.

 

역시 알고리즘을 알면 알 수록 사용자에게 더욱 좋은 서비스를 제공할 수 있을거 같다.

 

---

 

참고 풀이

https://velog.io/@gayeong39/%EB%B0%B1%EC%A4%80-28278-%EC%8A%A4%ED%83%9D-2

백준 28278 스택 2[JAVA]