[백준] 5052 - 전화번호 목록 (JAVA)

정보

1. 소요시간 : 20분.
2. 문제 사이트 : 백준
3. 문제 수준 : 골드4
4. 문제 유형 : 정렬
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/5052
8. 푼 날짜 : 2023.03.06

1. 사용한 자료구조 & 알고리즘

정렬만을 사용했다.
처음부터 정렬 카테고리를 들어가서 문제를 풀었기 때문에 정렬 문제인 것을 알 수 있었다.

2. 풀이 과정

우선 처음에 실패한 코드는 이렇게 풀었었다.

1. 자료를 정렬한다.
2. i+1 번쨰 자료와 i 번째 자료를 비교하며 String 의 contains 메소드를 사용하고, 만약 contains 메소드가 true 를 하나라도 반환하면 NO 출력

=> 70% 쯤에서 틀렸습니다 출력. 만약에 아예 처음부터 틀렸습니다 라고 나왔으면 내가 문제를 잘못풀었나 ?? 하고 생각했겠지만 70% 쯤에서 틀렸으므로 전체적인 맥락은 맞을 것으로 추정함. 예외가 무엇일지 생각해봤음. 2분 고민하다가 답 찾음. 접두어만을 보므로 만약 12345 와 234 가 있다고 하면 234 는 12345의 접두어가 아니나 contains 메소드가 true 를 출력함. 즉, 접두어 인것만을 봐야함.

따라서 다음과 같이 다시 풀었음.

1. 자료를 정렬한다.
2. i번째 자료와 i + 1 번째 자료 중 더 length() 가 작은 것 만큼 size 를 정함.
3. 처음에 count 라는 변수를 0으로 설정하고, i번쨰 자료와 i+1 번째 자료를 비교해가면서 한글자씩 비교. 두 글자가 같다면 count 를 증가함.
4. 만약 count 의 개수가 size와 같다면 한 단어가 다른 단어의 접두어인것임. 이 경우에는 NO를 출력.
5. 이 외에는 YES 출력.

3. 소스코드

import java.util.*;
import java.io.*;
public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		
		int t=Integer.parseInt(br.readLine());
		while(t-->0) {
			int n=Integer.parseInt(br.readLine());
			String arr[]=new String[n];
			for(int i=0;i<arr.length;i++) {
				arr[i]=br.readLine();
			}
			Arrays.sort(arr);
			boolean status=true;
			
			for(int i=1;i<arr.length;i++) {	
				int size=Math.min(arr[i].length(), arr[i-1].length());
				
				int cnt=0;
				for(int j=0;j<size;j++) {
					if(arr[i].charAt(j)==arr[i-1].charAt(j)) {
						cnt++;
					}
				}
				if(cnt==size) {
					status=false;
					break;
				}
				
			}
			
			if(status) System.out.println("YES");
			else System.out.println("NO");
			
			
		}

	}
}

4. 결과

5. 회고

정렬문제는 가장 자신있는 것중 하나이기 때문에 쉽게 풀었다 !

하루에 백준 1문제 이상 푸는 것을 목표로 하고 있다.

https://solved.ac/profile/anwlro0212