본문 바로가기

Algorithm

 (252)
[백준] 2630 : 색종이 만들기 JAVA 풀이 이전에 풀었던 쿼드트리 문제와 푸는 방식은 동일하다. 한 종이가 파란색 또는 흰색 둘 중 하나의 색으로만 이루어져있다면 그 색으로만 이루어진 종이의 수를 증가시킨다. 종이가 하나의 색으로 이루어져있지 않다면 그 종이를 같은 크기로 4분할을 하고 위 과정을 반복하면 된다. 1. n을 입력받는다. 2. 종이에 각 칸이 어떤 색인지 저장할 2차원 배열 arr[n][n]를 생성한다 3. arr에 입력받은 값을 저장한다. 4. 흰색 종이의 개수와 파란색 종이의 개수를 저장할 배열 cnt[2]를 생성한다. 5. 종이가 하나의 색으로만으로 이루어져있는지 확인하는 함수 colorCheck를 구현한다. 종이의 첫번째 칸을 color라는 변수에 저장하고, 그 종이의 모든 칸이 color와 같은지 체크한다. color와 색..
[백준] 1517 : 버블소트 JAVA 풀이 처음 문제를 읽었을 때는 쉬워보이는데 정답 비율이 왜 이렇게 낮지?라는 생각이 들었다. 그리고 버블소트로 풀어보니 역시나 시간초과가 나왔다. 버블소트는 시간복잡도가 O(N^2)인데, 최대 500,000개의 수가 주어지니 그럴 만했다. swap횟수는 병합정렬을 하는 과정에 뒤쪽에 있던 인덱스가 앞으로 이동한 만큼 더해주면 된다. import java.io.*; import java.util.*; public class Main{ static long cnt = 0; static long[] sorted; public static void main(String[] args)throws IOException{ BufferedReader br = new BufferedReader(new InputStreamRe..
[백준] 2448 : 별 찍기 - 11 JAVA 풀이 https://rightbellboy.tistory.com/39 [백준/BOJ] 2448번 별찍기 - 11 (java) 백준 온라인 저지(BOJ) 2448번 별찍기 - 11 https://www.acmicpc.net/problem/2448 * 사용언어 : java, 자바 1. 문제 N( = 3 * 2 ^ k(1, 2, ... , 10) )을 입력받고 N번째 줄까지 예제와 같이 별을 출력 2. 풀이.. rightbellboy.tistory.com 이 포스트를 참고해서 풀었다. 설명이 아주 잘 되어 있어서 읽어보면 큰 도움이 될 것이다. import java.io.*; import java.util.*; public class Main{ public static void main(String[] args)t..
[백준] 1992 : 쿼드트리 JAVA 풀이 직전에 푼 문제는 보드를 9분할해가며 그 한 조각이 같은 값으로 구성돼있는지 검사하는 거였다. 이번 문제는 보드를 4분할한다는 것만 빼면 풀이방식은 완전 동일하다. 언제 괄호를 출력해야 하는지가 좀 헷갈렸지만, 간단하게 한 조각이 같은 수로만 이루어지지 않았을 때는 괄호를 열고 그렇지 않을 때는 괄호를 닫으면 된다. import java.io.*; import java.util.*; public class Main{ static int board[][]; static int[] cnt = new int[3]; static StringBuilder sb = new StringBuilder(); public static void main(String[] args)throws IOException{ Buffe..
[백준] 1780 : 종이의 개수 JAVA 풀이 너무 안 풀려서 내가 너무 어렵게 생각하고 있는 건가 하고 다른 분들의 풀이를 검색해보니 어렵게 생각하고 있던 게 맞았다 하하 그래서 이 포스트를 참고해서 문제를 해결했다. https://st-lab.tistory.com/235 [백준] 1780번 : 종이의 개수 - JAVA [자바] www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, st-lab.tistory.com 대략적인 풀이방법은 이렇다. 보드의 모든 칸을 검사해서 하나의 색으로 구성되어 있다면, 그 색깔의 개수를 1 추가한다. 여러 색이 섞여있다면 그 보드를 ..
[백준] 11728 : 배열 합치기 JAVA 풀이 1. 배열 A의 크기 N, B의 크기 M을 입력받는다. 2. A와 B에 들어있는 수를 한 번에 저장할 ArrayList를 생성한다. 3. 배열 A와 B의 내용을 ArrayList에 저장한다. 4. Collections.sort()를 사용해 ArrayList를 정렬한다. 5. ArrayList에 저장된 값을 출력한다. import java.io.*; import java.util.*; public class Main{ public static void main(String[] args)throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new String..
[백준] 1476 : 날짜 계산 JAVA 풀이 E S M은 모두 1부터 시작해서 1년이 지날 때마다 1씩 증가한다. 이때 E S M의 범위는 모두 달라서 1씩 증가하다가 자신의 범위를 넘어서면 다시 1로 돌아가야 한다. 이를 반복하면서 입력된 E S M을 만족하려면 몇 년이 걸리는지를 알아내는 문제인데, 풀이방법은 간단하다. 1. E S M을 입력받는다 2. 입력된 E S M을 만족하려면 몇 년이 걸리는지 기록할 변수 year를 생성한다. 3. 1 1 1부터 1씩 증가시켜서 E S M과 일치하는지 검사하는 데에 필요한 변수 e, s, m을 생성한다. 4. E와 e가 같고, S와 s가 같고, E와 e가 같을 때까지 e, s, m, year을 1씩 증가시킨다. 5. E==e&&S==s&&M==m을 만족할 때의 year값을 출력한다. import java..
[백준] 10824 : 네 수 JAVA 풀이 1. 문자열을 입력 받는다. 2. A와 B를 연결한 값, C와 D를 연결할 값을 저장할 StringBuilder를 생성한다. 2. A B C D는 공백으로 나누어져 입력되므로, StringTokenizer를 사용해 쪼갠다. 3. StringBuilder.append()를 사용해 A와 B, C와 D를 이어붙인다. 4. 두 StringBuilder에 저장된 값을 Long으로 캐스팅한 후 더하고 출력해준다. 아무리 봐도 문제가 없어보이는데 자꾸 NumberFormat 런타임에러가 떠서 당황스러웠다. 다시 문제를 잘 읽어보니 A B C D 각각이 1,000,000까지도 가능하기 때문에 int로는 감당할 수 없는 값이 입력될 수도 있는 거였다. 문제를 꼼꼼히 읽는 게 참 중요한 것 같다. import java.i..

티스토리툴바