Today's Algorithm(2019-02-22)

최근 여러 일로 바빠서 알고리즘 정리를 제대로 못했네요. 그 동안 총 5문제를 풀었는데요. 어려웠던 2문제의 포인트만 정리해볼게요.

 

방금그곡

이 문제는 요구사항을 제대로 이해하는 것이 중요합니다. 각 음은 1분에 1개씩 재생된다는 점, 한 음악을 중간에 끊을 경우 원본에 기억한 멜로디가 들어있더라도 그 곡이 아닐 수 있다는 점이 중요합니다. 즉, 해당 재생시간 동안 멜로디를 구성하고 그 안에 기억한 멜로디가 들어있는지 확인하는 것이 핵심이죠.

 

재생시간의 중요성을 파악하지 못하고, String에서 사용할 수 있는 좋은 메서드를 활용하지 못하여 테스트 케이스 1개를 남겨두고 다른 사람의 코드를 참고했는데요. 결국 제가 문제를 제대로 이해하지 못했다는 것을 깨닫고 핵심 로직들을 조금 수정하였습니다.

 

참고한 부분은 다음과 같습니다.

• 이 문제에서 #이 들어있는 음을 처리하는 것이 힘든데요. 물론 비교를 통해서 할 수 있지만 가장 쉬운 방법은 String의 replace를 이용하는 방법입니다. 그리고 다른 문자로 치환을 하는 것이죠.
• 재생시간 동안 원본에서 한 음씩 이어붙인 다음 그 안에 기억하는 멜로디가 있는지 확인합니다.

class Solution {
    public String solution(String m, String[] musicinfos) {
        List<Song> answer = new ArrayList<>();
        List<Song> list = init(musicinfos);

        for (Song song : list) {
            if (matchCheck(parse(m), song)) answer.add(song);
        }
        Collections.sort(answer);

        if (answer.isEmpty()) return "(None)";
        return answer.get(0).name;
    }

    private List<Song> init(String[] musicinfos) {
        List<Song> list = new ArrayList<>();
        for (int i = 0; i < musicinfos.length; i++) {
            String[] splittedInfo = musicinfos[i].split(",");
            list.add(new Song(i + 1, timeDifference(splittedInfo[0], splittedInfo[1]), splittedInfo[2], parse(splittedInfo[3])));
        }
        return list;
    }

    public int timeDifference(String time1, String time2) {
        int[] splittedTime1 = split(time1);
        int[] splittedTime2 = split(time2);
        LocalTime localTime1 = LocalTime.of(splittedTime1[0], splittedTime1[1]);
        LocalTime localTime2 = LocalTime.of(splittedTime2[0], splittedTime2[1]);
        return (int) localTime1.until(localTime2, MINUTES);
    }

    private int[] split(String time) {
        int[] output = new int[2];
        String[] splittedTime = time.split(":");
        output[0] = Integer.parseInt(splittedTime[0]);
        output[1] = Integer.parseInt(splittedTime[1]);
        return output;
    }

    public boolean matchCheck(String m, Song song) {
        StringBuilder sb = new StringBuilder();

        int j = 0;
        for (int i = 0; i < song.playTime; i++) {
            j = i % song.notes.length();
            sb.append(song.notes.charAt(j));
        }
        return sb.toString().contains(m);
    }

    public String parse(String s) {
       return s.replace("C#", "c").replace("D#", "d").replace("F#", "f").replace("G#", "g").replace("A#", "a");
    }
}

class Song implements Comparable<Song> {
    int index;
    int playTime;
    String name;
    String notes;

    public Song(int index, int playTime, String name, String notes) {
        this.index = index;
        this.playTime = playTime;
        this.name = name;
        this.notes = notes;
    }

    @Override
    public int compareTo(Song o) {
        if (o.playTime == playTime) {
            return index - o.index;
        }
        return o.playTime - playTime;
    }
}

 

 

자동완성

기존 방식이 시간초과가 발생하여 Trie라는 자료구조를 직접 만들어 구현하였습니다. 처음 만들어보는거라 쉽진 않더라구요. Trie는 쉽게 말하면 Tree 구조인데요. 보통 단어에 대해 빠르게 접근하기 위해 사용합니다. 예를들어 guild가 있다면 g밑에 u, u 밑에 i가 있게 하는 구조입니다. guild말고 gua가 있었다면 u미에 i외에 a가 더 있겠죠.

 

이렇게 구현하고 나서 문제를 풀 때 간과한 점이 있는데요. 그건 passCount입니다. 몇 개가 지나갔는지인데요. 만약 1개가 지나갔는 지점이 있으면 그게 자기 자신 밖에 없으니 자동완성할 수 있는 조건이 된 것이지요. 그렇기 때문에 passCount가 있는 것이 중요합니다.

class Solution {
    public int solution(String[] words) {
        int answer = 0;

        Map<Character, Node> map = init(words);
        for (String word : words) {
            Map<Character, Node> innerMap = map;
            char[] chars = word.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                char c = chars[i];
                Node thisNode = innerMap.get(c);
                if (isFullWord(i, chars) || uniqueCheck(thisNode)) {
                    answer += i + 1;
                    break;
                }
                innerMap = thisNode.map;
            }
        }
        return answer;
    }

    private boolean uniqueCheck(Node thisNode) {
        return thisNode.passCount == 1;
    }

    private boolean isFullWord(int i, char[] chars) {
        return chars.length - 1 == i;
    }

    public Map<Character, Node> init(String[] words) {
        Map<Character, Node> map = new HashMap<>();
        for (String word : words) {
            Map<Character, Node> innerMap = map;
            for (char c : word.toCharArray()) {
                Node thisNode = innerMap.getOrDefault(c, new Node());
                thisNode.passCount++;
                innerMap.put(c, thisNode);
                innerMap = innerMap.get(c).map;
            }
        }
        return map;
    }

}

class Node {
    int passCount = 0;
    HashMap<Character, Node> map = new HashMap<>();
}