231114 - 탐욕법 : 배열 -> 리스트.contians(), 아스키코드, 좌우이동, 큰 수 만들기

[robert-min]

https://school.programmers.co.kr/learn/courses/30/lessons/42862?language=java

체육복 (배열 -> 리스트.contians())

• 풀이
  1. 학생이 체육복을 가지고 있는지 확인하도록 student 배열 생성
  2. lost, reserve에 contains 함수를 쓰기위해 Arraylist로 변경 후 값 갱신
  3. 체육복을 가지고 있지 않는 학생이 옆의 학생에게 빌리 수 있는지 확인
  4. 체육복을 가지고 있는 학생 수 정답 갱신

     
     import java.util.*;
     import java.util.stream.Collectors;

class Solution {

public int solution(int n, int[] lost, int[] reserve) {
    // 1
    int[] student = new int[n+2];
    List<Integer> lostList = new ArrayList<>(Arrays.stream(lost)
            .boxed().collect(Collectors.toList()));
    List<Integer> reserveList = new ArrayList<>(Arrays.stream(reserve)
            .boxed().collect(Collectors.toList()));

    // 2
    for (int i = 1; i <= n; i++) {
        student[i] = 1;
        if (lostList.contains(i)) {
            student[i]--;
        }
        if (reserveList.contains(i)) {
            student[i]++;
        }
    }

    // 3

    for (int i = 1; i <= n; i++) {
        if (student[i] == 0) {
            if (student[i-1] >= 2) {
                student[i-1]--;
                student[i]++;
            } else if (student[i+1] >= 2) {
                student[i+1]--;
                student[i]++;
            }
        }
    }

// System.out.println(Arrays.toString(student)); int answer = 0; for (int i = 1; i <= n; i++) { if (student[i] >= 1) { answer++; } }

    return answer;
}

}

[robert-min]

https://school.programmers.co.kr/learn/courses/30/lessons/42860?language=java

조이스틱(아스키코드, 좌우이동)

• 주석 참고

• 설명 참고

  class Solution {
  public int solution(String name) {
      int answer = 0;
      int n = name.length();
      int idx;
      int move = n - 1;
  
      for (int i = 0; i < n; i++) {
          // 1 : 글자 변환
          answer += Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1);
  
          // 2 좌우 이동 확인
          idx = i+1;
          while (idx < n && name.charAt(idx) == 'A') {
              idx++;
          }
          // 순서대로 이동, 처음부터 반대로 이동한 것중 더 빠른 경우
          move = Math.min(move, i * 2 + n - idx);
          move = Math.min(move, (n - idx) * 2 + i);
  
      }
      return answer + move;
  }
  }

[robert-min]

https://school.programmers.co.kr/learn/courses/30/lessons/42883?language=java

큰 수 만들기

• 풀이 : 주석 참고

• 포인트 : 처음부터 k자리까지 수 중 가장 큰 수가 시작점. 해당 시작점부터 leftNum을 넘지 않는 수 중 가장 큰 수를 선택

  class Solution {
  public String solution(String number, int k) {
      StringBuilder answer = new StringBuilder();
      int len = number.length() - k;
      int start = 0;
  
      while (start < number.length() && answer.length() != len) {
          // leftNum - k 만큼의 자리수를 구해야 함
          int leftNum = k + answer.length() + 1;
          int max = 0;
  
          for (int j = start; j < leftNum; j++) {
              // 자리수까지 가장 큰 수를 찾고 시작점 정의
              if (max < number.charAt(j) - '0') {
                  max = number.charAt(j) - '0';
                  // 가장 큰 수의 다음 수 부터 탐색
                  start = j+1;
              }
          }
          // 가장 큰 수 정의
          answer.append(Integer.toString(max));
      }
  
      return answer.toString();
  }
  }

[robert-min]

https://school.programmers.co.kr/learn/courses/30/lessons/42885?language=java#

구명보트

• 풀이 : 주석 참고
• 포인트 : 예외 케이스 확인, 가벼운 사람 부터 탈 경우 어차피 최대 인원이 2명이기 때문에 손해임

  
  import java.util.*;

class Solution { public int solution(int[] people, int limit) {

    Arrays.sort(people);
    // 1. 최대 2명만 탑승할 수 있기 때문에 가장 가벼운 1명 + 무거운 1명이 탑승할 수 있는지 확인
    int answer = 0;
    int start = 0;
    int end = people.length - 1;
    while (start <= end) {
        if (people[start] + people[end] <= limit) {
            start++;
        }
        // 2. limit을 초과하면 무거운 사람만 배를 탐.
        end--;
        answer++;
    }

    return answer;
}

}

[robert-min]

https://school.programmers.co.kr/learn/courses/30/lessons/42861

섬 연결하기

• 포인트 : 다익스트라는 가중치가 최소인 동선만 찾아간다.
• 풀이 :
  0. Node 클래스를 별도로 사용해 정점과 가중치를 관리
  1. List에 ArrayList를 추가 후 값 입력
  2. 다익스트라로 사용된 가중치 값 dist 저장
     • 이 문제는 특정 노드에서 특정 노드까지의 최소 값을 찾는게 아닌 각 간선의 가중치가 필요하기 때문에 값을 누적하지 않음.
  3. dist 값을 합하여 리턴

     
     import java.util.*;

// 0 class Node implements Comparable { int nodeNum; int weight;

public Node(int nodeNum, int weight) {
    this.nodeNum = nodeNum;
    this.weight = weight;
}

@Override
public int compareTo(Node o) {
    return weight - o.weight;
}

}

class Solution {

static List<ArrayList<Node>> graph;
static boolean[] visited;
static int[] dist;

static void dikstra(int n,int start){
    PriorityQueue<Node> Q = new PriorityQueue<>();
    visited = new boolean[n];
    dist = new int[n];

    Q.add(new Node(start, 0));
    while (!Q.isEmpty()) {
        Node node = Q.poll();
        int now = node.nodeNum;
        int w = node.weight;

        if (!visited[now]) {
            visited[now] = true;
            dist[now] = w;

            for (Node nx : graph.get(now)) {
                Q.add(new Node(nx.nodeNum, nx.weight));
            }
        }
    }

}

public int solution(int n, int[][] costs) {

    // 1
    graph = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        graph.add(new ArrayList<>());
    }
    for (int i = 0; i < costs.length; i++) {
        int u = costs[i][0];
        int v = costs[i][1];
        int w = costs[i][2];

        graph.get(u).add(new Node(v, w));
        graph.get(v).add(new Node(u, w));
    }

    // 2
    dikstra(n, 0);
    // System.out.println(Arrays.toString(dist));

    // 3
    int answer = 0;
    for (int i = 1; i < n; i++) {
        answer += dist[i];
    }

    return answer;
}

}