BaekJoon 9470. Strahler (Java) (골드3) (위상정렬, bfs, 인접리스트)

문제출처: https://www.acmicpc.net/problem/9470 9470번: Strahler 순서 지질학에서 하천계는 유향그래프로 나타낼 수 있다. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳 www.acmicpc.net 문제 이해 목표 하천계의 정보가 주어졌을 때 Strahler 순서를 구하는 프로그램 작성 단계 1. 일단 루트 노드를 찾는다. 루트 노드의 순서는 1이다. 2. 인접리스트(adjList)를 만든다 ex) 1 2 3 4 5 6 7 3 3 4 7 7 4 5 7 3. 해당 노드에 들어온 순서를 관리하는 orders 인접리스트를 만든다. (max와 maxCount를 알 수 있도록) ex) ..

숫자 게임 (Programmers / Summer,Winter Coding) (java)

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/12987 코딩테스트 연습 - 숫자 게임 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 programmers.co.kr 문제 알고리즘 고안 For. 낭비를 최소화 [남아 있는 B의 가장 큰 값]에 [남아 있는 A의 값중 B가 이길 수 있는 가장 큰 값]을 할당 시켜주는 게 중요하다. 풀이 방법 1. 정렬 2. 가장 마지막 값 부터 비교 시작 -> while 모든 탐색을 위해 indexA >= 0 && indexB >= 0 이면 반복 (indexA--, ..

순위 (프로그래머스-그래프)(java)

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 문제 설명 int n: n명의 선수 존재 int[][] results: [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 같은 값이 들어 있고, [4,3]은 4선수가 3선수를 이겼다는 의미. 경기 결과엔 모순이 없고 -> 순위가 확정된 선수의 수를 계산하라 ! 문제풀이 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 의 예제에서 4, 3, 1 선수가 2를 이겼고, 2가 5를 이겼으므로 4,3,1이 5를 이겼다..

무지의 먹방 라이브(KAKAO BLIND RECRUITMENT) (java)

출처: https://programmers.co.kr/learn/courses/30/lessons/42891 코딩테스트 연습 - 무지의 먹방 라이브 programmers.co.kr int[] food_times -> 해당 인덱스의 음식이 몇 초 동안 더 먹을 수 있는지 나타냄 int k -> k초 이후 몇 번째 음식을 먹고 있는지 알려 줌 예를들면) k = 11 food_times 배열 1 2 3 4 5 3 1 2 3 5 같이 주어졌을 때 답은 5 이다. 실패한 나의 풀이 package programmers; import java.util.LinkedList; public class 무지의먹방라이브 { long next_food_time; class Food { int index; int food_tim..

JUNGOL 1169 : 주사위 던지기1 (Java)(조합)(순열)

문제출처: jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=449&sca=2080 소스코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader; public class 주사위던지기1_1..

JUNGOL 1141 : 불쾌한 날(Bad Hair Day) (Java)(Stack)

문제출처: jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=421&sca=3020 풀이과정 - Stack - 현재 데이터를 받은 소의 키를 nowHeight변수로 받고 바로 이전 순서의 소들의 키와 비교했을 때, nowHeight가 크거나 같으면 해당 순서의 소들은 이후로 안보일테니 pop으로 스택에서 제거해버린다. - 여기서 순서는 Stack의 후입선출법이므로 바로 이전 소부터 시작해서 한마리씩 이전으로 들어가 검사한다. 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; public class 불쾌한..

BaekJoon 18405. 경쟁적 전염(Java)(BFS)(실버1)

문제출처: www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 풀이 과정 - disease객체는 필드를 4개 가진다. 바이러스의 종류(virus), 좌표(row, col), 시간초(s). 여기서 s는 bfs를 진행하면서 해당 바이러스가 몇초 지나고 퍼진 바이러스인지 알려줌. - 바이러스가 있는 곳을 미리 찾아놓고 Queue에 저장. - 큐를 virus종류를 기준으로 정렬 - 큐에서 바이러스를 하나씩 꺼내면서 BFS시작. - BFS과..

JUNGOL 1459 : 숫자고르기(Java) (dfs)

문제 출처: jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=731&sca=2080 문제 조건 예) 크기가 7인 배열이 1 2 3 4 5 6 7 3 1 1 5 5 4 6 으로 값이 들어있다면, 인덱스 집합과 값 집합이 가장 크게 일치하려면 1, 3, 5를 뽑으면 된다. 가장 큰 크기는 3이다. 1 2 3 4 5 6 7 3 1 5 5 6 5 6 인 경우에는 1, 3, 5, 6이 되겠다. 크기는 4이다. 풀이 방법 - 배열의 인덱스와 값을 node로 생각하여 연결고리가 있는 그래프인지 확인하면된다. - 확인을 위해서는 dfs를 통해 노드를 계속 타고 들어가서 결국 처음시작한 노드와 끝나는 노드가 일치하는지 확인하면 된다. - set은 이미 완성된 그래프의 노드(요소)인지..