개발하는 고라니

코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr [Dijkstra] 1번 정점에서 모든 정점까지의 최단 거리를 구해 dist[ ]에 저장 후, 1번 정점부터 n번 정점까지 dist[i]를 돌면서 dist[i]가 max인 곳의 정점 개수를 카운팅 한다. # Code import java.util.ArrayList; import java.util.List; import java.util.PriorityQueue; import java.util.Queue; class Solution { static class Edge{ int tg, d; public Edge(int target, i..

14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1

12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net [문자열 + BFS] 이 문제는 정공법으로 풀면 안된다. s -> t를 가는게 아닌, t -> s를 가는 것을 생각해야 한다. 전자로 풀면 메모리 초과가 날 수 있다. 따라서 t -> s로 가는 방법으로 풀어보자. 1. 문자열의 끝이 'A'이면 맨 끝 문자 삭제 2. 문자열의 끝이 'B'이면 맨 끝 문자 삭제 후 뒤집기 나는 Set을 이용해 방문을 표시했엇으나, 굳이 필요하지 않음을 느꼈다. 따라서 반복문의 종료 조건은 문자열..

4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net [문자열 + Map] 우선 문제의 입력은 마지막이 특별한 조건이 없으므로 입력받은 값이 Null 또는 공백일 때 입력을 종료한다. 나는 BufferedReader를 썻지만, Scanner를 사용한다면 hasNextLine()을 사용할 수 있을지도 모르겠다. Map을 이용해서 나무 이름으로 Key를, 그 나무 이름이 나오는 횟수를 Value로 설정하고 값을 계속 업데이트하자. 그러면 해당 나무가 몇 번 이름 불렸는지 알게되는데, 문제에서는 이름 순으로 ..

14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net [최소 스패닝 트리(Minimum Spanning Tree, MST), 크루스칼] 남초와 여초만을 이어주는 경로만 존재한다고 생각하면 쉽다. 문제에서 2번째 줄에 M W W W M 이런 식으로 주어지는데, 이를 boolean[ ]에 저장을 한다. 예를 들어 1번 째 학교가 M(남초) 이면 true, 2번 째 학교가 W(여초)이면 false 이런 식으로. 그럼 간선 정보가 주어질 때 선별적으로 간선을 저장할 수 있다. for..

1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net [DFS + 백트래킹 + 비트마스킹] DFS를 이용해 백트래킹을 구현했고, 알파벳 'a' ~ 'z'까지 어떤 알파벳을 알고 있는지에 대한 정보를 비트마스킹으로 표현했다. 즉, 'a', 'b'를 알고있다면 0b00 0000 0000 0000 0000 0000 0011로 나타낼 수 있다. 그런데 남극의 단어는 "anta"로 시작해서 "tica"로 끝난다고 했으니, 'a', 'c', 'n', 't', 'i'는 반드시 알고있어야 한다. 그래서 check를 다음과..

6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 DFS 탐색 -> 방문 취소 가 이뤄져야 한다. # Code import java.io.BufferedReader; import java.io.IOException; i..

9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net [문자열 / Stack(Array)] # 풀이 요약 1. 문자열(origin)을 받아 char[ ] arr로 변환한다. 2. 폭발 문자열을 받아 char[ ] bomb으로 변환한다. 3. char[ ] stack을 준비한다. 이때 top = -1 4. arr의 한 문자씩 stack에 넣는다. 5. 만약 stack에 넣은게 bomb의 마지막 문자라면 bomb의 크기만큼 stack의 뒤로 가며 문자 비교 6 비교 결과 bomb을 동일하게 포함하고 있다..