10773 제로

제로 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

 

1 초

256 MB

118526

81106

65358

68.426%

문제

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

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

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

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

입력

 

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

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

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

출력

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

 

나의 답안 (1차 실패)

/*
* [스택]
* 잘못된 수를 부를 때마다 0을 외치고 가장 최근 수를 지움
* 남은 수의 합을 구하기
* 정수가 "0"일 경우 가장 최근에 쓴 수를 지움(pop()) 아닐 경우 그대로 push > 지울 경우, 스택에 데이터가 들어있음을 보장
* 첫번째 정수는 테스트 케이스*/

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

public class Main{
    public static void main(String[] args) throws IOException{
        // 데이터 읽기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 스택 생성
        Stack<Integer> stack = new Stack<>();
        // 테스트 케이스 개수
        int T = Integer.parseInt(br.readLine());

        for(int i = 0; i < T; i++){
            if(Integer.parseInt(br.readLine()) != 0){
                stack.push(Integer.parseInt(br.readLine()));
            } else if(Integer.parseInt(br.readLine()) == 0) {
                stack.pop();
            }
            System.out.println(stack);
        }

        // 스택에 남은 수들의 합
        int sum;


    }
}

 

for문이 T번만큼 돌고 끝나야 하는데, 출력창에 반복문을 T번만큼 입력해도 반복문이 종료되지 않고 계속 됨. 의도한 대로 코드가 진행되지 않고 있었음.

 

[실패 이유]
이유는 br.readLine()을 너무 많이 호출하고 있어서이다.나는 내가 입력하는 숫자를 한 줄씩 읽고 스택에 넣거나 빼는 처리하고 싶은데 br.readLine()이 한 번 호출될 때마다 줄이 하나씩 날아가니까, 순서가 다 꼬이는 거임.

• br.readLine()을 하면 → 사용자 입력 중 한 줄을 통째로 읽고 그 줄은 더 이상 못 씀.

if(Integer.parseInt(br.readLine()) != 0){
    stack.push(Integer.parseInt(br.readLine()));
} else if(Integer.parseInt(br.readLine()) == 0) {
    stack.pop();
}

• 위 코드에서 br.readLine()이 다음처럼 세 번 호출됨:

1. 첫 번째 br.readLine() → 입력 줄 1 읽고 숫자 확인
2. 조건이 true면 → 두 번째 br.readLine() → 다음 줄 또 읽고 push
3. 조건이 false면 → 세 번째 br.readLine() → 다음 줄 읽고 == 0 확인 후 pop

• 즉, 3 5 0 2를 입력했을 때
  • 나의 의도는 5 push
  • 0 pop
  • 2 push
• 위의 잘못된 코드로 진행되었을 때
  • 5 읽고 5 가 0 과 같지 않은게 true라면
    • 그 다음 줄을 읽고 0을 push
    • br.readLine() → "2" 읽음 → 2 != 0 → true
    • br.readLine() → 없음 or 다음 입력 줄이 있으면 읽음 → 그걸 push
  • 따라서 흐름이 잘못 되게 됨.
• 해결: int형 변수에 읽은 수를 저장해서 처리하도록 한다.

 

나의 답안(2차 성공, 약 35분 소요)

/*
* [스택]
* 잘못된 수를 부를 때마다 0을 외치고 가장 최근 수를 지움
* 남은 수의 합을 구하기
* 정수가 "0"일 경우 가장 최근에 쓴 수를 지움(pop()) 아닐 경우 그대로 push > 지울 경우, 스택에 데이터가 들어있음을 보장
* 첫번째 정수는 테스트 케이스*/

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

public class Main{
    public static void main(String[] args) throws IOException{
        // 데이터 읽기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 스택 생성
        Stack<Integer> stack = new Stack<>();
        // 테스트 케이스 개수
        int T = Integer.parseInt(br.readLine());
        // 스택에 남은 수들의 합
        int sum = 0;

        for(int i = 0; i < T; i++){
            int num = Integer.parseInt(br.readLine());
            if(num != 0){
                stack.push(num);
                sum += num;
            } else {
                sum -= stack.peek();
                stack.pop();
            }
        }

        System.out.println(sum);

    }
}

 

💡회고

• 원래는 반복문을 모두 처리하고 스택에 남은 정수들을 모두 더할까 했지만, 그렇게 되면 pop으로 반복문을 하나 더 돌아야하고 비효율적이라 생각이 들어서 반복문 하나만 사용해서 처리하도록 해봄.