👀 문제
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXJZ8ua6CTkDFAU3
👊 도전
1. 설계
- W앞에 있는 B의 개수만큼 뒤집기를 할 수 있으므로 연산 횟수는 W위치-B가 시작되는 위치를 모두 누적하면 된다.
2. 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.*;
/**
*
* @author HEESOO
*
*/
class Solution {
public static void main(String args[]) throws Exception {
Scanner sc = new Scanner(System.in);
int T;
T=sc.nextInt();
for(int test_case = 1; test_case <= T; test_case++) {
char[] cards=sc.next().toCharArray();
long answer=0;
int prevB=0;
for(int i=0;i<cards.length;i++) {
if(cards[i]=='W') {
answer+=(i-prevB);
prevB++;
}
}
System.out.println("#"+test_case+" "+answer);
}
}
}
3. 결과
🤟 성공 🤟
문제 설명대로 B, W의 뒤집기를 진짜 하도록 코드를 짰더니 제한시간 초과가 발생했다.
오답은 answer을 long형으로 선언하지 않아서였다.
4. 설명
- W 앞의 B 개수를 구한다
- BW를 WB로 바꾸면 W가 앞으로 이동하는 것과 같으므로 W의 앞에 B가 있는 만큼 swap할 수 있다.
- 따라서 W 앞에 있는 B의 개수를 구해야 한다.
- 인덱스 i로 문자를 하나하나 체크하다가, W를 발견하면 W 앞에 B의 시작 인덱스 prevB를 구한다.
- prevB 변수를 생성하여 이전 B의 위치를 저장한다. 현재 i 위치가 W이므로 swap이 모두 끝나면 W가 아까 B의 시작 지점으로 가고 W자리에 B가 온다. 그러면 B의 시작은 이전 B가 끝난 다음+1이므로 prevB++이다.
- answer의 오버플로우를 방지한다
- 문자열 s가 길이가 200,000(=2*10^5)인 “BW…BW”라면
answer= 1+2+...+200,000-1~=(2*10^5+1)*10^5=2*10^10+10^5이므로 21억을 거뜬히 넘는다. 따라서 long형으로 선언해야 한다.
- 문자열 s가 길이가 200,000(=2*10^5)인 “BW…BW”라면