스택_10773_제로

문제 설명

문제

나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.

재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.

재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.

재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!

입력

첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)

이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.

정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.

출력

재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 2^31-1보다 작거나 같은 정수이다.

https://www.acmicpc.net/problem/10773

나의 풀이

먼저 지문에 나와있는 조건을 먼저 살펴보겠습니다. 

 

입력 조건을 보면, K의 범위는 (1 ≤ K ≤ 100,000) 이와 같습니다. 혹여나 이 문제를 2중 반복문으로 풀고자 하셨던 분은 모든 데이터를 순회하기 위해선 100,000 * 100,000 = 1,000,000,000,000 도합 1조개의 경우의 수를 탐색해야하기 때문에 index값을 저장할 정수형 변수 int자료형은 오버플로우가 발생합니다. 오버플로우와 관련해서는 다음 포스팅에서 설명하도록 하겠습니다.

정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다라는 말은 스택에 아무런 요소가 없을 때, pop명령을 받으면 underflow가 발생하는데, 지울 수 있는 수가 있음이 보장되니, 언더플로우 또한 고려하지 않아도 되는 비교적 쉬운 문제입니다. 

 

출력 조건을 보면, 최종적으로 적어낸 수의 합은 "2^31-1보다 작거나 같은 정수이다."라고 합니다. 정수형 타입의 int형 변수의 합을 구하다가 int형 변수가 표현할 수 있는 최대값을 넘어서면 이 또한 오버플로우가 발생하여 원하지 않는 내용 오류 값을 받게 됩니다. 하지만 지문의 조건에서 출력값의 최대 크기를 지정해주었기 때문에 덧셈 연산에서 발생하는 오버플로우는 고려하지 않으셔도 됩니다. 

 

단, 탐색의 경우의 수와 덧셈 연산을 통한 오버플로우는 약간 상이한 개념입니다. 이 또한 다음 포스팅에서 설명하도록 하겠습니다. 

 

다음 전체 코드를 보면서 주요 알고리즘만 살펴보도록 하겠습니다.

import java.util.Scanner;
 
public class _10773 {    // 가장 최근에 쓴 수를 지우는 문제
    public static int [] moneyClip;
    public static int size;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int K = sc.nextInt();
        moneyClip = new int[K];
        int sum = 0;
        
        //정수가 0일 경우에 지울 수가 있는 수가 있음을 보장할 수 있다.(입력값의 정보가 스택이 비어있을 경우의수는 없다는 것)
        while(K --> 0) {
            int number = sc.nextInt();
            if(number == 0) {
                pop();
            }else {
                push(number);
            }
        }
        
        for(int i=0; i<size; i++) {
            sum += moneyClip[i];
        }
        
        if(size==0) {
            System.out.println("0");
        }else {
            System.out.println(sum);
        }
        
        sc.close();
    }
 
    private static void push(int number) {
        // TODO Auto-generated method stub
        moneyClip[size] = number;
        size++;
    }
 
    private static void pop() {
        // TODO Auto-generated method stub
        moneyClip[size-1] = 0;
        size--;
    }
}
 

1. 변수 설정

moneyClip -> 스택의 개념을 도입할 int형 배열. 배열을 사용하여 스택을 구현하고자 할때는 가로로 누워있는 스택을 세로로 세우고 생각하시면 됩니다. 

size          -> 스택에 저장된 요소의 개수를 기억하는 변수. 요소의 크기입니다. 스택 전체 크기가 아닙니다.

K             -> 정수의 개수를 저장합니다. 

number     -> K개의 정수를 입력받습니다.(반복문 내부에 선언되어 있기 때문에, 반복이 새로 돌때 마다 선언과 초기화                     가 새로이 이루어 집니다. )

sum          -> 모든 과정을 마친 후 남은 수의 합을 저장할 변수

 

2. 반복문 설정 

주요 로직의 반복문은 간단합니다. 

while(K --> 0)은 축약된 람다식으로 K > 0; K--; 두 개의 식의 합성이라고 생각하시면 편합니다. 

결국은 매 반복이 돌 때마다 K--를 해줄 것인데, K>0을 만족하는 동안에만 반복을 수행하라는 의미입니다. 

 

3. 조건문 설정

입력받은 값이 0이라면, 스택에 있는 값을 꺼내주고, 0이 아니라면 스택에 값을 push해줍니다. 필자는 조건문에서 반례를 줄이기 위해 항상 특정 조건을 명시하고 나머지는 else문으로 묶어줍니다.

 

4. 메소드 구현

push()

위에서 size는 스택에 저장된 요소의 개수를 저장한다고 했습니다. 하지만 필자는 1차원 배열을 세로로 세우면서 스택을 모델링했기 때문에 배열의 인덱스를 고려해주어야 합니다. 

예를 들어, 스택(배열)의 size가 5라고 한다면, 최상단에 있는 값의 인덱스는 4입니다. 

다음을 참조해주시면 됩니다. 

 

1차원 배열

idx : 0 1 2 3 4

val : 3 4 2 5 6

 

따라서 새로운 값을 스택의 최상단에 추가할 때는 moneyClip[size]에 값을 저장해주어야 합니다. 

moneyClip[size-1]은 최상단에 저장되어 있는 값입니다.

연산 후에 size의 크기를 1 증가 시켜줍니다.

 

pop()

위의 설명을 이해하셨다면 pop은 더욱 간단합니다. 

최상단에 있는 값을 삭제만 해주시고, size를 1줄여 주시면 됩니다.

 

 

 

 

 

문제 및 자료 출처 : https://www.acmicpc.net/problem/10773