[백준] 1141번 접두사 문제! (silver 1

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		int n=Integer.parseInt(br.readLine());
		ArrayList<String> arr=new ArrayList<String>();
		for(int i=0; i<n; i++) {
			arr.add(br.readLine());
		}
		bw.write(set(arr)+"");
		bw.flush();
	}
	public static int set(ArrayList<String> arr) {
		String a;
		String b;
		int removed=0;//리스트에서 a가 삭제되었으면 1, 삭제되지 않았으면 0
        
        //i의 크기를 단어의 삭제여부에 따라 계속 바꾸어 줄 것이므로 증가식 생략.
		for(int i=0; i<arr.size();) {
			for(int j=0; j<arr.size(); j++) {
				if(i==j) {
					continue;
				}
				a=arr.get(i);
				b=arr.get(j);
                //a가 다른 단어와 겹치면 리스트에서 삭제한다.
                //과감하게 삭제를 해버리는 이유는, 먼저 이 문제는 접두사로 겹치지 않는
                //최대의 부분집합을 구하라고 한다. 이 말은 바꾸어 말하면, 다른 단어와 접두사로 겹치는
                //단어가 있다면, 그 단어를 삭제하면 되는 것이다. 
                //다른 단어와 겹치는 단어가 삭제된다면, 남는 단어끼리는 겹치지 않을 것이니 말이다.
                
                //만약 같은 단어가 여러개 있다고 가정해보자, 만약 같은 단어가 3개일 경우,
                //리스트에서 같은 단어가 2개째 까지는 똑같은 단어가 있으므로, 삭제된다.
                //하지만 3번째에서는 그 단어 혼자 생존하고 나머지는 이미 지워진 상태이므로,
                //이 단어와 다른 단어들과의 관계만 비교하면 되는것이다. 
                
                //간단하게 정리하면, list에 처음에 모든 요소를 넣고서, 
                //인덱스 0부터 다른 단어의 접두사가 되는 단어들을 모두 삭제한다.
                //그 단어를 삭제하면 list의 인덱스와 사이즈가 바뀌므로 다시
                //index 0부터 비교를 한다. 단어가 삭제되지 않으면, 그 index는 문제 x
                //이말은 다음 index부터 비교하면 되는 것이다. 
                //removed==0일 경우이므로 i++;
                //그렇다면 남는 단어끼리는 서로의 접두사가 되는 일이 발생하지 않으므로,
                //그 list의 사이즈가 결국은 최대크기의 부분집합이 되는 것이다. 
              
     	
        		
                //두 단어가 처음 시작하는 알파벳이 같을경우,
                //a를 나머지 단어들 b에 비교하는 것이므로, 
                //a.length가 b.length보다 작거나 같아야 a가 b에 접두사로 포함될 수있는 것이므로분류
                //b를 a의 크기 만큼 substring해서 두 단어가 같은지 비교
                //같을경우 list 에서 a를 삭제하고, removed에 1을 넣어서 삭제를 한 것을 표시.
				
                if(a.charAt(0)==b.charAt(0)) {
					if(a.length()<=b.length()) {
						if(a.equals(b.substring(0,a.length()))) {
							arr.remove(i);
							removed=1;
							break;
						}
					}
				}
				removed=0;
			}
            //만약 지워졌으면 다시 index 0부터 비교해야 하므로, 0대입
            //아니면 다음 인덱스 단어를 살펴보기 위해 i+1;
			
            i= removed==0 ? i+1:0;
			
            //arr의 크기가 1일때는 removed는 계속 0이므로 반복문이 무한 반복되므로
            //이 경우를 분류해서 break
            
            if(arr.size()==1) {
				break;
			}
		}
		return arr.size();
	}
}

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

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

        int n=Integer.valueOf(br.readLine());
        ArrayList<String> arr=new ArrayList<>();

        for(int i=0; i<n; i++){
            arr.add(br.readLine());
        }
        Collections.sort(arr, new Comparator<String>(){
            public int compare(String o1, String o2){
                return -(o1.length()-o2.length());
            }
        });

        ArrayList<String> map=new ArrayList<>();
        map.add("1");
        for(int i=0; i<arr.size(); i++){
            String temp=arr.get(i);
            boolean is=true;
            for(int j=0; j<map.size(); j++){
                String com=map.get(j);
                if(temp.length()>com.length()){
                    continue;
                }
                else{
                    if(temp.equals(com.substring(0,temp.length()))){
                        is=false;
                        break;
                    }
                }
            }
            if(is){
                map.add(temp);
            }
        }
        bw.write(map.size()-1+"");
        bw.flush();
    }
}

//23.12.26일 풀이. 예전에 비해 상당히 간결해진것 같다 vv
//사이에 랭크가 silver1로 올랐는 것 같다. 수정반영