Lv. 1
1. 폰켓몬
HashSet 풀이
import java.util.HashSet;
class Solution {
public int solution(int[] nums) {
HashSet<Integer> hs = new HashSet<>();
for (int i=0; i<nums.length; i++){
hs.add(nums[i]);
}
int length = nums.length / 2;
int size = hs.size();
if (size >= length){
return length;
} else {
return size;
}
}
}HashMap 풀이
import java.util.HashMap;
class Solution {
public int solution(int[] nums) {
HashMap <Integer, Integer> hm = new HashMap<>();
for (int num : nums){
hm.put(num,1);
}
return hm.size() >= nums.length / 2 ? nums.length / 2 : hm.size();
}
}
2. 완주하지 못한 선수
import java.util.HashMap;
class Solution {
public String solution(String[] participant, String[] completion) {
HashMap<String, Integer> hm = new HashMap<>();
for (int i=0; i<participant.length; i++){
hm.put(participant[i], hm.getOrDefault(participant[i],0) + 1);
}
for(int i=0; i<completion.length; i++){
hm.put(completion[i], hm.get(completion[i]) - 1);
}
for (int i=0; i<participant.length; i++){
if (hm.get(participant[i]) != 0){
return participant[i];
}
}
return null;
}
}
3. 같은 숫자는 싫어
import java.util.*;
public class Solution {
public int[] solution(int []arr) {
Queue<Integer> queue = new LinkedList<>();
for (int i=0; i<arr.length; i++){
if (i==0){
queue.add(arr[i]);
} else {
if (arr[i] != arr[i-1]){
queue.add(arr[i]);
}
}
}
ArrayList<Integer> answer = new ArrayList<>();
while (!queue.isEmpty()){
answer.add(queue.poll());
}
return answer.stream().mapToInt(i->i).toArray();
}
}
4. K번째 수
import java.util .*;
class Solution {
public int[] solution(int[] array, int[][] commands) {
int[] answer = new int[commands.length];
for (int t = 0; t < commands.length; t++) {
int length = commands[t][1] - commands[t][0] + 1;
int[] arr = new int[length];
int k = 0;
for (int i = commands[t][0] - 1; i <= commands[t][1] - 1; i++) {
arr[k++] = array[i];
}
Arrays.sort(arr);
answer[t] = arr[commands[t][2] - 1];
}
return answer;
}
}
5. 최소 직사각형
class Solution {
public int solution(int[][] sizes) {
for (int i = 0; i < sizes.length; i++) {
if (sizes[i][0] < sizes[i][1]) {
int temp = sizes[i][1];
sizes[i][1] = sizes[i][0];
sizes[i][0] = temp;
}
}
int x = 0;
int y = 0;
for (int i = 0; i < sizes.length; i++) {
if (x < sizes[i][0]) {
x = sizes[i][0];
}
if (y < sizes[i][1]) {
y = sizes[i][1];
}
}
int result = x * y;
return result;
}
}
6. 모의고사
import java.util.*;
class Solution {
public int[] solution(int[] answers) {
int count1 = 0;
int k1 = 1;
for (int i = 0; i < answers.length; i++) {
if (k1 == answers[i]) {
count1++;
}
k1++;
if (k1 == 6) {
k1 = 1;
}
}
int count2 = 0;
int k2 = 1;
for (int i = 0; i < answers.length; i++) {
if (i % 2 == 0) {
if (answers[i] == 2) {
count2++;
}
} else {
if (answers[i] == k2) {
count2++;
}
if (k2 == 1) {
k2 = 3;
} else if (k2 == 5) {
k2 = 1;
} else {
k2++;
}
}
}
int count3 = 0;
int k3 = 3;
for (int i = 0; i < answers.length; i++) {
if (k3 == answers[i]) {
count3++;
}
if (i % 2 == 1) {
if (k3 == 3) {
k3 = 1;
} else if (k3 == 2) {
k3 = 4;
} else if (k3 == 5) {
k3 = 3;
} else {
k3++;
}
}
}
int[] arr = new int[3];
arr[0] = count1;
arr[1] = count2;
arr[2] = count3;
ArrayList<Integer> al = new ArrayList<>();
int max = 0;
for (int i = 0; i < 3; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
for (int i = 0; i < 3; i++) {
if (max == arr[i]) {
al.add(i + 1);
}
}
return al.stream().mapToInt(i -> i).toArray();
}
}
7. 체육복
import java.util.*;
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
boolean[] bl = new boolean[n + 1];
int count = 0;
Arrays.sort(lost);
Arrays.sort(reserve);
for (int i = 0; i < reserve.length; i++) {
bl[reserve[i]] = true;
}
for (int i = 0; i < lost.length; i++) {
if (bl[lost[i]]) {
count++;
bl[lost[i]] = false;
lost[i] = -1;
}
}
for (int i = 0; i < lost.length; i++) {
if (lost[i] == -1) {
continue;
} else if (lost[i] == n) {
if (bl[lost[i] - 1]) {
count++;
bl[lost[i] - 1] = false;
}
} else {
if (bl[lost[i] - 1]) {
count++;
bl[lost[i] - 1] = false;
} else if (bl[lost[i] + 1]) {
count++;
bl[lost[i] + 1] = false;
}
}
}
int answer = n - lost.length + count;
return answer;
}
}
8. 달리기 경주
import java.util.*;
import java.util.Map.Entry;
public class 달리기경주 {
public String[] solution(String[] players, String[] callings) {
HashMap<String, Integer> map = new HashMap<>();
for (int i = 0; i < players.length; i++) {
map.put(players[i], i);
}
for (String player : callings) {
int nowRank = map.get(player);
String frontPlayer = players[nowRank - 1];
map.replace(frontPlayer, nowRank);
players[nowRank] = frontPlayer;
map.replace(player, nowRank - 1);
players[nowRank - 1] = player;
}
return players;
}
}
9. 숫자 문자열과 영단어
import java.util.HashMap;
import java.util.Map;
public class 숫자문자열과영단어 {
public int solution(String s) {
Map<String, Integer> map = new HashMap<>();
map.put("zero", 0);
map.put("one", 1);
map.put("two", 2);
map.put("three", 3);
map.put("four", 4);
map.put("five", 5);
map.put("six", 6);
map.put("seven", 7);
map.put("eight", 8);
map.put("nine", 9);
String str = "";
String answer = "";
for (int i = 0; i < s.length(); i++) {
char sa = s.charAt(i);
if (sa >= '0' && sa <= '9') {
answer += sa;
} else {
str += sa;
if (map.containsKey(str)) {
answer += String.valueOf(map.get(str));
str = "";
}
}
}
return Integer.valueOf(answer);
}
}
Lv. 2
1. 전화번호 목록
배열 풀이
import java.util.Arrays;
import java.util.Comparator;
class Solution {
public boolean solution(String[] phone_book) {
Arrays.sort(phone_book);
for (int i=0; i<phone_book.length -1; i++){
if(phone_book[i+1].startsWith(phone_book[i])){
return false;
}
}
return true;
}
}HashMap 풀이
import java.util.HashMap;
class Solution {
public boolean solution(String[] phone_book) {
HashMap<String, Integer> hm = new HashMap<>();
for (int i=0; i<phone_book.length; i++){
hm.put(phone_book[i], i);
}
for (int i=0; i<phone_book.length; i++){
for (int j=0; j<phone_book[i].length(); j++){
if (hm.containsKey(phone_book[i].substring(0,j))){
return false;
}
}
}
return true;
}
}
2. 의상
import java.util.HashMap;
class Solution {
public int solution(String[][] clothes) {
HashMap<String, Integer> hm = new HashMap<>();
for (int i=0; i<clothes.length; i++){
hm.put(clothes[i][1], hm.getOrDefault(clothes[i][1], 0) + 1);
}
int result = 1;
for (String str : hm.keySet()){
result *= hm.get(str) + 1;
}
result -= 1;
return result;
}
}
3. 기능개발
import java.util.*;
class Solution {
public int[] solution(int[] progresses, int[] speeds) {
ArrayList<Integer> answer = new ArrayList<>();
int index = 0;
while (index < progresses.length) {
for (int i=0; i<progresses.length; i++){
progresses[i] += speeds[i];
}
if (progresses[index] >= 100){
int count = 1;
for (int i = index+1; i<progresses.length; i++){
if (progresses[i] < 100){
break;
}
count++;
}
index += count;
answer.add(count);
}
}
return answer.stream().mapToInt(i->i).toArray();
}
}
4. 올바른 괄호
class Solution {
boolean solution(String s) {
char[] arr = s.toCharArray();
int f=0;
int e=0;
for (int i=0; i<arr.length; i++){
if (arr[i] == '('){
f++;
} else {
e++;
}
if (e > f){
return false;
}
}
if (f == e){
return true;
} else {
return false;
}
}
}
5. 프로세스
import java.util.*;
class Solution {
public int solution(int[] priorities, int location) {
int answer = 0;
PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
for (int i : priorities){
queue.add(i);
}
while(!queue.isEmpty()){
for (int i=0; i<priorities.length; i++){
if (queue.peek() == priorities[i]){
queue.poll();
answer++;
if (i == location){
return answer;
}
}
}
}
return answer;
}
}
6. 다리를 지나는 트럭
import java.util.*;
class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
Queue<Integer> queue = new LinkedList<>();
int sumWeight = 0;
int time = 0;
for (int i = 0; i < truck_weights.length; i++) {
int truck = truck_weights[i];
while (true) {
if (queue.isEmpty()) {
queue.add(truck);
sumWeight += truck;
time++;
break;
} else if (queue.size() == bridge_length) {
sumWeight -= queue.poll();
} else {
if (sumWeight + truck <= weight) {
queue.add(truck);
sumWeight += truck;
time++;
break;
} else {
queue.add(0);
time++;
}
}
}
}
return time + bridge_length;
}
}
7. 주식가격
import java.util.Stack;
class Solution {
public int[] solution(int[] prices) {
Stack<Integer> stack = new Stack<>();
int[] answer = new int[prices.length];
for (int i=0; i<prices.length; i++){
while(true) {
if (stack.isEmpty()){
stack.push(i);
break;
} else {
if (prices[stack.peek()] <= prices[i]){
stack.push(i);
break;
} else {
int time = stack.pop();
answer[time] = i - time;
}
}
}
}
while (!stack.isEmpty()){
int time = stack.pop();
answer[time] = prices.length - 1 - time;
}
return answer;
}
}
8. 더 맵게
import java.util.*;
class Solution {
public int solution(int[] scoville, int K) {
PriorityQueue<Integer> queue = new PriorityQueue<>();
for (int i = 0; i < scoville.length; i++) {
queue.add(scoville[i]);
}
int count = 0;
while (queue.peek() < K) {
if (queue.size() < 2){
return -1;
}
count++;
int a = queue.poll();
int b = queue.poll();
if (a == 0 && b == 0) {
return -1;
}
int c = a + b*2;
queue.add(c);
}
return count;
}
}
9. 가장 큰 수
import java.util.*;
class Solution {
public String solution(int[] numbers) {
String[] arr = new String[numbers.length];
for (int i = 0; i < numbers.length; i++) {
arr[i] = String.valueOf(numbers[i]);
}
Arrays.sort(arr, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));
if (arr[0].equals("0")) {
return "0";
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < arr.length; i++) {
sb.append(arr[i]);
}
String answer = sb.toString();
return answer;
}
}
10. 소수 찾기
import java.util.*;
public int solution(String numbers) {
set = new HashSet<>();
dfs(numbers, "", 0);
int count = 0;
for (int num : set) {
if (isPrime(num)) {
count++;
}
}
return count;
}
public static void dfs(String numbers, String s, int depth) {
if (depth >= numbers.length()) {
return;
}
for (int i = 0; i < numbers.length(); i++) {
if (!visit[i]) {
visit[i] = true;
set.add(Integer.parseInt(s + numbers.charAt(i)));
dfs(numbers, s + numbers.charAt(i), depth + 1);
visit[i] = false;
}
}
}
public static boolean isPrime(int n) {
if (n < 2) {
return false;
}
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
11. 카펫
class Solution {
public int[] solution(int brown, int yellow) {
int x = 0;
int y = 0;
for (int i = 1; i <= Math.sqrt(yellow); i++) {
if (yellow % i == 0) {
int a = i;
int b = yellow / i;
int len = 2 * a + 2 * b + 4;
if (len == brown) {
x = a + 2;
y = b + 2;
break;
}
}
}
if (y > x) {
int temp = y;
y = x;
x = temp;
}
int[] answer = new int[2];
answer[0] = x;
answer[1] = y;
return answer;
}
}
12. 피로도
class Solution {
static boolean[] visited;
static int count = 0;
public int solution(int k, int[][] dungeons) {
visited = new boolean[dungeons.length];
dfs(dungeons, k, 0);
return count;
}
public static void dfs(int[][] dungeons, int k, int depth) {
for (int i = 0; i < dungeons.length; i++) {
if (!visited[i] && k >= dungeons[i][0]) {
visited[i] = true;
dfs(dungeons, k - dungeons[i][1], depth + 1);
visited[i] = false;
}
count = Math.max(count, depth);
}
}
}
13. 전력망을 둘로 나누니
import java.util.*;
class Solution {
static boolean[] visited;
static ArrayList<Integer>[] al;
class Solution {
static boolean[] visited;
static ArrayList<Integer>[] al;
public int solution(int n, int[][] wires) {
int min = Integer.MAX_VALUE;
visited = new boolean[n + 1];
al = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
al[i] = new ArrayList<>();
}
for (int i = 0; i < wires.length; i++) {
int a = wires[i][0];
int b = wires[i][1];
al[a].add(b);
al[b].add(a);
}
for (int i = 0; i < wires.length; i++) {
int a = wires[i][0];
int b = wires[i][1];
al[a].remove(Integer.valueOf(b));
al[b].remove(Integer.valueOf(a));
int count = dfs(1);
int count2 = n - count;
int gap = Math.abs(count - count2);
min = Math.min(min, gap);
al[a].add(b);
al[b].add(a);
}
return min;
}
public int dfs(int v) {
visited[v] = true;
int count = 1;
for (int num : al[v]) {
if (!visited[num]) {
count += dfs(num);
}
}
visited[v] = false;
return count;
}
}
}
14. 모음사전
import java.util.*;
class Solution {
static ArrayList<String> al = new ArrayList<>();
public int solution(String word) {
String[] dic = {"A", "E", "I", "O", "U"};
dfs(dic, "", 0);
int answer = al.indexOf(word) + 1;
return answer;
}
public static void dfs(String[] word, String s, int depth) {
if (depth >= word.length) {
return;
}
for (int i = 0; i < word.length; i++) {
al.add(s + word[i]);
dfs(word, s + word[i], depth + 1);
}
}
}
15. 큰 수 만들기
import java.util.*;
class Solution {
public String solution(String number, int k) {
char[] result = new char[number.length() - k];
Stack<Character> stack = new Stack<>();
for (int i=0; i<number.length(); i++) {
char c = number.charAt(i);
while (!stack.isEmpty() && stack.peek() < c && k-- >0 ) {
stack.pop();
}
stack.push(c);
}
for (int i=0; i<result.length; i++) {
result[i] = stack.get(i);
}
return new String(result);
}
}
16. 구명보트
import java.util.*;
class Solution {
public int solution(int[] people, int limit) {
Arrays.sort(people);
int answer = 0;
int index = 0;
for (int i = people.length - 1; i >= index; i--) {
if (people[i] + people[index] <= limit) {
index++;
answer++;
} else {
answer++;
}
}
return answer;
}
}
17. 타겟 넘버
class Solution {
static boolean[] visited;
static int answer = 0;
public int solution(int[] numbers, int target) {
visited = new boolean[numbers.length];
dfs(numbers, 0, target, 0);
return answer;
}
public static void dfs(int[] numbers, int sum, int target, int depth) {
if (depth >= numbers.length) {
if (sum == target) {
answer++;
}
return;
}
dfs(numbers, sum + numbers[depth], target, depth + 1);
dfs(numbers, sum - numbers[depth], target, depth + 1);
}
}
18. 게임 맵 최단거리
import java.util.*;
class Solution {
static int[] dx = {0, 1, 0, -1};
static int[] dy = {1, 0, -1, 0};
static boolean[][] visited;
public int solution(int[][] maps) {
visited = new boolean[maps.length][maps[0].length];
bfs(maps, 0, 0);
int answer = maps[maps.length - 1][maps[0].length - 1];
if (answer == 0 || answer == 1) {
return -1;
} else {
return answer;
}
}
public void bfs(int[][] maps, int t, int k) {
visited[t][k] = true;
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{t, k});
while (!queue.isEmpty()) {
int[] arr = queue.poll();
int a = arr[0];
int b = arr[1];
for (int i = 0; i < 4; i++) {
int x = a + dx[i];
int y = b + dy[i];
if (x >= 0 && y >= 0 && x < maps.length && y < maps[0].length) {
if (!visited[x][y] && maps[x][y] == 1) {
maps[x][y] += maps[a][b];
queue.add(new int[]{x, y});
}
}
}
}
}
}
19. 요격 시스템
import java.util.*;
public class 요격시스템 {
public int solution(int[][] targets) {
Arrays.sort(targets, new Comparator<int[]>() {
public int compare(int[] o1, int[] o2) {
if (o1[1] == o2[1]) {
return o1[0] - o2[0];
} else {
return o1[1] - o2[1];
}
}
});
int answer = 0;
int num = 0;
for (int i = 0; i < targets.length; i++) {
if (num <= targets[i][0]) {
answer++;
num = targets[i][1];
}
}
return answer;
}
}
Lv. 3
1. 베스트앨범
import java.util.*;
class Solution {
public int[] solution(String[] genres, int[] plays) {
ArrayList<Integer> answer = new ArrayList<>();
HashMap<String, Integer> num = new HashMap<>();
HashMap<String, HashMap<Integer, Integer>> music = new HashMap<>();
for (int i=0; i<plays.length; i++){
if (!num.containsKey(genres[i])){
HashMap<Integer, Integer> map = new HashMap<>();
map.put(i, plays[i]);
music.put(genres[i], map);
num.put(genres[i], plays[i]);
} else {
num.put(genres[i], num.get(genres[i]) + plays[i]);
music.get(genres[i]).put(i, plays[i]);
}
}
ArrayList<String> numKey = new ArrayList(num.keySet());
Collections.sort(numKey, (s1,s2) -> num.get(s2) - num.get(s1));
for (String key : numKey){
HashMap<Integer, Integer> map = music.get(key);
ArrayList<Integer> al = new ArrayList(map.keySet());
Collections.sort(al, (s1, s2) -> map.get(s2) - map.get(s1));
answer.add(al.get(0));
if (al.size() > 1){
answer.add(al.get(1));
}
}
return answer.stream().mapToInt(i -> i).toArray();
}
}
2. 디스크 컨트롤러
import java.util.*;
class Solution {
public int solution(int[][] jobs) {
Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]);
PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
int count = 0;
int nowTime = 0;
int answer = 0;
int index = 0;
while(count < jobs.length){
while(index < jobs.length && jobs[index][0] <= nowTime){
queue.add(jobs[index++]);
}
if (queue.isEmpty()) {
nowTime = jobs[index][0];
} else {
int[] time = queue.poll();
answer += time[1] + nowTime - time[0];
nowTime += time[1];
count++;
}
}
answer /= jobs.length;
return answer;
}
}
3. 이중우선순위큐
import java.util.*;
class Solution {
public int[] solution(String[] operations) {
StringTokenizer st;
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
for (int i = 0; i < operations.length; i++) {
st = new StringTokenizer(operations[i]);
String str = st.nextToken();
int num = Integer.parseInt(st.nextToken());
if (str.equals("I")) {
queue.add(num);
} else if (str.equals("D") && num == 1) {
if (queue.size() == 0) {
continue;
}
queue.poll();
} else {
if (queue.size() == 0) {
continue;
}
ArrayList<Integer> al = new ArrayList<>();
while (!queue.isEmpty()) {
al.add(queue.poll());
}
al.remove(al.size() - 1);
for (int j = 0; j < al.size(); j++) {
queue.add(al.get(j));
}
}
}
ArrayList<Integer> al = new ArrayList<>();
while (!queue.isEmpty()) {
al.add(queue.poll());
}
int[] answer = new int[2];
if (al.size() == 0) {
answer[0] = 0;
answer[1] = 0;
} else if (al.size() == 1) {
answer[0] = al.get(0);
answer[1] = 0;
} else {
answer[0] = al.get(0);
answer[1] = al.get(al.size() - 1);
}
return answer;
}
}
4. 정수 삼각형
class Solution {
public int solution(int[][] triangle) {
int[][] dp = new int[triangle.length][triangle.length];
dp[0][0] = triangle[0][0];
for (int i = 1; i < triangle.length; i++) {
dp[i][0] = dp[i - 1][0] + triangle[i][0];
dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
for (int j = 1; j < i; j++) {
dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
}
}
int answer = 0;
for (int i = 0; i < triangle.length; i++) {
answer = Math.max(answer, dp[triangle.length - 1][i]);
}
return answer;
}
}
5. 네트워크
import java.util.*;
class Solution {
static ArrayList<Integer>[] al;
static boolean[] visited;
public int solution(int n, int[][] computers) {
visited = new boolean[n];
al = new ArrayList[n];
for (int i=0; i<n; i++) {
al[i] = new ArrayList<>();
}
for (int i = 0; i < computers.length; i++) {
for (int j = 0; j < computers[i].length; j++) {
if (i == j) {
continue;
}
if (computers[i][j] == 1){
al[i].add(j);
}
}
}
int answer = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
answer++;
dfs(i);
}
}
return answer;
}
public static void dfs(int i) {
visited[i] = true;
for (int num : al[i]) {
if (!visited[num]) {
dfs(num);
}
}
}
}
6. 단어 변환
class Solution {
static boolean[] visited;
static int answer = 0;
public int solution(String begin, String target, String[] words) {
visited = new boolean[words.length];
dfs(begin, target, words, 0);
return answer;
}
public void dfs(String begin, String target, String[] words, int cnt) {
if (begin.equals(target)) {
answer = cnt;
return;
}
for (int i = 0; i < words.length; i++) {
int k = 0;
if (!visited[i]) {
for (int j = 0; j < begin.length(); j++) {
if (begin.charAt(j) == words[i].charAt(j)) {
k++;
}
}
}
if (k == words[i].length() - 1) {
visited[i] = true;
dfs(words[i], target, words, cnt + 1);
visited[i] = false;
}
}
}
}
7. 여행 경로
import java.util.*;
class Solution {
static String[] answer;
static boolean[] visited;
static int answer_index = 0;
public String[] solution(String[][] tickets) {
answer = new String[tickets.length + 1];
visited = new boolean[tickets.length];
answer = new String[tickets.length + 1];
visited = new boolean[tickets.length];
Arrays.sort(tickets, new Comparator<String[]>() {
public int compare(String[] o1, String[] o2) {
if (o1[0].equals(o2[0])) {
return o1[1].compareTo(o2[1]);
}
return o1[0].compareTo(o2[0]);
}
});
for (int i = 0; i < tickets.length; i++) {
if (tickets[i][0].equals("ICN")) {
boolean bl = true;
bfs(tickets, tickets[i][0], tickets[i][1], i);
for (int j = 0; j < answer.length; j++) {
if (answer[j] == null || answer[j] == "") {
Arrays.fill(answer, "");
Arrays.fill(visited, false);
bl = false;
answer_index = 0;
break;
}
}
if (bl) {
break;
}
}
}
return answer;
}
public static void bfs(String[][] tickets, String start, String end, int index) {
visited[index] = true;
Queue<String> queue = new LinkedList<>();
queue.add(start);
queue.add(end);
int count = 0;
while (!queue.isEmpty()) {
count++;
String s = queue.poll();
String e = queue.poll();
answer[answer_index++] = s;
if (count == tickets.length) {
answer[answer_index] = e;
break;
}
for (int i = 0; i < tickets.length; i++) {
if (!visited[i] && e.equals(tickets[i][0])) {
visited[i] = true;
queue.add(tickets[i][0]);
queue.add(tickets[i][1]);
break;
}
}
}
}
}
8. 가장 먼 노드
import java.util.*;
class Solution {
static boolean[] visited;
static ArrayList<Integer>[] al;
static int depth = 0;
static int maxDepth = 0;
public int solution(int n, int[][] edge) {
visited = new boolean[n + 1];
al = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
al[i] = new ArrayList<>();
}
for (int i = 0; i < edge.length; i++) {
int a = edge[i][0];
int b = edge[i][1];
al[a].add(b);
al[b].add(a);
}
bfs(1, 1);
return depth;
}
public static void bfs(int a, int cnt) {
visited[a] = true;
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{a, cnt});
while (!queue.isEmpty()) {
int[] num = queue.poll();
if (maxDepth < num[1]) {
maxDepth = num[1];
depth = 1;
} else if (maxDepth == num[1]) {
depth++;
}
for (int i : al[num[0]]) {
if (!visited[i]) {
visited[i] = true;
queue.add(new int[]{i, num[1] + 1});
}
}
}
}
}
9. 섬 연결하기
import java.util.*;
class Solution {
static int[] index;
static int sum = 0;
class Node implements Comparable<Node> {
int start;
int end;
int weight;
Node(int start, int end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
public int compareTo(Node o) {
return this.weight - o.weight;
}
}
public int solution(int n, int[][] costs) {
index = new int[n];
for (int i = 0; i < n; i++) {
index[i] = i;
}
PriorityQueue<Node> queue = new PriorityQueue<>();
for (int i = 0; i < costs.length; i++) {
int a = costs[i][0];
int b = costs[i][1];
int c = costs[i][2];
queue.add(new Node(a,b,c));
}
while (!queue.isEmpty()) {
Node o = queue.poll();
union(o.start, o.end, o.weight);
}
return sum;
}
public static void union(int a, int b, int c) {
a = find(a);
b = find(b);
if (a!=b){
index[b] = a;
sum += c;
}
}
public static int find(int a){
if (index[a] == a) {
return a;
} else {
return index[a] = find(index[a]);
}
}
}
10. 단속 카메라
import java.util.*;
class Solution {
public int solution(int[][] routes) {
Arrays.sort(routes, new Comparator<int[]>() {
public int compare(int[] o1, int[] o2) {
if (o1[1] == o2[1]) {
return o1[0] - o2[0];
} else {
return o1[1] - o2[1];
}
}
});
int answer = 0;
int now = -40000;
for (int i = 0; i < routes.length; i++) {
if (now < routes[i][0]) {
now = routes[i][1];
answer++;
}
}
return answer;
}
}
11. 입국심사
import java.util.*;
class Solution {
public long solution(int n, int[] times) {
long answer = 0;
Arrays.sort(times);
long left = 0;
long right = times[times.length - 1] * (long) n;
while (left <= right) {
long mid = (left + right) / 2;
long complete = 0;
for (int i = 0; i < times.length; i++) {
complete += mid / times[i];
}
if (complete < n) {
left = mid + 1;
} else {
right = mid - 1;
answer = mid;
}
}
return answer;
}
}
12. 순위
class Solution {
public int solution(int n, int[][] results) {
int answer = 0;
int[][] graph = new int[n + 1][n + 1];
for (int i = 0; i < results.length; i++) {
graph[results[i][0]][results[i][1]] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int z = 1; z <= n; z++) {
if (graph[j][i] == 1 && graph[i][z] == 1) {
graph[j][z] = 1;
}
}
}
}
for (int i = 1; i <= n; i++) {
int game = 0;
for (int j = 1; j <= n; j++) {
if (graph[i][j] == 1 || graph[j][i] == 1) {
game++;
}
}
if (game == n - 1) {
answer++;
}
}
return answer;
}
}
블로그 이전했습니다 -> https://young-code.tistory.com