[백준] 10773번 : 제로 - JAVA [자바]

www.acmicpc.net/problem/10773

10773번: 제로

  

 

---

• 문제

 

 

 

 

스택에 대해 알면 쉽게 풀 수 있는 문제다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

 

이 문제 또한 쉽게 풀 수 있을 것이다.

문제 지문이 길긴 하지만, 쉽게 이해하자면 0을 입력받으면 최근에 입력받았던 수를 지우면 된다. 또한 0을 입력받을 때 지울 수 있는 수가 보장된다고 했기때문에 예외 또한 고민 할 필요가 없다.

 

 

혹여 스택에 대해 잘 알지 못하는 경우 아래 글을 참고하시는 것도 좋을 것 같다.

 

자바 [JAVA] - Stack (스택) 구현하기

 

 

 

자바에서는 util 패키지에 Stack 자료구조가 구현되어있어 Stack 클래스를 사용할 수도 있고, 또는 자체적으로 구현하여 풀이할 수도 있다. 필자 또한 두 가지 방식 모두 보여주도록 하되, 되도록 알고리즘인 만큼 자체 구현방식을 중심으로 설명하고자 한다.

 

 

 

 

 

1. Stack Class 이용

 

Stack 클래스를 import 하여 사용할 경우 아래와 같이 간단하게 짤 수 있다.

 

Stack<Integer> stack = new Stack<Integer>();
		
int K = input();	// K 정수 입력(입력 개수)
		
for(int i = 0; i < K; i++) {
	int number = input();	// 정수 입력
    
	if(number == 0) {	// 0이라면 스택에 저장된 top 원소를 지운다.
		stack.pop();
	}
	else {	// 아닐경우는 스택에 원소 추가
		stack.push(number);
	}
}

int sum = 0;
for(int o : stack) {	// 스택에 담긴 원소 합 구하기 
	sum += o;
}

 

 

매 입력마다 0을 입력 받는 경우와 아닌 경우를 나누어 짜면 어려울 것 없이 금방 풀 것이다.

 

 

 

 

 

 

2. 자체 구현방법

 

Stack 클래스 대신 배열을 사용하여 풀이 할 수도 있다.

 

필자가 링크로 걸어둔 Stack구현 포스팅을 보셨다면 알겠지만, Stack도 내부적으로는 배열을 이용하여 사용하듯 우리도 최소한의 기능만으로도 Stack과 유사하게 구성할 수 있다.

 

우리에게 필요한 것은 데이터를 담을 배열과 마지막 원소의 위치(index)를 가리키는 변수만 있으면 쉽게 풀이할 수 있다. 0번째 index를 처음 위치라 하고, 마지막 원소의 index를 가리키는 변수 이름을 top 이라고 할 때, 0을 입력받으면 arr[top] 의 원소를 0으로 바꾼 뒤, top을 1 감소시키면 되고, 0이 아닌 수를 입력받으면 top변수를 1 증가시킨 뒤 arr[top] 에 입력받은 정수로 초기화 해주면 된다.

 

즉, 이렇게 짜면 된다.

 

int top = -1;	// 마지막 원소의 위치를 가리키는 변수

int K = input();	// 입력 개수
int[] arr = new int[K];	// 최대 원소 개수는 K개를 넘지 못함
		

for(int i = 0; i < K; i++) {
			
	int number = input();	// 정수 입력
			
	if (number == 0) {	// 0 이라면 top 위치에 있는 원소를 0으로 초기화 
		arr[top] = 0;
		top--;	// top이 가리키는 위치 1 감소
	} 
	else {
		top++;	// top이 가리키는 위치 1 증가
		arr[top] = number;	// 입력받은 정수로 초기화
	}
}

int sum = 0;
for(int i = 0; i < K; i++) {	// 배열 원소 전체 합 구하기
	sum += arr[i];
}	

 

 

참고로 이해하기 쉬우라고 number == 0 일 때 0으로 초기화를 했지만, 사실 0으로 초기화하지 않고 top만 감소시켜도 된다. 어짜피 '마지막 원소의 위치'를 가리키기 때문에 굳이 초기화 해줄 필요 없이 0이 아닐 때만 top 을 증가시킨 뒤 그 위치에 원소를 초기화 해주면 되는 것이다.

 

다만 마지막에 모든 합을 구할 때 배열 전체 원소의 합이 아닌 0부터 top까지의 합만 구해주어야 한다. 즉, 위 코드에서 조금 변형시킨다면 이렇다.

 

int top = -1;	// 마지막 원소의 위치를 가리키는 변수

int K = input();	// 입력 개수
int[] arr = new int[K];	// 최대 원소 개수는 K개를 넘지 못함
		

for(int i = 0; i < K; i++) {
			
	int number = input();	// 정수 입력
			
	if (number == 0) {	// 0 이라면 top 위치에 있는 원소를 0으로 초기화 
		top--;	// top이 가리키는 위치 1 감소
	} 
	else {
		top++;	// top이 가리키는 위치 1 증가
		arr[top] = number;	// 입력받은 정수로 초기화
	}
}

int sum = 0;
for(int i = 0; i <= top; i++) {	// 합을 구할 때 K가 아닌 top까지이다.
	sum += arr[i];
}

 

 

 

이를 토대로 이제 원소의 합을 구한 뒤 출력만 해주면 끝이다.

 

 

 

 

 

 

 

 

 

---

• 4가지 방법을 사용하여 풀이한다.

 

