반응형
2204번 문제 도비의 난독증 테스트
문제 난이도를 올렸더니 데이터 저장방식이 조금 더 까다로워진 듯 하다.
이번에도 ascii활용문제 조건 보고 데이터를 많이 저장할 필욘 없는 듯 하다. 최종적으로
사전상 가장 앞에 있는 단어 하나만 출력이니
종료조건 0을 잘 생각해서 구현해봐야겠다.
compare메서드 쓰면 편할거 같긴 한데 한번 직접 비교하는 코드 만들어서 해보기
-------
hint
while문 조건부에 입력받고 0이 아닐 때 반복 0을 입력 시 반복 종료
사전순인걸 기억해야함, 각 입력마다 사전순 앞의 값은 list에 add
-------
반응형
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 | 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; } } | cs |
실행시간 - 264ms
구현 다했는데 사전순의 마지막 반례를 생각못해서 계속 틀렸다.
찾은 반례
2
aAab
aAa
0
사전 순이라는 것은 다른 길이지만 바로 앞까지 길이와 알파벳이 같을 때 길이가 짧은 단어가 사전의 앞에 놓인다는 것을 말하는데, 이 부분을 놓쳤었다.
예를 들어, aaa aaaa가 있다고 가정했을 때 aaa와 aaaa는 세번째 자리까지는 같은 알파벳이지만, 뒤의 한글자로 단어의 길이가 나뉘는데 해당 부분을 해결하는 코드를 추가하자마자 문제해결이 되었다.
물론 코드는 그냥 돌아가게만 만들어둠..... 처리속도 등수 보니까 자바에서 거의 최하위권 ㅋㅋㅋ...
반응형
'공부 > Algorithm' 카테고리의 다른 글
| 백준 1193번 분수찾기 자바로 풀어 본 짧은 글 (0) | 2022.12.20 |
|---|---|
| 백준 2869번 달팽이는 올라가고 싶다 자바로 풀어 본 짧은 글 (0) | 2022.12.18 |
| 백준 4447번 좋은놈 나쁜놈 자바로 풀어 본 짧은 글 (0) | 2022.12.18 |
| 백준 13458 시험 감독 자바로 풀어 본 짧은 글 (0) | 2022.12.16 |
| 백준 15953 상금 헌터 자바로 풀어 본 짧은 글 (0) | 2022.12.16 |
