POCU 노트

2605solution

16 min read

Schedule

“Schedule 클래스는 정해진 틱(tick)에서 Sprinkler를 자동으로 켜기 위해 사용합니다.”

  • 스프링클러는 스케쥴이라는 정보를 통해서 자동으로 켜짐

2.2.1 생성자 구현

몇 번 째 틱에서 켜야하는지

  • 틱이 반복되고, 어떤 시점에 켜야하는지 나타냄
  • 스프링클러를 시작하는 개념이니 “startTick”라는 변수명으로 정하자
    • 스프링클러 클래스의 내포 클래스로 만들어도 되겠는데?
      • 강한 캡슐화 몇 번의 틱이 경과한 후에 Sprinkler가 꺼야 하는지를 나타내는 int
  • startTick + 이 값 = endTick
  • 지속 시간을 의미하는 변수명은 뭐가 좋을까? - durationTicks
    • 복수형이 포인트

요구 사항을 만족하는 최소 형태는 아래와 같음

package academy.pocu.comp2500.lab8;  
  
public final class Schedule {  
    private final int startTick;  
    private final int durationTicks;  
  
    public Schedule(final int startTick, final int durationTicks) {  
        this.startTick = startTick;  
        this.durationTicks = durationTicks;  
    }  
}

SmartDevice

“클래스로부터는 개체를 만들 수 없습니다.”

  • 추상 클래스죠

2.2.1 isOn() 메서드를 구현한다

2가지 가닥이 잡힙

  1. 호출할 때 마다 on/off 상태를 계산해 반환
  2. 멤버 변수로 on/off 상태를 저장해놓고, 이를 반환

아직 어떻게 구현할 지는 미정

지금까지 정보를 종합했을 때 스프링클러는 스케쥴을 통해서 on/off 상태를 계산할 수 있을 것 같음

2.2.2 onTick() 메서드를 구현한다

매 틱마다 호출됨

지금까지 정보를 종합했을 때 스프링클러에서 매 틱마다 이 함수를 호출한다면 다음 기능이 필요함

  • 현재 틱이 몇인지 알 수 있어야함
  • 틱이 몇인지 + 스케쥴을 기반으로 스프링클러 on/off

2.2.3 getTicksSinceLastUpdate() 메서드를 구현한다

장치의 on/off가 바뀌는 틱을 상태로 가지고 있어야 함

on/off 변경 시점에 이 상태(틱 값)을 저장

Sprinkler

addSchedule로 스케쥴을 추가하면, 스프링클러 개체에서 이를 상태로 관리함

  • 스케쥴 목록을 가짐

한 틱에서 적용되는 스케쥴은 오직 하나

스케쥴이 유효하지 않을 수 있음

  • 스케쥴의 시작 틱이 0이 아닌 것
    • 스케쥴에 포함된 상태로 확인할 수 있음
  • 스케쥴의 끝 틱이 현재 틱 이상인지 여부
    • 현재 몇 틱인지 알아야함
      • 현재 몇 틱인지 알 수 있는 방법은?
        • 지금 당장 떠오르는건 onTick 함수

“만약 새 스케줄을 처음으로 고려할 때, 그 스케줄의 시작 틱이 과거였다면”

  • 이 표현에서 스케쥴을 고려할 때 특정 틱에서 고려하고, 스케쥴의 시작은 스케쥴에 포함된 정보니까 비교할 수 있겠다

onTick에서 스케쥴 목록에서 순서대로 스케쥴이 유효한지 검사

  • 스케쥴이 유효하다면
    • 스케쥴 진행
  • 스케쥴이 유효하지 않으면
    • 버리고 다음 스케쥴 검사

“모든 스케줄은 틱이 시작되기 전에만 더해지며, 틱 중간에는 스케줄이 추가되지 않는다고 가정합니다.”

  • 스케쥴이 고정으로 정해진 상태에서 틱이 증가하고 그에 따라 동작해야함

onTick의 책임 도출

스펙에 테스트 코드를 확인해보면 외부(테스터)가 매 틱 호출하는 함수는 오직 onTick 하나다

  • 따라서 onTick을 호출할 때 개체의 상태를 스스로 책임지게 구현
Sprinkler sprinkler = new Sprinkler();
sprinkler.addSchedule(new Schedule(0, 4));
sprinkler.addSchedule(new Schedule(1, 4));
sprinkler.addSchedule(new Schedule(2, 3));
sprinkler.addSchedule(new Schedule(6, 4));
boolean[] expectedIsOn = new boolean[]{false, true, true, true, true, false, true, true, true, true, false, false, false};
 
