[프로그래머스] Lv3 문제풀이8(feat. JAVA)

가장 긴 팬린드롬

class Solution
{
    public int palindrome(int right, int left,  String s) {
        while(right < s.length() && left >= 0 && s.charAt(right) == s.charAt(left)) {
            right++;
            left--;
        }

        return right - left - 1;
    }
    public int solution(String s)
    {
        int answer = 0;

        for(int i = 0; i < s.length(); i++) {
            answer = Math.max(answer, palindrome(i+1, i-1, s));
            answer = Math.max(answer, palindrome(i+1, i, s));
        }

        return answer;
    }
}

 

 

 

합승 택시 요금

import java.util.*;

class Solution {
    ArrayList<Node>[] graph;
    int[] dist;
    public void Dijkstra(int n, int start) {
        boolean[] check = new boolean[n+1];

        dist[start] = 0;
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));

        while (!pq.isEmpty()) {
            int nowVertex = pq.poll().index;

            if(check[nowVertex]) continue;
            check[nowVertex] = true;

            for(Node next : graph[nowVertex]) {
                if(dist[next.index] > dist[nowVertex] + next.cost) {
                    dist[next.index] = dist[nowVertex] + next.cost;
                    pq.offer(new Node(next.index, dist[next.index]));
                }
            }
        }
    }

    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = Integer.MAX_VALUE;

        graph = new ArrayList[n+1];
        for(int i = 0; i <=n; i++) graph[i] = new ArrayList<>();

        for(int[] fare : fares) {
            int v = fare[0];
            int w = fare[1];
            int cost = fare[2];

            graph[v].add(new Node(w, cost));
            graph[w].add(new Node(v, cost));
        }

        boolean[] checked = new boolean[n+1];
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(s, 0));
        while(!queue.isEmpty()) {
            Node cur = queue.poll();
            if(checked[cur.index]) continue;
            checked[cur.index] = true;

            dist = new int[n+1];
            Arrays.fill(dist, Integer.MAX_VALUE);
            Dijkstra(n, cur.index);

            answer = Math.min(dist[s] + dist[a] + dist[b], answer);

            for(Node next : graph[cur.index]) {
                queue.offer(next);
            }

        }

        return answer;
    }
}

class Node implements Comparable<Node>{
    int index;
    int cost;

    public Node(int index, int cost) {
        this.index = index;
        this.cost = cost;
    }

    @Override
    public int compareTo(Node o) {
        return Integer.compare(this.cost, o.cost);
    }
}

 

 

 

[1차] 셔틀버스

import java.util.*;

class Solution {
    class Person implements Comparable<Person>{
        int h;
        int m;
        
        Person(int h, int m) {
            this.h = h;
            this.m = m;
        }
        
        @Override 
        public int compareTo(Person s){
            if(s.h == h) {
                return m - s.m;
            } else {
                return h - s.h;
            }
        }
    }    
    
    public String solution(int n, int t, int m, String[] timetable) {
        String answer = "";
        
        PriorityQueue<Person> plist = new PriorityQueue<>();
        for(String time : timetable) {
            String[] tm = time.split(":");
            plist.add(new Person(Integer.parseInt(tm[0]), Integer.parseInt(tm[1])));
        }
        
        int start_hour = 9, start_min = 0;
        
        for(int i = 0; i < n; i++) {
            int cnt = 0;
            int min = 0;
            int hour = 0;
            while(!plist.isEmpty() && cnt < m) {
                if(plist.peek().h < start_hour){
                    min = plist.peek().m;
                    hour = plist.poll().h;
                    cnt++;
                } else if (plist.peek().h == start_hour && plist.peek().m <= start_min) {
                    min = plist.peek().m;
                    hour = plist.poll().h;
                    cnt++;
                } else {
                    break;
                }
            }
            
            if(i == n - 1) {
                if(cnt == m) {
                    if(min == 0) {
                        start_min = 59;
                        start_hour = hour - 1;
                    } else {
                        start_min = min - 1;
                        start_hour = hour;
                    }
                }
                answer = ((start_hour < 10) ? "0" + Integer.toString(start_hour) : Integer.toString(start_hour)) + ":" + ((start_min < 10) ? "0" + Integer.toString(start_min) : Integer.toString(start_min));
            } else {
                start_min += t;
                if(start_min == 60) {
                    start_hour += 1;
                    start_min = 0;
                }
            }
        }
        
        return answer;
    }
}