[알고리즘 1단계] 고장난 컴퓨터

[출처 : Goorm 사이트 - Yun Goon]

문제

혜지는 자신의 컴퓨터로 코딩을 하던 중, 자신의 코드가 통째로 지워지는 현상을 겪었다. 여러 번의 시행착오 끝에, 키보드를 마지막으로 누른 후 c초 동안 자신의 코드가 그대로 남아있다가 (c+1)초가 경과하는 순간 모든 코드가 지워지는 것을 알게 되었다. 혜지는 오기가 생겨 과연 자신의 코드가 지워지는 게 먼저인지 아니면 자신이 코드를 완성하는 게 먼저인지 자신의 고장 난 컴퓨터와 대결해보고 싶었다. 혜지가 키보드를 총 N번 누른다고 할 때, 코딩을 시작한 이후 몇 초가 경과하고 키보드를 쳤는지에 대한 N개의 정보를 이용하여 코딩을 마쳤을 때 총 몇 글자가 남아있는지 계산하여라.

예를 들어, 혜지가 키보드를 [1, 3, 8, 14, 19, 20]의 시간이 경과했을 때 한 번씩 누르고 5초 동안은 코드가 남아있다고 해보자. 초기 상태엔 코드를 아무것도 입력하지 않은 상태이다. 코딩을 시작한 후 1초가 지나자 혜지는 1번째 글자를 입력했다. 여기서 2초가 지난 후 2번째 글자를 입력했다. 그 후 5초가 지난 후 3번째 글자를 입력했다. 5초 동안은 코드가 남아있기 때문에 현재 화면에는 3개의 글자가 남아있다. 그 후 6초가 지나 코드는 깨끗이 지워지고 4번째 글자를 입력한다. 그 후 5초가 지나고 5번째 글자를 입력하고, 마지막으로 1초가 지나고 6번째 글자를 입력한다. 중간에 코드가 지워졌기 때문에 최종적으로 화면에는 3개의 글자가 남아있다.

 

예시

---

풀이 (의식의 흐름)

가장 먼저 생각할 것.

1. 입력 변수 2개

2. 출력 변수 1개

3. 메인 알고리즘 [ 배열의 (n)번째와 (n+1)번째가 t 이상이 차이 나면 카운트 개수 초기화]

 

전체적인 코딩 후 -> 디테일한 수정

 

1) 변수 선언 

int tick; //설정할 제한 시간 ~10^9 범위

int length; //글자개수 10^5

int input[100000]; //글자 개수 10^5

int output = 1; //남아있는 글자의 개수

 

대략 이런 변수가 필요하다고 생각하였고, 메인 알고리즘은 떠오르는 대로 적어보았다.

//배열 앞뒤 간격이 설정한 시간간격보다 크면 카운트 1로 초기화

if ((input[j + 1] - input[j]) > tick) output = 1; 

     else output++;

 

2) 가장 확실히 먼저 작성할 수 있는 입력과 출력부분 작성

scanf("%d %d", &length, &tick); //글자 개수와 제한시간 입력

for (int i = 0; i < length; i++) { //글자갯수 만큼 숫자 입력

      scanf("%d", &input[i]);

      }

printf("%d", output); //결과 출력

 

입력받은 length와 tick을 활용하여 메인 알고리즘을 for문으로 몇 번 반복해야 하는지 생각해 코드를 작성하였다.

#include <stdio.h>
int main() {
	int tick; // 몇초제한인지 ~10^9
	int length;//글자갯수 ~10^5
	int input[100001]; //글자 갯수 조건
	int output = 1; //글자갯수를 1개만 입력했을 경우 기본 카운트는 1

	scanf("%d %d", &length, &tick); //글자갯수와 제한시간 입력

	for (int i = 0; i < length; i++) {
		scanf("%d", &input[i]);
	}
    
	//반복횟수를 잘 설정하기. 직접 숫자를 대입해보면 알아가기 쉽다.
	for (int j = 0; j < length - 1; j++) {
		if ((input[j + 1] - input[j]) > tick)	output = 1;
		else	output++;
	}

	printf("%d", output);
	return 0;
}

결과

---

* 개인적인 공부 목적으로 게시한 글이기에 내용에 잘못된 정보가 있을 수 있습니다.

* 문제 출처 - https://level.goorm.io/exam/49095/고장난-컴퓨터/quiz/1