(JAVA) 백준 15831번 : 준표와 조약돌 -- [투포인터]

https://www.acmicpc.net/problem/15831

15831번: 준표의 조약돌

 

안녕하세요.

 

이 문제는 투포인터 문제로,

 

어느 회사 코딩테스트의 마지막 문제 유형과 비슷해서 끝나자마자 한번 풀어봤습니다..

 

 

투포인터도 나올 줄 몰랐고,

실제로 코테 문제도 풀지 못했기에

 

아쉬워서 투포인터 다시 공부해야겠다 다잡고 시작했습니다만

결국 다른 사람들의 해설을 참고했습니다ㅠㅠ

 

 

 

알고리즘

---

풀이는 간단합니다.

 

Input 이

10 1 2

WBBWWBWWBW

 

라고할 때,

start = 0, end = 0으로 놓고 진행해봅시다.

 

 

1) start = 0, end = 0

-> window : W

-> black = 0 <= 1, white = 1 < 2 이므로, 최대 길이 갱신 X

-> end++

---

2) start = 0, end = 1

-> window : WB

-> black = 1 <= 1, white = 1 < 2 이므로, 최대 길이 갱신 X

-> end++

---

3) start = 0, end = 2

-> window : WBB

-> black = 2 <= 1, white = 1 < 2 이므로, 최대 길이 갱신 X, start 돌 제거

-> start++

---

4) start = 1, end = 2

-> window : BB

-> black = 2 <= 1, white = 0 < 2 이므로, 최대 길이 갱신 X, start 돌 제거

-> start++

---

5) start = 2, end = 2

-> window : B

-> black = 1 <= 1, white = 0 < 2 이므로, 최대 길이 갱신 X

-> end++

---

6) start = 2, end = 3

-> window : BW

-> black = 1 <= 1, white = 1 < 2 이므로, 최대 길이 갱신 X

-> end++

---

7) start = 2, end = 4

-> window : BWW

-> black = 1 <= 1, white = 2 < 2 이므로, 최대 길이 갱신 O(최대 길이 : 3)

-> end++

---

8) start = 2, end = 5

-> window : BWWB

-> black = 2 <= 1, white = 2 < 2 이므로, 최대 길이 갱신 X(최대 길이 : 3), start 돌 제거

-> start++

 

...

이런 식으로 풀 수 있는데요.

이렇게 start, end 지점을 잡고(이렇게 잡게 되면 start와 end 사이 구간이 생깁니다.)

start와 end를 움직이면서 조건에 맞는 결과를 찾아내는 방식이 투포인터(슬라이딩 윈도우) 방식입니다.

 

해당 구간을 window라 하고, 이를 양옆으로 움직인다 하여 sliding window라 하는 것 같습니다.

 

 

 

그럼, 알고리즘을 만들어보겠습니다.

 

 

 

1. 우선, 시작지점과 끝지점을 선언합니다.

처음이니까 0이겠죠?

 

 

2. 그리고, end index가 조약돌 길의 끝에 닿을때까지 while문을 수행합니다.

 

왜 end가 끝에 닿으면 종료하는가?

이유는 end가 끝에 닿으면 나머지 start가 1씩 증가하면서 end의 뒤를 따라오는데요(sliding window)

 

최대 길이가 이전에 정해졌다면, 반드시 이 값보다 같거나 작아지게 되기 때문입니다.

(start가 1씩 증가한다면, start ~ end 사이 길이는 무조건 이전보다 작아지겠죠? 그럼 최대 길이가 나오지 않습니다.)

 

 

3. 다음으로, 지금까지의 구간(window) 까지의 검은 조약돌 개수, 흰 조약돌 개수, 구간의 길이, 최대 길이를 선언합니다.

 

 

4. while문 내부에서 구간 내의 검은 조약돌 개수가 조건에 일치하는지 체크해서, 일치하지 않으면 구간의 맨 왼쪽(start)에 있는 돌을 제거합니다. 

이 때, 돌의 종류에 따라 검/흰 조약돌 개수 값도 조정하고, start도 1 증가시킵니다.

 

아참!

구간의 길이도 1 감소해야겠지요?

 

 

5. 4의 조건에 일치하는 경우, end 지점을 봐야합니다.

end 지점에 있는 돌의 종류에 맞게 개수를 증가시키고, 개수를 증가시켰으니 구간의 길이도 증가시켜야합니다.

돌을 확인했으니, end도 1 증가시킵니다.

 

 

6. 문제에서 주어진 검은 돌과 흰 돌의 조건에 만족한다면, 현재 구간의 길이와 최대 길이를 비교해서 최대 길이를 갱신해줍니다.

 

 

7. 이를 end가 조약돌의 끝지점에 도달할 때 까지 반복합니다.

 

 

이상입니다.

감사합니다!

 

소스코드

---