[15831] 준표의 조약돌

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

15831번: 준표의 조약돌

투 포인터 문제다. 

 

풀이

범위의 시작 인덱스를 담은 head 변수와 끝 인덱스를 담은 tail 변수를 생성. 다음과 같은 동작들을 tail이 n이 될 때까지 반복한다.

 

현재 tail이 가리키는 조약돌이 검은 돌이고 들고 있는 검은 돌의 개수가 B개 미만이라면, 더 들고 갈 수 있는 상태이므로 가져가야 할 돌로 포함시키고 tail을 증가시킨다.

 

현재 tail이 가리키는 조약돌이 검은 돌이고 들고 있는 검은 돌의 개수가 B개 이상이라면, 더 이상 들고 갈 수 없으므로 head가 가리키는 조약돌을 버리고 head를 증가시킨다.

 

현재 tail이 가리키는 조약돌이 흰돌이라면 가져가야 할 돌로 포함시키고 tail을 증가시킨다. 매 탐색마다 주운 조약돌의 개수가 준표의 조건에 맞다면 출력값을 최대길이로 갱신한다.

 

정답 코드

	import Foundation
	let nbw = readLine()!.split(separator: " ").map{Int($0)!}
	let n = nbw[0]
	let b = nbw[1]
	let w = nbw[2]
	let arr = readLine()!.map{String($0)}
	var head = 0
	var tail = 0
	var bCnt = 0
	var wCnt = 0
	var ans = 0
	while tail < n{
	if arr[tail]=="B"{
	if bCnt >= b{
	if arr[head] == "B"{
	bCnt -= 1
	}else{
	wCnt -= 1
	}
	head += 1
	}else{
	bCnt += 1
	tail += 1
	}
	}else{
	wCnt+=1
	tail+=1
	}
	if bCnt<=b && wCnt>=w{
	ans = max(ans, bCnt+wCnt)
	}
	}
	print(ans)

view raw 15831.swift hosted with ❤ by GitHub