[백준] 10773번 : 제로

문제

 

[문제 출처] : https://www.acmicpc.net/problem/10773

풀이 방법

 

문제를 보고 생각난 방법은 다음과 같다.

1) 입력받은 숫자를 배열에 저장한다.

2) 입력받은 숫자가 0이라면, 최근의 수를 0으로 바꿔준다. (지우는 것과 같다.)

    2-1) 이때, 이미 0으로 바뀌어졌을 수도 있다는 것을 고려해 배열에 들어있는 값이 0이 아닐 때까지 while문을 돌려

          배열의 인덱스 값을 줄여준다.

   2-2) 배열에 들어있는 값이 0이 아니라면, while문을 빠져나와 그곳에 0을 대입해준다.

3) for문을 이용하여 배열에 들어있는 값들을 검색해 0이 아닌 값들끼리 더해준다.

 

위의 방법을 토대로 짠 코드는 다음과 같다.

코드 1

 

초기에는 count라는 변수를 선언해주지 않았는데, 그랬을 경우에 input [i-1]이 0일 때마다 i값이 줄어들어 줄어든 i 인덱스에 새로운 원소가 들어가게 된다. ( 예를 들어, 예제 2에서 7은 input [4]의 값이다. )

그렇다면 i를 이용하여 for문을 돌렸기 때문에 10번보다 더 많은 숫자를 입력해야 sum 값을 출력하게 되고 ( 7은 7번째 입력인데 5번째에 입력한 상황과 같으므로 ) 그러면 문제에서 요구하는 출력 결과에서 벗어나게 된다.

이러한 점을 생각하지 못했고, 이를 해결하기 위해 i가 1씩 줄을때마다 count를 1씩 늘려주고 마지막에 i 값에 count를 더해 수정해주었다.

 

문제를 보고 방법은 생각났지만 그 방법을 실제로 구현하는 게 어렵고 헷갈리는 게 많아서 시간이 오래 걸렸다..

 

결과는!

 

시간 초과...  시간 초과의 원인을 알아봐야겠다...

 

또 다른 방법으로 코드를 짜보았는데 두 번째 방법은 스택을 이용한 것으로, 스택을 이용한다 생각하니 자연스럽게 for문에 이용하는 변수와 배열의 인덱스를 분리해서 짜게 되었고 이는 count가 필요 없어지게 되었다.

( 친구가 내 코드를 보고 for문에 이용하는 변수와 배열의 인덱스를 분리해서 짜는 게 편할 거라는 말이 이때 완전히 이해됐던 것 같다.. )

 

코드 2

 

결과는!

 

 

(+) 코드 1과 코드 2의 차이점을 말하자면, 코드 1은 배열에 1 0 0 0 0 0 0 0 0 6과 같이 저장이 되고

     코드 2는 배열에 1 6 0 0 0 0 0 0 0 0과 같이 저장된다.