백준 - 오리(12933)

문제 설명

해당 문제는 오리의 울음소리를 분석하여 "최소"오리 수를 찾아내야 한다.
최소 오리의 수 찾기는 총 2가지로 나눌 수 있는데

• 하나의 quack이 완료하기 전까지 나온 q가 최소오리의 개수인 경우
• 하나의 quack이 완료한 후 에 새로운 오리가 나타난 경우

나는 첫 번째 경우를 메인으로 잡고, 두 번째 경우를 동시에 잡아내기 위해 minus라는 변수를 활용했다.

나의 코드

import java.io.*;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        HashMap<Character, Integer> quackIndex = new HashMap<>();

        char[] input = br.readLine().toCharArray();
        int[] checkQuack = new int[6];
        int leastQuack = 0;
        int minus = 0;

        quackIndex.put('q',1);
        quackIndex.put('u',2);
        quackIndex.put('a',3);
        quackIndex.put('c',4);
        quackIndex.put('k',5);

        checkQuack[0]=input.length;

        //문자열의 길이가 5의 배수가 아닌경우, 프로그램 종료
        if(input.length%5!=0) { 
            leastQuack = -1;
            System.out.println(leastQuack);
            br.close();
            return;
        }

        for(char quack : input){
            int index = 0;
            if(!quackIndex.containsKey(quack)){ //들어온 문자열이 q,a,u,c,k 중 하나인지 검증.
                leastQuack=-1;
                break;
            }
            index = quackIndex.get(quack);
            checkQuack[index]++; //해당 인덱스에 ++를 해줌. 해당 문자열이 입력되었다는 의미를 지님
            if(!(checkQuack[index-1]>=checkQuack[index])){ //이전 문자열의 갯수>=현재 문자열의 갯수 여야 함(순서는 q,u,a,c,k순임)
                leastQuack = -1;
                break;
            }
            if(quack=='k'){ //k가 등장할때
                if(checkQuack[1]>checkQuack[5] && minus==0){ //q>k && minus = 0
                    if(leastQuack==0){ //최소 오리수가 안세어졌을때, 해당 케이스는 일단 quack 하나가 완성된 거니 최소 오리수++
                        leastQuack++;
                    }
                    minus=checkQuack[1]-checkQuack[5]; //minus=q-k
                }
                if(checkQuack[1]-checkQuack[5]>minus) { //k가 들어왓는데, q-k가 기존 minus보다 크다면 새로운 오리가 등장한 것!
                    minus=checkQuack[1]-checkQuack[5];
                }
                if(checkQuack[1]==checkQuack[5] && leastQuack==0){ //q=k && 최소 오리수 안 세어진 경우
                    leastQuack++;
                }
            }
        }
        if(checkQuack[5]*5!=input.length){ //모든 quack이 k까지 잘 입력되었는지 확인
            leastQuack = -1;
        }
        else {
            leastQuack+=minus;
        }
        System.out.println(leastQuack);
        br.close();
    }
}

깃허브 : https://github.com/jung-min-ju/CodingTestStudy/blob/main/baekjoon/b_12933/src/Main.java

자료구조

그리디 알고리즘을 이용하는 문제이다.

• 그리디 알고리즘 : 순간순간 최적의 선택을 하며 문제를 풀어나가는 알고리즘

해당 문제는 입력값에 대한 최소의 오리 수를 매순간마다 판단하여 찾아나가야 하기에 그리디 알고리즘이라고 할 수 있다.
https://adjh54.tistory.com/212

중점을 둔 부분

1. 시간복잡도 O(n)
2. hashMap을 사용하여 O(1)의 시간복잡도 활용 (해시코드화 된 key 덕분)

주요 로직

k가 등장했을때, 최소 오리의 수를 판단하는 것이 내 코드의 핵심 부분이다.
minus를 판단하는 부분은 다음을 참고하라.

if문은 전체적으로 3가지로 구성되어 있다.

* q>k && minus = 0 (아직 minus 값을 초기화 하지 않은 경우를 의미)
* q=k && 최소 오리수가 0인 경우 (아직 최소 오리수 카운팅 하지 않은 경우 의미)
* q-k > 기존 minus (최소 오리 수를 카운팅 한 후, 새로운 오리가 등장한 경우)