구간 칠하기 (1차원), 겹치는 지점과 겹치는 구간 구하기

약간 어디 구간 청소? 이런 문제에서 나오는듯

흰검 칠하기

1차원에서 칠하기 (사각형은 2차원)

 

Case 가 두가지로 나뉨

 

Case 1 . 두 구간이 겹칠 때

Case 2. 두 구간이 겹치지 않을 때

 

근데 뭐 케이스 안나누고 시뮬레이션 하는 방법이 있음

일단 배열 선언

int[] cleaned = new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

//만약에 3 - 8 구간 청소? 그러면 인덱스 2-7 +1

int[] cleaned = new int[]{0, 0, 1, 1, 1, 1, 1, 1, 0, 0};

이렇게 하고 전체 구간 쭉 순회하는 코드 (아마도 for 문 이겠죠?) 로 1 개수 세면 (cnt++ 이용?)

쓰면 끝

 

 

구간칠하기 2. 

 

겹치는 지점과 겹치는 구간 구하기

 

 

배열 선언하고 해당하는 위치에 전부 1씩 더해 숫자가 2인 곳의 수를 세는 방법으로 해결 가능

 

2인 곳의 수를 세면 겹치는 "지점" 은 구할 수 있음.

 

그러면 겹치는 "구간" 은 어떻게 구할까?

x1 ~ x2 표기를 x1 ~ (x2-1) 로!

3-8 청소면 2-7 까지 표기했던 것을

2-6 까지 표기해주면 된다

그리고 숫자 큰거 갯수 세기!!

 

만약 음수면 주어진 정수 범위 offset 더하기