본문 바로가기

분류 전체보기

 (215)
백준 1926 그림 (Java) 1. 문제 링크 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 처음에는 우, 하만 확인하면 될거라고 생각했는데 역시 아니었고…. 아래의 반례에서 틀렸다. (dfs로 돌아가니까 사방으로 탐색하는게 맞지..) 4 5 1 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 1 dfs탐색을 사방으로 하면서 각 그림의 크기를 list에 추가했다. 전체를 돌고 나서는 list를 정렬하여 그림의 개수와 그림의 최대 크기를 출력했다. 4. 코드 import java.io.B..
백준 13164 행복 유치원 (Java) 1. 문제 링크 13164번: 행복 유치원 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 입력받을 때 앞선 키와의 차이를 PQ에 넣는다. 2. 차이를 오름차순으로 정렬해서 K개를 빼고 더한 값을 출력한다. 중복순열이나 누적합하면 무조건 시간초과라는 생각에 키 차이를 이용했다. 키 차이 순으로 세우고 K개를 빼고 더한다면 가장 큰 차이가 있는 부분을 제외하고 더해 누적합 느낌으로 한 조 안에서의 최대 키와 최소 키의 차이를 구할 수 있다. 4. 코드 import jav..
백준1245 농장 관리 (Java) 1. 문제 링크 1245번: 농장 관리 첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 BFS로 하니까 바로 틀렸습니다 뜨거나 2%에서 떠서 DFS로 갈아탔다. dfs로 진행하면서 8방 탐색을 하는데 더 높은 숫자가 나온다면 isPick을 false로 리턴한다. 끝까지 진행해서 true가 return되는 경우에 꼭대기의 수를 1만큼 늘린다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReade..
백준 1796 신기한 키보드 (Java) 1. 문제 링크 https://www.acmicpc.net/problem/1796 1796번: 신기한 키보드 동혁이의 키보드에는 버튼 세 개와 LCD창 한 개가 달려 있다. LCD창에는 문자열 S가 쓰여 있다. 그리고 커서는 문자열의 가장 왼쪽 글자에 위치해 있다. 버튼 세 개는 왼쪽, 오른쪽, 엔터키이다. 왼 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 문자별로 ArrayList를 만들어 해당 문자 별로 어떤 문자가 들어왔는지 추가했다. 처음 시작은 a이고, 위치는 0, 움직인 횟수는 0으로 dfs를 했다. 마지막 알파벳인 z까지 출력했다면 return 한다. 현재 알파벳의 개수가 0이라면 다음으로 넘어간다. 현재 알파벳이 있다면 첫번째 자리와 마지막 자리를 구한다. 5-1. ..
백준 2866 문자열 잘라내기 (Java) 1. 문제 링크 2866번: 문자열 잘라내기 첫 번째 줄에는 테이블의 행의 개수와 열의 개수인 R과 C가 주어진다. (2 ≤ R, C ≤ 1000) 이후 R줄에 걸쳐서 C개의 알파벳 소문자가 주어진다. 가장 처음에 주어지는 테이블에는 열을 읽어서 문자 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 입력받은 문자들을 세로로 돌면서 문자열을 만든다. 2. 문자열을 하나씩 자르면서 set에 넣는다. 3. set에 동일한 문자열이 들어있다면 끝 인데 메모리랑 시간이랑 너무 크게 나와서 이분 탐색으로 다시 풀어봤다. 중복이 없으면 더 뒤로 가야하니까 end을 mid +1로 바꾸고 중복이 있으면 앞으로 가야하니까 start를 mid -1로 바꿨다. (뒤에서부터 자르니까 start를 뒤로..
백준 17219 비밀번호 찾기 (Java) 1. 문제 링크 https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 Map을 이용해서 사이트 주소와 비밀번호를 저장한다. 찾으려는 사이트를 입력받아서 Map에 있는 비밀번호를 출력한다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import ja..
백준 20920 영단어 암기는 괴로워 (Java) 1. 문제 링크 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 단어가 들어오면 길이가 M이 넘는지 확인한다. 단어와 횟수를 Word로 해서 list에 넣었다. Word에서는 단어가 나타난 개수 우선으로 비교하고, 길이를 비교한다. list를 정렬하고 그 안의 단어를 출력한다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; ..
백준 11651 좌표 정렬하기2 (Java) 1. 문제 링크 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 각 좌표들을 Point 객체로 PQ에 넣는다. y좌표 기준으로 비교하고 x 좌표 기준으로 비교해 정렬한다. pq를 x좌표 y좌표 순으로 출력하면 끝이다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java...

티스토리툴바