프로그래머스LV2_13

전화번호 목록

접근 과정

1. 배열을 정렬하여 비슷한 번호는 인접하게 배치되도록 한다.
2. 반복문으로 해당 위치의 문자가 다음 문자로 시작하는 문자이면 false 반환
3. 반복문 끝까지 돌면 없는 것이므로 true를 반환

시행착오

• 가장 짧은 길이를 찾아서 그 길이만큼 모두 잘라서 해당하는 접두사가 있는지 체크했는데 반례가 있는 것을 체크하지 못하여 실패했다.
• phone_book = ["123", "1456", "1457"] 이 입력인 경우 3개로 자르면 145가 두 번 들어와 접두사가 아닌데도 false가 반환되는 문제가 있음

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        int min_l = phone_book[0].length();
        for(String phone : phone_book){
            min_l = Math.min(min_l, phone.length());
        }
        Set<String> s = new HashSet<>();
        for(String phone : phone_book){
            String str = phone.substring(0, min_l);
            if(s.contains(str)){
                return false;
            }
            s.add(str);
        }
        return true;
    }
}

해결 코드

• 시행착오를 거치고 정렬하여 인접한 번호 시작을 체크하여 해결

import java.util.*;

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

시간 및 공간 복잡도

• 시간 복잡도(정렬하므로)

• 공간 복잡도

프로세스

접근 과정

1. 우선순위와 우선순위의 인덱스를 기억해야 해서 Process 클래스를 생성
2. 큐에 우선순위와 인덱스로 Process를 넣음
3. 큐를 순회하면서 최댓값과 일치하는 첫 요소를 제거를 하고 해당 요소의 인덱스가 찾고자 하는 위치이면 정지
4. 최댓값과 일치하지 않으면 다시 큐에 추가

시행착오

• 시행착오 없이 접근 과정대로 해결

해결 코드

import java.util.*;

class Solution {
    class Process {
        int priority;
        int index;
        
        Process(int p, int i){
            priority = p;
            index = i;
        }
    }
    
    public int solution(int[] priorities, int location) {
        int answer = 0;
        Queue<Process> q = new LinkedList<>();
        for(int i = 0; i < priorities.length; i++){
            q.add(new Process(priorities[i], i));
        }
        while(!q.isEmpty()){
            Process p = q.poll();
            int[] max = findMax(priorities);
            if(p.priority == max[0]){
                priorities[max[1]] = -1;
                answer++;
                if(p.index == location) break;
            }
            else{
                q.add(p);
            }
        }
        return answer;
    }
    
    private int[] findMax(int[] priorities){
        int max = 0, idx = 0;
        for(int i = 0; i < priorities.length; i++){
            if(max < priorities[i]){
                max = priorities[i];
                idx = i;
            }
        }
        return new int[]{max, idx};
    }
}

시간 및 공간 복잡도

• 시간 복잡도(매번 최댓값을 찾고 큐 전체를 돌아야 함)

• 공간 복잡도(Process 객체를 담는 큐를 생성)

개선

• 우선순위 큐를 사용하고 싶었는데 자바에서 사용하는 방식을 몰라서 문제를 풀고 찾아보고 개선했다.
• 시간 복잡도는 동일하나 좀 더 간단하게 해결 가능!

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int p : priorities) {
            pq.add(p);
        }
        int answer = 0;
        while (!pq.isEmpty()) {
            for (int i = 0; i < priorities.length; i++) {
                if (priorities[i] == pq.peek()) {
                    pq.poll();
                    answer++;
                    if (i == location) {
                        return answer;
                    }
                }
            }
        }
        return answer;
    }
}