더 이상 물러설 곳이 없다

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

각 작업의 진행상태와 작업속도를 담은 배열 int[] progresses, int[] speeds가 주어진다.

작업이 완료되어 배포될 때마다 몇 개의 작업이 배포되는지를 담은 배열을 반환해야한다.

1. 작업의 진도가 100까지 도달해야 새로운 기능을 배포할 수 있다.

2. 앞의 작업이 배포되기 전에 뒤의 작업이 배포될 수 없다. 뒤의 작업이 먼저 완료되더라도 앞이 끝날 때까지 기다렸다가 앞의 작업이 완료되면 함께 배포된다.

풀이 .

class Solution {
    public ArrayList<Integer> solution(int[] progresses, int[] speeds) {
        ArrayList<Integer> answer = new ArrayList<Integer>();

        ArrayList<Integer> pList = new ArrayList<Integer>();
        ArrayList<Integer> sList = new ArrayList<Integer>();
        for(int i = 0; i < progresses.length; i++) {
            pList.add(progresses[i]);
            sList.add(speeds[i]);
        }

        while(!pList.isEmpty()) {
            while(pList.get(0) < 100) {
                for(int i = 0; i < pList.size(); i++) {
                    pList.set(i, pList.get(i) + sList.get(i));
                }
            }
            int cnt = 0;
            while(!pList.isEmpty() && pList.get(0) >= 100) {  // 완료되지 않은 작업 있으면 바로 중지
                pList.remove(0);
                sList.remove(0);
                cnt++;
            }
            answer.add(cnt);
        }
        return answer;
    }
}

progress와 speed를 ArrayList로 옮겨 완료된 작업을 하나씩 삭제하며 진행했다.

맨 앞의 작업의 진도가 100이 될 때까지 모든 작업이 각자 자신의 속도대로 진도를 나간다.

맨 앞이 100이 됐다면 100 미만의 작업이 나올 때까지 앞에서부터 모두 제거하며 개수를 센다.

추가

java.util.ConcurrentModificationException
처음에 짠 코드에서 위 에러가 발생했다. 

원인은, 다음과 같다.

    for(int progress : pList) {
        if(progress >= 100) {
            pList.remove(0);
            sList.remove(0);
            cnt++;
        }else {
            break;
        }
    }

pList에 대한 반복을 돌리면서 pList.remove()를 실행했기 때문이다.

다음과 같이 코드를 수정했고 java.lang.nullpointerexception이 발생했다.

while(pList.get(0) >= 100) {
	pList.remove(0);
	sList.remove(0);
	cnt++;
}

반복 초반에는 상관이 없지만 마지막까지 가서 모든 원소가 지워지게 되면 pList는 비어있기 때문에 널포인트 예외가 발생한다.

!pList.isEmpty()를 추가하여 정답 코드를 완성하였다. 

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

초단위로 주식의 가격을 담은 int[] prices가 주어진다. (인덱스 한 칸 당 1초)

각 초를 시점으로 하여 주식 가격이 몇 초 동안 떨어지지 않는지 기록한 배열을 반환해야한다.

주의할 점은 1초 뒤에(바로 다음 인덱스에서) 가격이 떨어지는 경우는 1초 동안 떨어지지 않은 것으로 본다.

마지막 인덱스는 그 뒤의 가격이 존재하지 않기 때문에 0초로 한다.

풀이 .

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        for(int i = 0; i < prices.length; i++) {
            int time = 0;
            for(int j = i + 1; j < prices.length; j++) {
                // 다음 초에 가격이 떨어지더라도 그 초까지는 카운트를 해야한다
                time++;
                // 가격이 떨어지면 카운트 중지
                if(prices[i] > prices[j]) {
                    break;
                }
            }
            answer[i] = time;
        }
        return answer;
    }
}

주석으로 표시한 사항만 조심하면 되는 문제

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

각 노래들의 장르와 플레이 수를 담은 String[] genres, int[] plays가 주어진다.

배열의 인덱스를 각 노래의 고유번호로 한다.

이 중 몇 가지 노래를 뽑아 베스트 앨범을 만들고자 한다.

베스트 앨범 조건

1. 장르 별로 두 개의 곡을 선정한다. (장르에 속한 곡이 하나 뿐이라면 하나만 선정)

2. 장르 별 총 재생 수가 많은 장르부터 뽑는다. 

3. 같은 장르 내에서 순서는 재생 수의 내림차순이다.

4. 재생 수가 같을 경우 고유 번호(인덱스)의 오름차순으로 한다.

풀이 .

import java.util.*;

//1. 장르 별로 두 개의 곡을 선정한다. (장르에 속한 곡이 하나 뿐이라면 하나만 선정)
//2. 장르 별 총 재생 수가 많은 장르부터 뽑는다.
//3. 같은 장르 내에서 순서는 재생 수의 내림차순이다.
//4. 재생 수가 같을 경우 고유 번호(인덱스)의 오름차순으로 한다.

class Song implements Comparable<Song> {
    int index;
    int play;

    public Song() {}
    public Song(int index, int play) {
        this.index = index;
        this.play = play;
    }