Stack 클래스를 이용한 방법과 배열을 이용한 방식 두 가지로 나눠서 볼 것이다.

그리고 각각의 방식에서 Scanner와 BufferedReader을 사용한 방식으로 나눠 볼 것이다. 

 

1 . Scanner + Stack

2. BufferedReader + Stack

3 . Scanner + 배열

4. BufferedReader + 배열

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner + Stack]

 

import java.util.Stack;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		Stack<Integer> stack = new Stack<Integer>();
		
		int K = in.nextInt();
		
		for(int i = 0; i < K; i++) {
			int number = in.nextInt();
            
			if(number == 0) {	// 0이라면 스택에 저장된 top 원소를 지운다.
				stack.pop();
			}
			else {
				/*
				 * push() 대신 add()로 대체해도 됨 (똑같이 상단에 원소를 추가하는 메소드다.)
				 * ex) stack.add(number);
				 */
				stack.push(number);
			}
		}
		int sum = 0;
		
		for(int o : stack) {
			sum += o;
		}

		System.out.println(sum);		
	}

}

 

 

가장 기본적인 방법이라 할 수 있겠다.

또한 모든 정수가 양의 정수고 int형 최댓값 범위를 넘지 않으므로 굳이 long형을 쓰지 않아도 된다.

 

참고로 add() 메소드와 push() 메소드 모두 가장 마지막 위치에 원소를 추가하는 같은 동작을 하는 메소드다. 필자가 포스팅한 Stack 구현에서도 이를 설명하고 있으니 참고하시면 좋을 것 같다.

(스택 내부에서도 push()메소드는 addElement() 메소드로 보내는데, 이 메소드 또한 최종적으로 add() 라는 메소드로 보낸다.)

 

 

 

 

---

- 방법 2 : [BufferedReader + Stack]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 

 

 

import java.util.Stack;

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		Stack<Integer> stack = new Stack<Integer>();
		
		int K = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < K; i++) {
			int number = Integer.parseInt(br.readLine());	// 정수 입력
			
			if(number == 0) {	// 0이라면 스택에 저장된 top 원소를 지운다.
				stack.pop();
			}
			else {
				/*
				 * push() 대신 add()로 대체해도 됨 (똑같이 상단에 원소를 추가하는 메소드다.)
				 * ex) stack.add(number);
				 */
				stack.push(number);
			}
		}
		int sum = 0;
		
		for(int o : stack) {
			sum += o;
		}

		System.out.println(sum);		
	}

}

 

 

 

크게 어려울 것은 없을 것이다.

 

 

 

---

- 방법 3 : [Scanner + 배열]

 

 

 

필자가 설명한 두 번째 풀이 방법이다. 조금 더 효율적인 방법으로 수정했던 방식을 사용할 것이다.

 

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		int top = -1;	// 마지막 원소의 위치를 가리키는 변수

		int K = in.nextInt();
		int[] arr = new int[K];
		

		for(int i = 0; i < K; i++) {
			
			int number = in.nextInt();	// 정수 입력
			
			if (number == 0) {	// 0 이라면 top 위치에 있는 원소를 0으로 초기화 
				top--;	// top이 가리키는 위치 1 감소
			} 
			else {
				top++;	// top이 가리키는 위치 1 증가
				arr[top] = number;	// 입력받은 정수로 초기화
			}
		}
		int sum = 0;
		for (int i = 0; i <= top; i++) {	// 합을 구할 때 K가 아닌 top까지다.
			sum += arr[i];
		}
		System.out.println(sum);

	}

}

 

 

 

어디까지나 이 번 문제 같은 경우에서나 별다른 삭제 작업 없이 top이 가리키는 값만 변경해주는 것일 뿐이니 완전하게 이해 한 뒤에 이와 같이 풀었으면 한다.

 

 

---

- 방법 4 : [BufferedReader + 배열]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 

 

 

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int top = -1;	// 마지막 원소의 위치를 가리키는 변수

		int K = Integer.parseInt(br.readLine());
		int[] arr = new int[K];
		

		for(int i = 0; i < K; i++) {
			
			int number = Integer.parseInt(br.readLine());	// 정수 입력
			
			if (number == 0) {	// 0 이라면 top 위치에 있는 원소를 0으로 초기화 
				top--;	// top이 가리키는 위치 1 감소
			} 
			else {
				top++;	// top이 가리키는 위치 1 증가
				arr[top] = number;	// 입력받은 정수로 초기화
			}
		}
		int sum = 0;
		for (int i = 0; i <= top; i++) {	// 합을 구할 때 K가 아닌 top까지이다.
			sum += arr[i];
		}
		System.out.println(sum);

	}

}

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

채점 번호 : 24088589  -  방법 4 : BufferedReader + 배열

채점 번호 : 24088585  -  방법 3 : Scanner + 배열

채점 번호 : 24088579  -  방법 2 : BufferedReader + Stack

채점 번호 : 24088576  -  방법 1 : Scanner + Stack

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

---

• 정리

 

워낙 쉬운 문제라 별달리 설명할 것이 없었다.

 

이러한 자료구조 관련 알고리즘 문제는 만약 가능하다면 언어에서 지원하는 자료구조 클래스들을 사용하는 것 보다 직접 구현해보는 것도 좋을 듯 하다. 만약 어렵거나 이해가 되지 않은 부분이 있다면 언제든 댓글 남겨주시면 최대한 빠르게 답변드리겠다.