백준 2204번 도비의 난독증 테스트 자바로 풀어 본 짧은 글

2204번 문제 도비의 난독증 테스트

문제 난이도를 올렸더니 데이터 저장방식이 조금 더 까다로워진 듯 하다.
이번에도 ascii활용문제 조건 보고 데이터를 많이 저장할 필욘 없는 듯 하다. 최종적으로
사전상 가장 앞에 있는 단어 하나만 출력이니
종료조건 0을 잘 생각해서 구현해봐야겠다.
compare메서드 쓰면 편할거 같긴 한데 한번 직접 비교하는 코드 만들어서 해보기

 

-------

hint

while문 조건부에 입력받고 0이 아닐 때 반복 0을 입력 시 반복 종료
사전순인걸 기억해야함, 각 입력마다 사전순 앞의 값은 list에 add

-------

반응형

Solution

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        dicfirst dic = new dicfirst();
        Scanner sc = new Scanner(System.in);
        String first = new String();
        
        List<String> list = new ArrayList<String>(1000);
        int n;
        int count = 0;
        
        while((n = Integer.parseInt(sc.nextLine())) != 0) {
            
            String[] s = new String[n];
        
            for(int i = 0; i < n; i++) {
                s[i] = sc.nextLine();
            }
            first = s[0];
            //사전앞단어 구한 후 배열저장 or list저장
            //ascii A = 65 + 26(범위 65~90) / a = 95 + 26(범위 97~122)
            
            for(int i = 0; i < n; i++) {
                first = dic.go(first, s[i]);
            }
            
            list.add(first);//사전상 앞단어를 저장해둠
            count++;
        }
        for(int i = 0; i < count; i++) {
            System.out.println(list.get(i));
        }
 
    }
}
 
 
class dicfirst {
    
    String go(String a, String b){
        if(a != null) { // first문자열이 아직 저장되어있지 않다면 a는 null상태 - 바로 b return
            int count = 0;
            if(a.length() <= b.length()) {
                count = a.length();
            }
            else {
                count = b.length();
            }
            
            for(int i = 0; i < count; i++) {
                int compareOne = a.charAt(i);
                int compareTwo = b.charAt(i);
                if( 65 <= compareOne && compareOne <= 90) { // 대문자일 때 소문자로 변환 (+32)
                    compareOne += 32;
                }
                if( 65 <= compareTwo && compareTwo <= 90) { // 대문자일 때 소문자로 변환 (+32)
                    compareTwo += 32;
                }
                if(97 <= compareOne && compareOne <= 122 
                        && 97 <= compareTwo && compareTwo <= 122 ) {
                    if(compareOne < compareTwo) {return a;}
                    else if(compareOne > compareTwo) {return b;}//==미구현의도 : 같으면 다음 비교로 넘어가게끔 설계 
                }
            }
            if(a.length() <= b.length()) {
                return a;
            }
            else {
                return b;
            }
        }
        return b;
    }
}

실행시간 - 264ms

구현 다했는데 사전순의 마지막 반례를 생각못해서 계속 틀렸다.

찾은 반례

 

2
aAab
aAa
0

사전 순이라는 것은 다른 길이지만 바로 앞까지 길이와 알파벳이 같을 때 길이가 짧은 단어가 사전의 앞에 놓인다는 것을 말하는데, 이 부분을 놓쳤었다.
예를 들어, aaa aaaa가 있다고 가정했을 때 aaa와 aaaa는 세번째 자리까지는 같은 알파벳이지만, 뒤의 한글자로 단어의 길이가 나뉘는데 해당 부분을 해결하는 코드를 추가하자마자 문제해결이 되었다.
물론 코드는 그냥 돌아가게만 만들어둠..... 처리속도 등수 보니까 자바에서 거의 최하위권 ㅋㅋㅋ...