연속되는 조건이 있는 문제 백준 20365 - 블로그2
20365번: 블로그2
neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한
www.acmicpc.net
해당 문제에서 가장 중요한 조건은 연속된 임의의 문제들을 선택한다는 것이다.
이러한 조건이 나오면 연속되는 문자를 하나의 집합으로 생각하고 중복되는 문자들은 제거해주고 저장해주자.
나는 굳이 배열을 쓰지 않고 StringBuilder(sb)만 사용해서 입력 받을 때 문자가 달라지는 경우만 Stringbuilder에 append 해주었다. 이렇게 되면 sb에는 BBR과 같이 연속되는 문자가 절대 존재하지 않게 된다.
이후 count, 즉 최소 색칠 횟수를 1로 설정하고(어떤 경우에든 최소한 1번은 칠해야 하기 때문) 문자가 달라지는 경우에만 count를 증가시켜 주었다.
문제에서 주어진 예제로 예를 들어보자.
BBRBRBBR => (BB)RBR(BB)R => BRBRBR
1. sb에 중복이 제거된 BRBRBR이 저장된다.
2. B를 일단 한번 다 칠해준 다음에(count=1)
3. R인 경우에만 추가적으로 칠해주면 된다(count++)
다른 예시 하나를 더 들어보겠다.
10
RRBBRRBBRR
1. sb = RBRBR
2. R을 한번에 싹 칠해준다.
3. B만 추가적으로 한번씩 칠해주는 작업을 거친다.
count=3
import java.io.*;
import java.util.*;
public class tmp {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
String str = br.readLine();
char tmp = str.charAt(0);
sb.append(tmp);
for(int i = 1; i < n; i++) {
if(tmp != str.charAt(i)) {
sb.append(str.charAt(i));
tmp = str.charAt(i);
}
}
int count = 1;
char first = sb.charAt(0);
for(int i = 1; i < sb.length(); i++) {
if(first != sb.charAt(i)) count++;
}
System.out.println(count);
}
}
'Algorithms > study log' 카테고리의 다른 글
[백트래킹] 눈덩이 굴리기, 근손실, 1,2,3 더하기 2 (1) | 2024.04.07 |
---|---|
[Greedy] 백준 2141 우체국 (0) | 2024.03.19 |
[java] 트리와 DFS (0) | 2024.02.26 |
[java] 큐 / 우선순위 큐 / 힙 (0) | 2024.02.23 |
[java] 플로이드-워셜 알고리즘 (0) | 2024.02.06 |