    @Override
    public int compareTo(Song o) {
        if (this.play != o.play) {
            if (this.play > o.play) { return -1; }
            else { return 1; }
        } else {
            if (this.index < o.index) { return -1; }
            else { return 1; }
        }
    }
}

class Solution {
    public ArrayList<Integer> solution(String[] genres, int[] plays) {
        // 장르 별 총 재생 수 세기
        Map<String, Integer> jenreHm = new HashMap<String, Integer>();
        for(int i = 0; i < genres.length; i++) {
            String jenre = genres[i];
            if(jenreHm.get(jenre) == null) {
                jenreHm.put(jenre, plays[i]);
            }else {
                jenreHm.put(jenre, jenreHm.get(jenre) + plays[i]);
            }
        }

        // 총 재생 수의 내림차순으로 정렬
        // List에 옮겨 정렬한 후 LinkedHashMap으로 넘겨 순서 유지
        List<Map.Entry<String, Integer>> list = new LinkedList<Map.Entry<String, Integer>>();
        for(Map.Entry<String, Integer> entry : jenreHm.entrySet()) {
            list.add(entry);
        }
        Collections.sort(list, (o1, o2) -> o2.getValue().compareTo(o1.getValue()));
        Map<String, Integer> sortedJenreHm = new LinkedHashMap<String, Integer>();
        for(Map.Entry<String, Integer> entry : list) {
            sortedJenreHm.put(entry.getKey(), entry.getValue());
        }

        // Map<String, ArrayList<Song>>으로 멀티 맵 구현
        Map<String, ArrayList<Song>> multiHm = new LinkedHashMap<String, ArrayList<Song>>();
        for(String jenre : sortedJenreHm.keySet()) {
            multiHm.put(jenre, new ArrayList<Song>());
        }

        // 장르 별 노래 저장. 이때 장르 별 총 재생 수 내림차순 정렬은 완료되어있음
        for(int i = 0; i < genres.length; i++) {
            String genre = genres[i];
            multiHm.get(genre).add(new Song(i, plays[i]));
        }

        // 장르 별 최다 재생 곡 2개 뽑아서 저장
        ArrayList<Integer> ansList = new ArrayList<Integer>();
        for(ArrayList<Song> aList : multiHm.values()) {
            Collections.sort(aList);
            // 장르에 곡이 하나 뿐이면 하나만 저장
            ansList.add(aList.get(0).index);
            if(aList.size() >= 2) {
                ansList.add(aList.get(1).index);
            }
        }
        return ansList;
    }
}

1. 최다 재생 수가 많은 장르부터 수록해야 하므로 hm을 통해 장르 별 총 새생 수 먼저 파악

2. LinkedList를 사용해 총 재생 수로 내림차순 정렬 후 LinkedHashMap으로 옮겨 그 순서를 유지 (그냥 HashMap은 입력 순서 유지되지 않아 정렬이 해쳐짐)

3. 장르 안의 노래들 사이에서도 정렬이 필요. Song 클래스를 만들어 정렬 기준 명시 (play 내림차순, index 오름차순)

4. Map<String, ArrayList<Song>>으로 멀티 맵 구현. 장르 별로 자신의 노래를 저장할 리스트를 갖는다.

5. 각 장르에 해당하는 Song을 모두 담고 이를 내림차순 정렬하여 인덱스 0, 1의 원소(상위 2곡)를 정답 리스트에 저장

너무 주먹구구식의 풀이가 아닌가 싶다. 이정도 방법도 생각하는데 꽤 오랜 시간이 걸렸다.

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

이차원 배열 String[][] clothes가 주어진다.

clothes : { {옷이름, 옷종류}, {옷이름, 옷종류}, ... {옷이름, 옷종류} }

주어진 옷들로 만들 수 있는 조합의 수를 반환하는 문제.

단, 각각의 옷은 입을 수도 안 입을 수도 있으나 아무것도 안 입는 경우는 없다.

풀이 .

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

class Solution {
    public int solution(String[][] clothes) {
        // clothes : [{옷이름, 옷종료}, {옷이름, 옷종류}, ... , {옷이름, 옷종류} ]
        int answer = 1;

        Map<String, Integer> hm = new HashMap<String, Integer>();
        for(String[] cloth : clothes) {
            String key = cloth[1];  // 옷 종류를 key로 사용

            if(hm.get(key) == null) {
                hm.put(key, 2);  // 안 입는 경우도 고려하여 2부터 시작
            }else {
                hm.put(key, hm.get(key) + 1);
            }
        }

        for(Integer num : hm.values()) {
            answer *= num;
        }
        answer--;  // 아무것도 안 입는 경우는 없음
        return answer;
    }
}

옷의 이름은 중요하지 않다.

옷의 종류를 key로 잡고 HashMap을 사용해 종류별로 몇 개의 옷이 있는지 센 다음 그걸 모두 곱하면 된다.

옷을 입지 않는 경우, 아무것도 입지 않는 경우에 대한 고려를 해줘야한다.

O(n)으로 처리 가능

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가 완주하지 못한 선수.