개발하는 고라니

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을 동일하게 포함하고 있다..

4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net [문자열, Stack] 이 문제를 풀기 전 아스키 코드를 알면 좋다. 아스키 코드 표를 참고하면 '(' : 40 ')' : 41 '[' : 91 ']' : 93 위와 같다. 따라서 ')' - '(' = 1이고, ']' - '[' = 2이다. 이 규칙만 잘 활용하면 쉽게 풀 수 있다. 먼저 스택을 준비하는데, 동적의 크기를 갖는 컬렉션 또는 자료구조로 할 수 있지만, 배열로도 충분하기 때문에 배열로 스택을 구현해주었다. 그리고 타겟의 문자를 저장하는..

14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net [BFS] BFS를 이용해서 풀었다. 일반적인 BFS와 다른 점은, 보통 BFS는 현재 정점에서 탐색할 수 있는 모든 정점을 Queue에 넣지만, 이 문제는 현재 정점에서 한 개의 정점만 큐에 넣을 수 있다. 큐에 들어갈 원소는 y좌표, x좌표 그리고 방향이다. static class Point{ int y, x, dir; public Point(int yy, int xx, int d){ y=yy; x=xx; dir = d; } } 현재 방향에 따라 다음 방향이..