[Java] 프로그래머스 : 전화번호 목록[hash, startsWith]

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

 

startsWith : 첫번째 글자부터 문자 포함 여부를 True, False로 출력

endsWith : 마지막 글자부터 역순으로 문자 포함 여부 확인

str = "가나다라마바사"
str.startsWith("가나다")			// True
str.startsWith("가나다마바")		// False

Temp = "안녕하세요! "			// 끝에 공백 한칸 포함
Temp.endsWith("세요! ")		// True
Temp.endsWith("세요!")			// False
Temp.endsWith("! ")			// True

 

 

 

문제

 

 

 

테스트는 통과하나 효율성에서 떨어지는 내가 작성한 코드(Hash사용 X)

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        
        boolean answer = true;
        Arrays.sort(phone_book);
        
        for(int i = 0; i < phone_book.length; i++) {
            for(int j = i + 1; j < phone_book.length; j++) {
                if(phone_book[j].startsWith(phone_book[i])){
                    answer = false;                    
                }
            }
        }
        
        return answer;
    }
}

이중 for문 때문에 효율성이 떨어진다 생각했으나 밑의 코드를 보면 이중 for문을 사용하여도 HashMap을 쓰면 효율성을 통과하는 코드를 볼 수 있다. 

 

 

다른 분들이 작성한 통과한 코드들

import java.util.*;
 
class Solution {
    public boolean solution(String[] phoneBook) {
        Arrays.sort(phoneBook);
        for (int i = 0; i < phoneBook.length - 1; i++){        
            if (phoneBook[i + 1].startsWith(phoneBook[i])){
                return false;
            }
        }
        return true;
    }
}

j 대신 i+1을 해주는 것만으로도 이중 for문 문제 해결..된게 맞는가?

0번과 1번은 비교할 수 있어도 0번과 2번은 어떻게 비교하지? 그래도 통과는 됨.

프로그래머스에서 원하는 Hash는 사용되지 않음

 

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean solution(String[] phoneBook) {
        boolean answer = true;

        Map<String, Integer> map = new HashMap<>();

        for(int i = 0; i < phoneBook.length; i++) {
            map.put(phoneBook[i], i);
        }

        for(int i = 0; i < phoneBook.length; i++) {
            for(int j = 0; j < phoneBook[i].length(); j++) {
                if(map.containsKey(phoneBook[i].substring(0,j))) {
                    answer = false;
                    return answer;
                }
            }
        }
        return answer;
    }
}

 ·  10번 줄 : HashMap Key에 순서를 나타내줄 숫자 입력

 ·  16번 줄 : containsKey(인자)는 맵에 인자로 보낸 Key가 있으면 True, 없으면 False 

                   substring을 통해 자신을 제외한 비교를 위해 하나씩 비교한다는데...(이해가 안됨)

 

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        HashSet<String> set = new HashSet<>();
        Arrays.stream(phone_book).forEach(s -> set.add(s));

        for(String str : set){
            for(int i = 1; i < str.length(); i++){
                if(set.contains(str.substring(0, i))){
                    return false;
                }
            }
        }
        return true;
    }
}

 

 

import java.util.HashMap;
import java.util.Arrays;
class Solution {
    static public boolean solution(String[] phoneBook) {
       Arrays.sort(phoneBook);
       //HashMap mp = new HashMap();

       for(int i=0; i<phoneBook.length-1;i++)
       {
           if(phoneBook[i+1].startsWith(phoneBook[i])) {return false;}
       }
       return true;
    }

    public static void main(String[] args) throws Exception {

        String[] temp = {"119", "97674223", "1195524421"};
        boolean result = solution(temp);
            System.out.println(result);
    }
}