본문 바로가기

BOJ749

백준 11609 자바 - Class Time (BOJ 11609 JAVA) 문제 : boj11609 order by last asc, first asc의 형태로 정렬하면 된다. 문자열을 입력 받아 띄어쓰기를 기준으로 나눌 줄 알고, 정렬하는 방법을 안다면 쉽게 풀 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; class Name implements Comparable { String first, last; public Name(String name) { StringTokenizer st = new StringTokenizer(name); first = st.nextToken.. 2022. 1. 29.
백준 15922 자바 - 아우으 우아으이야!! (BOJ 15922 JAVA) 문제 : boj15922 결국 겹치는 구간은 무시하고, 모두 그려봤을 때 실제 포함되는 구간만을 구하면 된다. 이에 따라 예제 입력 1은 다음과 같이 생각해볼 수 있다. 그렇다고 배열같은거에 기입하자니 20억개나 표현이 가능해야하고, 당연히 이건 단순 순회만으로도 시간초과가 나게 된다. 따라서 내 경우엔 우선 각 x값을 기준으로 정렬한 후 현재 측정중인 구간의 시작 x와 끝점 y를 따로 기록해뒀다(코드에서 s와 e). 로직은 다음과 같다. A. x값을 기준으로 오름차순으로 정렬된 데이터를 차례대로 확인한다. 첫 s와 e는 즉 가장 x가 낮은 데이터 중 하나의 값과 동일해진다. B. 이후 각 (x,y)를 순회하면서 x가 e 이하라면 이전까지 보고 있던 (x,y)와 같은 구간으로 칠 수 있으므로 e만 조정한.. 2022. 1. 28.
백준 1817 자바 - 짐 챙기는 숌 (BOJ 1817 JAVA) 문제 : boj1817 '책은 탑처럼 차곡차곡 쌓여있기 때문에, 차례대로 박스에 넣을 수밖에 없다.' 부분이 없었다면 좀 더 어려웠을텐데, 이 문제의 경우 차례대로 넣을 수 밖에 없으므로 매번 최선의 선택만 진행하면 된다. (그리디 알고리즘) 입력을 받으면서 M의 무게를 다 채울 때 까지 계속 진행하고, M이상이 되었다면 무게를 다시 리셋하고 박스의 개수를 올리는 방식을 모든 입력값에 대해 취하면 해결할 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private void solution() throws Ex.. 2022. 1. 27.
백준 2239 자바 - 스도쿠 (BOJ 2239 JAVA) 문제 : boj2239 row기준 9개, 세로기준 9개, 3x3으로 나뉜 9개에 모두 1~9가 하나씩 들어가기만 하면 된다. 따라서 로직은 다음과 같다. 1. 입력에서 0이 아닌 칸에 대해 위 3개의 조건을 체크한다. 2. 0인 칸 모두에 대해 차례대로 1~9중 들어갈 수 있는 숫자를 무작정 넣어본다. 3. 그렇게 해서 0인칸 모두를 채울 수 있는 경우가 나온다면 그대로 출력하면 된다. 그렇지 않다면 바로 직전 단계로 돌아가서 다른 수를 넣어본다.(따라서 백트래킹 문제이다.) 다음 스도쿠 이미지를 보자. 저 빨간부분에는 우선 row를 기준으로 보면(초록색 선) 아직 체크안된 값은 1과 4이다. 그리고 col기준(파란선)으로 보면 역시 1과 4가 들어갈 수 있다. 격자 기준(연두색)으로 보면 1,4,9가 .. 2022. 1. 26.
백준 2580 자바 - 스도쿠 (BOJ 2580 JAVA) 문제 : boj2580 row기준 9개, 세로기준 9개, 3x3으로 나뉜 9개에 모두 1~9가 하나씩 들어가기만 하면 된다. 따라서 로직은 다음과 같다. 1. 입력에서 0이 아닌 칸에 대해 위 3개의 조건을 체크한다. 2. 0인 칸 모두에 대해 차례대로 1~9중 들어갈 수 있는 숫자를 무작정 넣어본다. 3. 그렇게 해서 0인칸 모두를 채울 수 있는 경우가 나온다면 그대로 출력하면 된다. 그렇지 않다면 바로 직전 단계로 돌아가서 다른 수를 넣어본다.(따라서 백트래킹 문제이다.) 예를들어 기본 예제를 약간 변경한 다음 스도쿠 이미지를 보자. 저 빨간부분에는 우선 row를 기준으로 보면(초록색 선) 아직 체크안된 값은 1과 4이다. 그리고 col기준(파란선)으로 보면 역시 1과 4가 들어갈 수 있다. 격자 기.. 2022. 1. 26.
백준 14467 자바 - 소가 길을 건너간 이유 1 (BOJ 14467 JAVA) 문제 : boj14467 결국 1~10에 해당하는 값을 저장해둘 수 있는 자료구조만 있으면 된다. 내경우엔 11개(인덱스 0번은 안씀) 짜리 배열로 처리했고, 문제에서 절대 등장할 수 없는 값으로 초기값을 설정한다(내 경우엔 -1). 이후 N개의 입력을 받으면서 입력받은게 'A B'라고 한다면, A는 1~10에 해당한다. A의 값이 초기값이라면 그냥 B를 배열에 넣고, 그렇지 않을 경우 이전과 비교해서 위치가 변경되었다면 cnt를 1 증가하고 값을 넣는다. 이걸 N번에 걸쳐 진행하면 되고, 최종적으로 cnt가 답이 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; i.. 2022. 1. 25.
백준 20040 자바 - 사이클 게임 (BOJ 20040 JAVA) 문제 : boj20040 N개의 정점이 있는 그래프에 대해 M개의 간선을 순서대로 연결하면서 사이클이 언제 생기는지 파악하면 된다. 즉, 간선을 연결하는 중에 사이클 판정만 할 수 있다면 풀 수 있다. 내 경우엔 union-find를 사용해 disjoint set(분리 집합)에 대해 판단했다. 새로운 간선을 연결했을 때, 연결한 두 정점이 동일한 그룹이라면 사이클이 생긴 경우이므로, 현재까지 연결한 간선의 개수를 카운팅한걸 답으로 출력하면 된다. 모든 간선을 연결해도 사이클이 생기지 않았다면 0을 출력하면 된다. 코드 : github import java.io.DataInputStream; import java.io.IOException; import java.util.Arrays; public clas.. 2022. 1. 24.
백준 1806 자바 - 부분합 (BOJ 1806 JAVA) 문제 : boj1806 1. 틀린 방법 ※ 제가 틀린 방법에 대해 써둔 것으로, 해설만 보고 싶다면 2번부터 보시면 됩니다. 덱에 모든 값들을 담으면서 그 합을 따로 계산한다. 그럼 일단 그 합은 최대치로 나올 수 있는 합이 될 것이다. 그 합이 S보다 작다면 0을 출력하고, 그렇지 않다면 합이 S보다 작아질 때 까지 덱의 시작부분과 끝부분을 각각 peek 해봐서 둘 중 작은 값을 덱에서 빼버린다. 이렇게 하면 그리디하게 답을 구할수 있을줄 알았다. 예를들어 S가 5일 때 다음과 같이 수행한다. 이렇게 짠 코드는 다음과 같다. ※ 틀린 코드임 ... int n = nextInt(); int s = nextInt(); int sum = 0; Deque dq = new ArrayDeque(); for (in.. 2022. 1. 23.
백준 1450 자바 - 냅색문제 (BOJ 1450 JAVA) 문제 : boj1450 1. 문제 접근 딱히 냅색과 관련없어 보이는 문제이다. N이 작아 쉽게 풀 수 있을 줄 알았다. 근데 당연하게도 모든 경우를 보면 O(2^30) 이므로 통과할 수 없다. 그렇다고 냅색처럼 DP로 풀자니 1~10^9 까지 확인해야 할 것 같으니 역시 통과할 수 없다. bit DP쪽으로도 딱히 떠오르지 않았다. 그래서 이 문제에서 적용한 방식처럼 반반을 나눠서 생각해보기로 했다. 1.1 최대 30개의 데이터를 대충 반반으로 15개씩 나눈다(사실 한쪽을 25개, 한쪽을 5개로 해도 상관없다.). 이걸 A와 B라 하겠다. 1.2 A에 대해 나올 수 있는 모든 무게 합의 경우의 수 확인하고 어딘가에 저장한다. 이 경우 최대 15번에 대해 해당 수를 포함하거나 포함하지 않거나의 2가지 경우이.. 2022. 1. 22.
백준 2252 자바 - 줄 세우기 (BOJ 2252 JAVA) 문제 : boj2252 1. 그래프로 생각해보자. 이런식으로 A에서 B로 향한다던지, A와 B가 연관되었다든지 하면 일단 그래프로 생각해보는게 이해하기 편하다. 이 문제에서는 'A가 학생 B의 앞에 서야 한다'에 대해 A에서 B로의 간선을 긋는 방향 그래프로 생각해보자. 그럼 다음과 같은 경우를 보자. 5 3 1 2 2 3 4 5 위의 경우를 그래프로 나타내보면 다음과 같다. 위와 같은 경우는 간단하다. 이 문제의 경우 1->2->3을 먼저 가던지, 4->5를 먼저 가던지, 심지어 1->4->2->3->5 이렇게 가던지 상관없다. 서로 섞여있더라도 아무튼 모든 경우에서 A가 B보다 먼저 나오기만 하면 된다. 그렇다면 M개의 A, B를 입력받으면서, A에 나타났으면서 B에는 등장하지 않은 1과 4어디에서든.. 2022. 1. 21.

티스토리툴바