[문제]
https://www.acmicpc.net/problem/12933
[풀이]
연속되는 'quack'을 찾아 '.'으로 치환시켜주고 전체 문자열 개수에서 5씩 차감시킨다.
연속되는 'quack'을 찾을 수 있다면 오리 개수를 증가시키고, 이후 남은 문자 개수가 0이라면 정답을 출력한다.
연속되는 'quack'을 찾을 수 없다면 잘못된 오리 울음이므로 -1을 출력한다.
quqacukqauackck
..q..u..a....ck //처음 for문 돈 이후
............... //두번째 for문 돈 이후. 남은 문자개수 0개이므로 break
[코드]
package 그리디;
import java.util.*;
import java.io.*;
public class boj_12933_오리 {
static String s;
static char[] input;
static int answer;
static char[] quack = {'q', 'u', 'a', 'c', 'k'};
public static void main(String[] args) throws Exception{
// 영선이 방에 있을 수 있는 오리의 최소 개수를 구하는 프로그램을 작성하시오.
Scanner scan = new Scanner(System.in);
s = scan.nextLine();
input = s.toCharArray();
if(s.length()%5!=0) {
System.out.println(-1);
return;
}
int idx = 0;
int total = s.length();
while(true){
int ptr = 0;
int[] temp = new int[5]; //quack 인덱스 저장
int tid = 0;
boolean flag = false;
for(int i=0; i<s.length(); i++){
if(input[i]==quack[ptr]){
temp[tid++] = i;
ptr++;
}
if(ptr==5){ //올바른 오리 울음 소리
flag = true;
ptr = 0;
tid = 0;
//index '.'로 치환
total -= 5;
for(int j=0; j<5; j++){
input[temp[j]] = '.';
}
}
}
if(flag) answer++;
else {
System.out.println(-1);
return;
}
if(total==0) break;
}
System.out.println(answer);
}
}
'알고리즘 공부 및 문제 풀이 > 백준(BOJ)' 카테고리의 다른 글
[boj] 백준 17413 단어 뒤집기 (Java) - 스택 (0) | 2023.05.05 |
---|---|
[boj] 백준 15661 스타트 링크 (Java) - 완전탐색 (0) | 2023.05.05 |
[boj] 백준 2615 오목 (Java) - 완전탐색 (0) | 2023.05.04 |
[boj] 백준 1890 점프 (Java) - dp (0) | 2023.05.04 |
[boj] 백준 2346 풍선 터뜨리기 (Java) - Deque (0) | 2023.05.04 |