[백준/JAVA] 12933번: 오리

📖 문제

12933번: 오리

 

 

💡  풀이 방식

• 그리디

- 2중 for문으로 미방문한 입력값이 quack 문자열의 순서가 맞는지 하나하나 비교  확인한다.

순서를 지켰으면 맞게 운 것이므로 리스트에 값을 추가한다.

for(int i = 0 ; i < ch.length ; i++) {
    List<Character> list = new ArrayList<>();

    for(int j = i ; j < ch.length ; j++) {
        // 이 값이 방문 안 한 울음소리 배열이 duck 배열의 순서를 지켰는지 확인
        if(!visited[j] && ch[j] == duck[idx]) {
            idx++;
            list.add(ch[j]);
            visited[j] = true;

            if(idx == 5) {
                idx = 0;
            }
        }
    }
}

 

- 매번 for문이 종료하고 리스트의 마지막 값이 k가 아니면 제대로 울었다고 할 수 없으므로 -1을 출력한다.

if(list.size() != 0) {
    // 리스트의 마지막 값이 k가 아니라면 제대로 운 게 아니니까 -1 리턴
    if(list.get(list.size() - 1) != 'k') {
        System.out.println(-1);
        return;
    }

    cnt++;
}

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static char[] duck = {'q', 'u', 'a','c', 'k'};
    
    static char[] ch;   // 울음소리 배열
    static boolean[] visited;
    
    static int idx = 0;
    static int cnt = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        ch = br.readLine().toCharArray();
        visited = new boolean[ch.length];
        
        // 첫 번째 값이 'q'로 시작하지 않거나, 배열 길이가 5의 배수가 아닌 경우 -1
        if(ch[0] != 'q' || ch.length % 5 != 0) {
            System.out.println(-1);
            return;
        }
        
        for(int i = 0 ; i < ch.length ; i++) {
            List<Character> list = new ArrayList<>();   // 방문 안 한 울음소리 배열
            
            for(int j = i ; j < ch.length ; j++) {
                // 미방문한 입력값과 quack 문자열 하나하나 비교
                if(!visited[j] && ch[j] == duck[idx]) {
                    idx++;
                    list.add(ch[j]);
                    visited[j] = true;
                    
                    if(idx == 5) {
                        idx = 0;
                    }
                }
            }
            
            if(list.size() != 0) {
                // 리스트의 마지막 값이 k가 아니라면 제대로 운 게 아니니까 -1 리턴
                if(list.get(list.size() - 1) != 'k') {
                    System.out.println(-1);
                    return;
                }
                
                cnt++;
            }
        }
        
        System.out.println(cnt);
    }
}
 

 

 

 

➕ 다른 풀이 방식

백준 12933 오리 (JAVA)

[자바] 백준 12933 - 오리 (java)

 

---

💦 어려웠던 점

- 아이디어 자체를 생각해내지 못 해 다른 분 코드를 보고 작성했다,,,,

- 입력받은 문자열과 duck 문자열 만들어서 비교하기 💥

 

1회독	2회독	3회독	4회독	5회독
V	240612

 

 

(+ 2회독 240612 : 14948KB, 168ms)

import java.util.*;
import java.io.*;
 
public class Main {
    static char[] duck = new char[]{'q', 'u', 'a', 'c', 'k'};
    
    static char[] ch;
    static boolean[] visited;
    
    static int idx, cnt;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        ch = br.readLine().toCharArray();
        visited = new boolean[ch.length];
        
        if(ch[0] != 'q' || ch.length % 5 != 0) {
            System.out.println(-1);
            return;
        }
        
        for(int i = 0 ; i < ch.length ; i++) {
            List<Character> list = new ArrayList<>();
            
            for(int j = i ; j < ch.length ; j++) {
                if(visited[j])  continue;
                
                if(ch[j] == duck[idx]) {
                    visited[j] = true;
                    list.add(ch[j]);
                    idx = (idx + 1) % 5;
                }
            }
            
            if(list.size() != 0) {
                if(list.get(list.size() - 1) != 'k') {
                    System.out.println(-1);
                    return;
                }
                
                cnt++;
            }
        }
        
        System.out.println(cnt);
    }
}
 

 

 

---

(참고)

[백준] 12933_오리 (JAVA)