본문 바로가기

백준749

백준 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.
백준 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.
백준 2467 자바 - 용액 (BOJ 2467 JAVA) 문제 : boj2467 1. 당연히 모든 쌍을 확인해보면 O(N^2)이 걸릴 것이므로 통과가 불가하다. 이 문제는 투 포인터 알고리즘으로 풀 수 있는 기본형 문제이다. 또는 안풀어보긴 했으나 이분탐색으로도 문제없이 풀 수 있을 것 같다(N개를 TreeSet에 넣어둔 후 N개의 값을 순회하며 해당 값에 -1을 곱한 값에 대해 TreeSet에서 ceilling과 floor를 확인해 그 중 작은 수를 택하면 될 듯함). 2. 이미 정렬되어 들어온 데이터 이므로 정렬과정 필요 없이 첫번째 값을 s로 가르키고, 맨 뒤의 값을 e로 가르켜보자. 이제 s와 e가 가르키는 값을 합쳐가며 이 중 0과 가장 가까운 값을 찾으면 된다. s와 e를 변경하는 규칙은 다음과 같다. arr[s]+arr[e] == 0 -> 바로 출.. 2022. 1. 20.

티스토리툴바