Strong Root

프로그래머스 여행경로(tickets) 정답 코드

뿌리튼튼 CS/Algorithm2019. 4. 16. 16:30

난이도 ★★★★☆

 

문제를 보시려면 여기를 클릭

 

 

 

틀리기 쉬운 입출력 예제

입력 출력
{{"ICN", "JFK"}, {"JFK", "ICN"}, {"ICN", "JFK"}, {"JFK", "ICN"}} [ICN, JFK, ICN, JFK, ICN]

 

 

 

힌트

전형적인 너비우선탐색(BFS) 문제이지만 구현이 어렵습니다.

 

1. 위 입출력 예시처럼 동일한 티켓이 여러장 입력될 수도 있다는 점

2. 반드시 모든 티켓을 다 사용해야한다는 점

3. 정렬이 필요한 점

 

구현하실 때, 이미 방문한 녀석인지 체크할 변수가 필요할텐데 Java는 객체지향 언어잖아요?

별도 배열을 두지마시고 저처럼 객체(Ticket.count)로 만드시길 추천드립니다.

익숙치 않아도 노력해보시길!

 

※ String[][] tickets 를 한번 서치하여 ticketSet 을 만들고 싶었는데 count 값을 넣어줄 방법을 못찾아서 tmpCountMap 을 거쳐야만 했습니다. 안거치고 넣을 수 있는 방법이 있을까요?

 

 

 

이하는 코드입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
 
public class Solution {
    public String[] solution(String[][] tickets) {
        Map<Ticket, Integer> tmpCountMap = new HashMap<>();    // 표별 개수 세는 용도로 임시
 
        for (String[] ticketStr : tickets) {
            Ticket ticket = new Ticket();
 
            ticket.start = ticketStr[0];
            ticket.end = ticketStr[1];
 
            Integer count = tmpCountMap.get(ticket);
 
            if (count == null) {
                tmpCountMap.put(ticket, 1);
            } else {
                tmpCountMap.put(ticket, count + 1);
            }
        }
 
        Set<Ticket> ticketSet = new TreeSet<>();
 
        for (Ticket ticket : tmpCountMap.keySet()) {
            int count = tmpCountMap.get(ticket);
            ticket.count = count;    // 위에서 tmpCountMap으로 측정한 count
            ticketSet.add(ticket);
        }
 
        String[] answer = new String[tickets.length + 1];
 
        List<String> path = getPath("ICN", ticketSet);
        path.toArray(answer);
 
        return answer;
    }
 
    private LinkedList<String> getPath(String start, Set<Ticket> tickets) {
        LinkedList<String> path = null;
 
        if (allUsed(tickets)) {
            path = new LinkedList<>();
            path.add(start);
            return path;
        }
 
        for (Ticket ticket : tickets) {
            if (ticket.count < 1 || !ticket.start.equals(start)) {
                continue;
            }
 
            ticket.count--;
            path = getPath(ticket.end, tickets);
            ticket.count++;
 
            if (path != null) {
                path.addFirst(start); // This is why use LinkedList
                break;
            }
        }
 
        return path;
    }
 
    private boolean allUsed(Set<Ticket> tickets) {
        for (Ticket ticket : tickets) {
            if (ticket.count > 0) {
                return false;
            }
        }
 
        return true;
    }
 
    private class Ticket implements Comparable<Ticket> {
        String start;
        String end;
        int count;
 
        @Override
        public int compareTo(Ticket that) {
            int startComp = this.start.compareTo(that.start);
 
            if (startComp != 0) {
                return startComp;
            }
 
            return this.end.compareTo(that.end);
        }
 
        @Override
        public boolean equals(Object arg0) {
            if (!(arg0 instanceof Ticket)) {
                return false;
            }
 
            Ticket that = (Ticket) arg0;
 
            return this.start.equals(that.start) && this.end.equals(that.end);
        }
 
        @Override
        public int hashCode() {
            return (start + "," + end).hashCode();
        }
    }
}
 cs

 

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

프로그래머스 다리를 지나는 트럭 정답 코드  (0) 2019.04.23
프로그래머스 네트워크(computers) 정답 코드  (0) 2019.04.17
프로그래머스 단어 변환(words) 정답 코드  (0) 2019.04.16
프로그래머스 타겟 넘버 정답 코드  (0) 2019.04.16
프로그래머스 프린터(priorities) 정답 코드  (0) 2019.04.16

프로그래머스 단어 변환(words) 정답 코드

뿌리튼튼 CS/Algorithm2019. 4. 16. 10:28

난이도 ★★★★☆

 

문제를 보시려면 여기를 클릭

 

 

 

힌트

전형적인 너비우선탐색(BFS) 문제입니다.

