[level.2] 프로그래머스 전화번호 목록 + 삽질

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
• 각 전화번호의 길이는 1 이상 20 이하입니다.

입출력 예제

phone_book	return
[119, 97674223, 1195524421]	false
[123,456,789]	true
[12,123,1235,567,88]	false

이 문제는 엄청나게 삽질도 많이하고 최대한 머리를 쥐어 짜 봤으나 결국 완벽하게는 풀지 못했다.

프로그래머스에서 각각 80점, 50점 맞은 코드를 우선 정리하고 다음에 다시 풀어서 100점을 맞도록 해야겠다.

테스트주도 방식 역시 100점 맞으면 그 때 다시 정리해서 들고오도록 하겠다..

먼저 80점 짜리 코드.

나는 굳이 이 문제를 해시를 써야하나? 라는 생각에 배열과 subString을 사용해서 풀어보았다.

하지만 80점이 나왔고, 혹시나 맵을 써서해야하나 하고 중간만 Map으로 바꿔줘 보았지만 역시 안됐다.

정확도 테스트는 다 맞았지만 효율성에서 문제가 발생했다.

아, 그리고 중간에 3시간씩이나 잡아 먹은 문제가 있었다.

  if (phone_book[0].substring(0, idxLenth).equals(phone_book[i].substring(0, idxLenth)) )

조건문에서 문자열간의 비교이기 때문에 equals로 비교를 했었어야하는데, '=='연산자로 비교해서 true, false 값이 아예 제대로 들어가지를 못했다.

너무 조건만 생각하느라 지나쳐버리고 까먹었었다.

이런 실수를 하지 않도록 주의해야한다.

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedHashMap;
 
 
public class Solution {
   
    public static boolean solution(String[] phone_book) {
        boolean answer = true;
        int lenth = phone_book.length;
        
        int intNum[] = new int[lenth];
        String strNum[] = new String[lenth];
        for (int i = 0; i < lenth; i++) {
            intNum[i] = Integer.parseInt(phone_book[i]);
        }
        Arrays.sort(intNum);
        for (int i = 0; i < lenth; i++) {
            strNum[i] = Integer.toString(intNum[i]);
        }
       
 
 
           /* LinkedHashMap<Integer,String> map = new LinkedHashMap<>();

            for(int i=0; i<lenth; i++){
                map.put(i,num[i]);
            }
            System.out.println("맵[0] : " + map.get(0).length());

            for(String str : strNum){
                if(map.get(str)==null){
                    map.put(1,str);
                }else{
                    int value = map.get(1) + 1;
                    map.put(value,str);
                }
            }
            int idxLenth = map.get(0).length();
            for(int i=1; i<lenth; i++){
                if(map.get(0).substring(0,idxLenth).equals(map.get(i).substring(0, idxLenth))){
                    answer = false;
                    break;
                }else{
                    answer = true;
                }
            }*/
       
        int strLenth = phone_book.length;
        int idxLenth = strNum[0].length();
      
 
        for (int i = 1; i < strLenth; i++) {
 
 
            if (phone_book[0].substring(0, idxLenth).equals(phone_book[i].substring(0, idxLenth)) ) {
                answer = false;
                break;
            } else {
                answer = true;
            }
         
        }
        return answer;
    }
}

효율성 문제는 보통 시간복잡도에 의해 생긴다고한다.

그래서 나는 문자를 오름차순으로 바꾸는 과정에서 너무 시간을 잡아 먹는 것 같아서 메소드를 검색해보니

Arrays.sort(num, String.CASE_INSENSITIVE_ORDER);

숫자 정렬말고 문자도 정렬해주는 메소드가 있어서 이걸 사용하고 오름차순으로 바꿔주던 for문들을 삭제했다.

이렇게 했더니 이번에는 효율성은 다 맞았지만, 정확도테스트에서 다 맞추지 못했다. >> 50점 짜리 코드 

메소드가 오름차순으로 바꾸는 과정에서 아무래도 문제가 있는 것 같다.

하지만 뭐가 잘못됐는지 정확히 알지 못하겠어서 여기서 멈춘 상태이다.

좀 더 고민을 해보고 다시 문제를 풀어봐야겠다.

오늘은 패스...

드디어 100점을 맞았다. 바로 코드를 공유하도록 하겠다.

 
 
public class ContactAddress {
 
    /*public static void main(String[] args) {
        System.out.println(phone_book(new String[]{"119", "97674223", "1195524421"}));
        System.out.println(phone_book(new String[]{"123", "456", "789"}));
        System.out.println(phone_book(new String[]{"1235", "12", "123", "567", "88"}));

    }*/
    //스트링버퍼 사용
    static boolean phone_book(String[] str) {
        int length = str.length;
        StringBuffer sb = new StringBuffer();
        int sbLength = 0;
 
        for (int i = 0; i < length; i++) {
            sb.setLength(0);
            sb.append(str[i]);
            sbLength = sb.length();
            System.out.println("sbLength : " + sbLength);
            for (int j = 0; j < length; j++) {
                if (i == j) {   //자시자신은 비교 할 필요가 없으니
                    continue;
                }
                //나머지 비교
                if ((sbLength <= str[j].length()) && (sb.toString().equals(str[j].substring(0, sbLength).toString()))) {
                    return false;
                }
            }
        }
        return true;
 
    }
}
 

이 문제는 해시에 있었지만 해시로는 도저히 어떻게 풀어야 하는지 감이 오지 않는다.

String으로 연산하는데 시간을 많이 뺏기는 것 같아서 구글링을 하다가 StringBuffer를 사용하는 것을 깨닫고

StringBuffer로 도전.

로직은 위의 코드와 비슷하다.

다만 StringBuffer를 쓰냐 안쓰냐의 차이

- 삽질 끝 -

- 최종 코드 가독성 수정

/*    문제 설명
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항
phone_book의 길이는 1 이상 1,000,000 이하입니다.
각 전화번호의 길이는 1 이상 20 이하입니다.
입출력 예제
phone_book    return
[119, 97674223, 1195524421]    false
[123,456,789]    true
[12,123,1235,567,88]    false*/
 
public class ContactAddress {
 
    /*public static void main(String[] args) {
        System.out.println(phone_book(new String[]{"119", "97674223", "1195524421"}));
        System.out.println(phone_book(new String[]{"123", "456", "789"}));
        System.out.println(phone_book(new String[]{"1235", "12", "123", "567", "88"}));

    }*/
    //스트링버퍼 사용
    static boolean phone_book(String[] str) {
        int length = str.length;
        StringBuffer sb = new StringBuffer();
        int sbLength = 0;
 
        for (int i = 0; i < length; i++) {
            sb.setLength(0);
            sb.append(str[i]);
            sbLength = sb.length();
            //System.out.println("sbLength : " + sbLength);
            for (int j = 0; j < length; j++) {
                if (i == j) {   //자시자신은 비교 할 필요가 없으니
                    continue;
                }
                if (nmgCompare(str[j], sb, sbLength)) {
                    return false;
                }
            }
        }
        return true;
    }
 
    private static boolean nmgCompare(String s, StringBuffer sb, int sbLength) {
        //나머지 비교
        int nmgLength = s.length();
        String nmgString = s.substring(0, sbLength);
        if ((sbLength <= nmgLength && (sb.toString().equals(nmgString))))
            return true;
        return false;
    }
}