for (int i = 0; i < expectedIsOn.length; ++i) {
	assert (expectedIsOn[i] == sprinkler.isOn());
	sprinkler.onTick();
    }

[[#222-ontick-메서드를-구현한다|2.2.2 onTick() 메서드를 구현한다]] 에서 생각했듯이, onTick을 호출할 때 마다 개체 내부에서 현재 몇 틱인지 count 해야 함

  • onTick이 인자를 받는 것도, 반환값이 있는 것도 아님
  • 클래스의 멤버 변수로 관리

컴파일러가 Sprinkler 타입의 변수 sprinkler에서 onTick 호출이 가능하려면 onTick의 위치 후보는 다음과 같다.

  • Sprinkler 클래스 내부
  • Sprinkler 가 상속하는 부모 클래스 SmartDevice 내부

두 후보에 대한 가능성을 열어두고 Sprinkler의 onTick 동작을 도출해보자.

onTick의 동작

우선 개체 내부에서 가지고 있는 현재 틱을 기록하는 멤버 변수의 값을 증가 시킨다.

  • currentTick 같은 변수
    • 이 변수의 위치 후보는 다음과 같다.
      • Sprinkler 클래스 내부
      • Sprinkler 가 상속하는 부모 클래스 SmartDevice 내부

다음으로 k번째 틱에서 수행할 동작을 도출하면

  • 스케쥴 목록에서 스케쥴 확인
  • 스케쥴이 유효한지 검사
    • 유효하면 그 스케쥴에 따라 on/off 상태 변화
      • 상태가 바뀌면 바뀐 시점의 틱 값을 기록
        • 기록해두어야 [[#223-gettickssincelastupdate-메서드를-구현한다|2.2.3 getTicksSinceLastUpdate() 메서드를 구현한다]]에서 본 것처럼 getTicksSinceLastUpdate에서 사용할 수 있음
    • 유효하지 않으면 다음 스케쥴 확인

알고리듬을 구체화하기 위해 스펙의 테스트 케이스를 돌려본다.

2.3 Sprinkler 클래스 구현하기에 나오는 테스트 케이스를 돌려보면 다음과 같다.

0틱

  • 스케쥴 목록 : [스케쥴1, 스케쥴2, 스케쥴3]
  • 스케쥴 목록에서 가장 먼저 추가한 “스케쥴 1”이 유효한지 검사
    • 시작틱은 2라서 0이 아님
    • 꺼져야 되는 틱이 5로 현재 틱인 0틱 이상임
    • 따라서 유효하다고 판단
      • 유효하기 때문에 스케쥴을 적용
        • 현재 틱이 시작 틱 전이기 때문에 아무일도 일어나지 않음

1틱은 0틱과 동일함

2틱

  • 스케쥴 목록 : [스케쥴1, 스케쥴2, 스케쥴3]
  • 스케쥴 목록에서 가장 먼저 추가한 “스케쥴 1”이 유효한지 검사
    • 유효하다고 판단 (유효성 검사 과정은 0틱과 동일하니 생략)
      • 유효하기 때문에 스케쥴을 적용
        • 현재 틱은 2틱이라 스프링클러를 킴
          • 마지막으로 on/off 를 변경한 틱을 기록

7틱

  • 스케쥴 목록 : [스케쥴1, 스케쥴2, 스케쥴3]
  • 스케쥴 목록에서 가장 먼저 추가한 스케쥴을 고려, 유효성 검사는 기존과 동일
    • 현재 틱은 7틱이라 스프링클러를 꺼야함
      • 마지막으로 on/off 를 변경한 틱을 기록

8틱

  • 스케쥴 목록 : [스케쥴1, 스케쥴2, 스케쥴3]
  • 스케쥴 목록에 가자 먼저 추가한 “스케쥴 1”이 유효한지 검사
    • 스프링클러가 꺼져야 되는 틱이 7틱, 현재 틱은 8틱으로 유효하지 않음
      • 앞으로 틱에서 “스케쥴1”을 고려할 이유가 없음
      • “스케쥴1”을 목록에서 제거
  • 스케쥴 목록에서 다음 스케쥴인 “스케쥴2”가 유효한지 검사
    • 같은 틱에서 “스케쥴1”을 목록에서 제거하고, “스케쥴2”를 검사하는 상황이 스펙의 “새 스케줄을 처음으로 고려할 때”임
    • 새 스케줄인 “스케줄2”의 시작 틱이 4로 8틱보다 과거라서, 유효하지만 키지 않음

12틱

  • 스케쥴 목록 : [스케쥴2, 스케쥴3]
  • 스케쥴 목록에 가장 앞에 있는 “스케쥴 2”이 유효한지 검사
    • 유효서 검사는 8틱과 동일
    • 유효한 “스케쥴2”의 스프링클러를 끄는 틱이 12라서 꺼야하지만 스프링클러는 이미 꺼져 있기 때문에 아무 일도 일어나지 않음

13틱

  • 스케쥴 목록 : [스케쥴2, 스케쥴3]
  • 스케쥴 목록에 가장 앞에 있는 “스케쥴 2”이 유효한지 검사
    • 스프링클러가 꺼져야 되는 틱은 12틱으로 현재 틱보다 과거라 유효하지 않음
      • 앞으로 틱에서 “스케쥴2”를 고려할 이유가 없음
      • “스케줄2”를 목록에서 제거
  • 스케줄 목록에서 다음 스케줄인 “스케줄3”이 유효한지 검사
    • “스케줄3”은 끝나는 틱이 7로 현재 틱 13보다 과거라 유효하지 않음

이를 종합해서 알고리즘을 구상해보면

k번째 틱에 다음 동작 수행

  • 스케줄 목록에서 가장 먼저 넣은 스케줄 확인
    • 자료구조 큐 확정
    • 가장 먼저 넣은 스케줄을 바로 확인하는 연산 제공
  • 스케줄 유효성 검사
    • 유효하면 다음을 진행
      • 처음으로 고려하는 스케줄(같은 틱에서 유효하지 않은 스케줄 이후 새로운 스케줄 검사?)
        • 스케줄의 시작 틱이 과거였다면 켜지 않음
          • 유효하지만 on/off 동작이 없음
        • 스케줄의 시작 틱이 과거가 아니라면 on
          • 미래라도 켜지 않음
          • 시작 틱이 정확히 지금 틱과 같아야함
          • on/off 가 바뀌는 현재 틱을 기록
      • 처음으로 고려하는 스케줄이 아니라면
        • on 하는 경우는 없음
        • 끝나는 틱과 현재 틱 비교해서 off
          • on/off 가 바뀌는 현재 틱을 기록
    • 유효하지 않으면 다음을 진행
      • 목록에서 스케줄 제거
      • 큐에서 다음 스케줄 유효성 검사
        • 다음 스케줄이 유효하다면 새로운 스케쥴이 됨
    • 유효한 스케줄이 나올 때 까지 반복해서 목록에서 스케줄 제거
      • 스케줄 목록이 비면 아무 행동도 하지 않음
        • 명세에서 딱히 정의된 것이 없기 때문

스펙에서 말하는 “새 스케줄을 처음으로 고려할 때”를 구체화 해보자.

  • 틱0, 틱1에서 “스케줄1”은 처음으로 고려한 스케줄인가?

    • 처음으로 고려한 스케줄이라고 가정하자
    • 스케쥴의 시작이 미래라서 키면 안 됨
      • 201라인에 작성했던 조건을 수정해야함 “과거 아니라면” 이 아니라 “정확히 동일한 틱이라면”
    • 처음으로 고려한 스케줄이라고 가정하고, 스케줄의 시작 틱을 현재 틱과 값이 동일한지 비교하면 잘 동작함
    • 그렇다면 어떻게 처음으로 고려한 스케쥴임을 알 수 있을까?
      • 상태로 저장하는 방법이 있음
        • 기존에 고려하는 상태는 스케줄 목록, 현재 몇 틱인지, on/off가 바뀐 틱
          • 여기에 추가적으로 어떤 상태를 기록해 스케줄의 처음 여부를 판단

  • 틱 9,10,11 에서 “스케줄2”는 처음으로 고려한 스케줄인가?

    • 틱 8에서 “스케줄1”을 유효하지 않다고 판단하고, 처음으로 “스케줄2”를 고려했기 때문에 198라인에 작성한 “같은 틱에서 유효하지 않은 스케줄 이후 새로운 스케줄 검사”로 새로운 스케줄인지 판단할 수 없음

그래프 뷰