더 이상 물러설 곳이 없다

programmers.co.kr/learn/courses/30/lessons/42577

전화번호 목록이 담긴 String[] phone_book이 주어진다.

등록된 번호들 중 다른 번호의 접두어로서 존재하는 번호가 있는지 찾는 문제.
(접두어가 존재하면 false, 존재하지 않으면 true를 반환. 반대여야 하는 거 아닌가..?)

풀이 1.

import java.util.Arrays;
import java.util.Comparator;

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public boolean solution(String[] phone_book) {
        // String의 길이순으로 정렬
        Arrays.sort(phone_book, Comparator.comparing(String::length));

        // O(n^2) 시간 소요..
        for(int i = 0; i < phone_book.length - 1; i++) {
            for(int j = i + 1; j < phone_book.length; j++) {
                // charAt()으로 하나씩 검사하지 않고 substring으로 한 번에 처리
                int len = phone_book[i].length();
                String sub = phone_book[j].substring(0, len);
                if (phone_book[i].equals(sub)) {  // 접두어 존재
                    return false;  // 존재'할' 경우에 false 반환임. 헷갈림 주의
                }
            }
        }
        return true;
    }
}

String[] phone_boo의 최대길이는 1,000,000 (10^6)이기 때문에 O(n^2)의 방식으로는 시간초과가 나야한다.

근데 안 나길래 그냥 O(n^2)로 풀었다. (테스트케이스가 좀 허술한 듯) 더 효율적인 방법을 모르겠다.

그냥 Arrays.sort()를 사용할 경우 String의 길이 순으로 정렬할 수 없었다.

구글링을 통해 Arrays.sort()의 두번째 파라미터를 찾아 길이순으로 정렬할 수 있었다.

처음엔 charAt()를 통해 phone_book[i].length()만큼 반복하며 [i]와 [j]의 char를 하나씩 비교하려고 했었다.

그 후 substring()을 통해 시간복잡도를 줄일 수 있었다. (그래봤자 O(n^2)이지만..)

풀이 2.

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

프로그래머스의 '다른 사람의 풀이'를 통해 startWith()에 대해 알게 되었다.

시간복잡도는 동일하지만 길이순으로 정렬할 필요도 없고 코드도 더 직관적이다.

programmers.co.kr/learn/courses/30/lessons/42576

참가자 배열 String[] participant, 완주자 배열 String[] completion이 주어진다.

참가자들 중 완주하지 못한 선수가 1명 존재할 때 이 선수의 이름을 반환하는 문제.

해시 태그로 분류되었지만 정렬만으로도 풀 수 있다.

풀이 1. 

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        Arrays.sort(participant);
        Arrays.sort(completion);

        for(int i = 0; i < completion.length; i++) {
            if(!participant[i].equals(completion[i])) {
                answer = participant[i];
                break;
            }
            
            // completion의 마지막까지 전부 같다면 남은 한 명이 정답
            if(i == completion.length - 1) {
                answer = participant[i + 1];
            }
        }
        return answer;
    }
}

Arrays.sort()를 사용해 두 배열을 모두 정렬한 후 원소들을 차례로 비교한다.

다른 원소가 등장하는 순간 그 놈이 정답. 반복 종료.

마지막 원소까지 모두 같다면 participant에 남은 마지막 원소가 정답.

풀이 2.

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        Map<String, Integer> hm = new HashMap<String, Integer>();

        // 참가자 수만큼 value 증가
        for(String p : participant) {
            // 동명이인을 고려해야한다
            if(hm.get(p) == null) {
                hm.put(p, 1);
            }else {
                hm.put(p, hm.get(p) + 1);
            }
        }

        // 완주자 수만큼 value 감소
        for(String c : completion) {
            hm.put(c, hm.get(c) - 1);
        }

        // value가 1인 key가 정답
        for(String key : hm.keySet()) {
            if(hm.get(key) == 1) {
                answer = key;
                break;
            }
        }
        return answer;
    }
}

HashMap 사용한 풀이.

참가자 수만큼 Map.entry의 value를 1씩 증가시킨다. 이때 동명이인 존재하는 경우까지 고려해야한다.

그 후 완주자 수만큼 value를 1씩 뺀다.

value가 1인 key가 완주하지 못한 선수.