최소값을 찾는 문제이므로 전역(혹은 그런느낌)으로 최소값을 저장할 변수(minCountMap)를 잘 운용하셔야 해요.

 

구현하실 때, 이미 방문한 녀석인지 체크할 변수가 필요할텐데 Java는 객체지향 언어잖아요?
별도 배열을 두지마시고 저처럼 객체(Word.used)로 만드시길 추천드립니다.
익숙치 않아도 노력해보시길!

 

 

 

이하는 코드입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
 
public class Solution {
    private Map<String, Integer> minCountMap;
    private int MAX_COUNT;
 
    public int solution(String start, String target, String[] words) {
        minCountMap = new HashMap<>();
        MAX_COUNT = words.length;
        Set<Word> wordSet = new HashSet<>();
 
        for (String word : words) {
            Word wordObj = new Word();
 
            wordObj.word = word;
            wordObj.used = false;
 
            wordSet.add(wordObj);
        }
 
        int answer = getMinCount(start, target, wordSet);
 
        if (answer > MAX_COUNT) { // no way
            return 0;
        }
 
        return answer;
    }
 
    private int getMinCount(String start, String target, Set<Word> words) {
        Integer minCount = minCountMap.get(start);
 
        if (minCount == null) {
            minCount = MAX_COUNT + 1;
        }
 
        for (Word word : words) {
            if (word.used || !isNext(start, word.word)) {
                continue;
            }
 
            if (target.equals(word.word)) {
                minCount = 1;
                break;
            }
 
            word.used = true;
            int count = getMinCount(word.word, target, words) + 1;
            word.used = false;
 
            if (count < minCount) {
                minCount = count;
            }
        }
 
        minCountMap.put(start, minCount);
        return minCount;
    }
 
    private boolean isNext(String a, String b) {
        int diffCount = 0;
 
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) {
                diffCount++;
 
                if (diffCount > 1) {
                    return false;
                }
            }
        }
 
        return true;
    }
 
    private class Word {
        String word;
        boolean used;
 
        @Override
        public int hashCode() {
            return word.hashCode();
        }
    }
}
 cs

 

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

프로그래머스 네트워크(computers) 정답 코드  (0) 2019.04.17
프로그래머스 여행경로(tickets) 정답 코드  (0) 2019.04.16
프로그래머스 타겟 넘버 정답 코드  (0) 2019.04.16
프로그래머스 프린터(priorities) 정답 코드  (0) 2019.04.16
프로그래머스 쇠막대기(arrangement) 정답 코드  (0) 2019.04.15

프로그래머스 타겟 넘버 정답 코드

뿌리튼튼 CS/Algorithm2019. 4. 16. 10:01

난이도 ★★★☆☆

 

문제를 보시려면 여기를 클릭

 

 

 

힌트

반복문이 아닌 재귀로 풀었습니다.

f(i, t) = f(i + 1, t + n[i]) + f(i + 1, t - n[i])

 

동적계획법(Dynamic Programming)도 사용하였는데, 이부분은 성능을 위한 것이므로 없어도 결과에는 영향이 없습니다.

(헷갈릴시 cache 변수를 제거하시면 됩니다)

 

 

 

이하는 코드입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.HashMap;
import java.util.Map;
 
public class Solution {
    private Map<Integer, Integer>[] cache; // Dynamic Programming
    private int[] numbers;
 
    public int solution(int[] numbers, int target) {
        this.numbers = numbers;
        cache = new HashMap[numbers.length]; // TODO Remove the warning
 
        for (int i = 0; i < numbers.length; i++) {
            cache[i] = new HashMap<>();
        }
 
        int answer = getCount(0, target);
        return answer;
    }
 
    // f(i, t) = f(i + 1, t + n[i]) + f(i + 1, t - n[i])
    private int getCount(int startIdx, int target) {
        if (startIdx >= numbers.length) {
            return 0;
        }
 
        if (startIdx == numbers.length - 1) {
            if (numbers[startIdx] == target || numbers[startIdx] == target * -1) { // Don't forget -1
                return 1;
            } else {
                return 0;
            }
        }
 
        Integer count = cache[startIdx].get(target);
 
        if (count != null) {
            return count;
        }
 
        count = getCount(startIdx + 1, target + numbers[startIdx]) + getCount(startIdx + 1, target - numbers[startIdx]);
        cache[startIdx].put(target, count);
 
        return count;
    }
}
 cs

 

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

프로그래머스 여행경로(tickets) 정답 코드  (0) 2019.04.16
프로그래머스 단어 변환(words) 정답 코드  (0) 2019.04.16
프로그래머스 프린터(priorities) 정답 코드  (0) 2019.04.16
프로그래머스 쇠막대기(arrangement) 정답 코드  (0) 2019.04.15
프로그래머스 H-Index(citations) 정답 코드  (0) 2019.04.15

티스토리툴바