https://www.acmicpc.net/problem/12933
코드설명
구현(Implementation) + 스택(Stack) 을 활용합니다.
구현하다보면, 맞는데 왜 틀리지 라는 상황이 발생합니다.
첫번쨰 유의사항입니다. 입력자체가 틀리다면 울음소리가 잘못된 것이므로 -1 을 출력해야 합니다.
예시케이스입니다.
kcauquack
위의 테스트케이스는 틀립니다. 이유는 kcau는 사용되지 못했기 때문입니다.
저의 경우, 오리가 한명도 없어서 이제 새로운 오리가 존재한다고 예측할떄,
처음에는 반드시 'q' 로 시작하는 것으로만 처리해서 계속해서 86%에서 오답이 발생했는데, 이와 다르게 만약 첫 시작에는 반드시 울음소리를 삽입하게 만들어 오류 울음소리를 찾아냅니다.
//만약 넣을 수 있는 공간이 없었다면, if(flag == false) { //새로 추가할 소리의 첫시작은 반드시 'q'이어야 함. // if(word == wordArray[0]) { arr.add(new Stack<Character>()); arr.get(arr.size() - 1).add(word); // } }
두번째는, Stack을 활용하여 구현을 편하게 할 수 있습니다.
가장 맨위의 울음소리와 다음 울음소리만 비교하면 되기 때문입니다.
코드
package Main; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.HashSet; import java.util.Stack; import java.util.StringTokenizer; public class Main { static int N, M, P, K, A, B, X, R, T; static int answer = 0; // static int[] arr; static ArrayList<Stack<Character>> arr = new ArrayList<Stack<Character>>(); static char[] wordArray = new char[] {'q','u','a','c','k'}; static HashSet<Character> hashset = new HashSet<>(); public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); String str = st.nextToken(); for(int i=0; i<str.length();i++) { Character word = str.charAt(i); boolean flag = false; for(int j=0; j<arr.size(); j++) { Stack<Character> stack = arr.get(j); if(word == wordArray[stack.size()]) { flag = true; stack.add(word); if(stack.size() == 5) { stack.clear(); } break; } } //만약 넣을 수 있는 공간이 없었다면, if(flag == false) { //새로 추가할 소리의 첫시작은 반드시 'q'이어야 함. // if(word == wordArray[0]) { arr.add(new Stack<Character>()); arr.get(arr.size() - 1).add(word); // } } } for(int j=0; j<arr.size(); j++) { Stack<Character> stack = arr.get(j); if(stack.size() > 0) { System.out.println(-1); return ; } } System.out.println(arr.size()); } }
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 14627 파닭파닭 - 파라매트릭서치(Paramatric Search) + 최적화 문제 결정문제로 바꿔풀기 JAVA (0) | 2024.09.16 |
---|---|
[백준] 14248 점프 점프 - BFS(너비우선탐색) JAVA (0) | 2024.09.16 |
[백준] 2885 초콜릿 식사 - 분할정복(DivideAndConquer) JAVA (0) | 2024.09.15 |
[백준] 1326 폴짝폴짝 - 너비우선탐색(BFS) JAVA (0) | 2024.09.14 |
[백준] 24480 알고리즘 수업 - 깊이 우선 탐색 2 - DFS(깊이우선탐색) JAVA (0) | 2024.09.13 |