Baekjoon/Silver
-
이번 문제는 우선순위 큐를 이용하는 문제이다. Comparable과 Comparator라는 인터페이스가 있다. 이 두 개의 인터페이스는 두 값을 비교해 어떠한 기준으로 정렬을 시키는 인터페이스이다. 그래서 이 인터페이스를 이용하여 정렬을 한 후 큐에서 poll() 메소드를 사용하면 된다. 필자는 Comparator라는 인터페이스를 사용했는데 compare라는 메소드를 오버라이딩하여 사용하면 된다. 우리가 생각해야할 기준은 두 가지이다. 먼저 절댓값이 서로 다를 때. 절댓값이 서로 다르면 어느 하나의 절댓값이 더 크다는 소리다. 절댓값이 더 큰 수가 뒤로 배치되어야 한다. 절댓값이 같으면 원래의 수가 더 작은 것이 앞에와야한다. 이 두가지를 생각하고 로직을 짜면 된다. 아래 코드를 보자. import ja..
[백준] 스택, 큐 - 11286_절댓값 힙 Java[자바]이번 문제는 우선순위 큐를 이용하는 문제이다. Comparable과 Comparator라는 인터페이스가 있다. 이 두 개의 인터페이스는 두 값을 비교해 어떠한 기준으로 정렬을 시키는 인터페이스이다. 그래서 이 인터페이스를 이용하여 정렬을 한 후 큐에서 poll() 메소드를 사용하면 된다. 필자는 Comparator라는 인터페이스를 사용했는데 compare라는 메소드를 오버라이딩하여 사용하면 된다. 우리가 생각해야할 기준은 두 가지이다. 먼저 절댓값이 서로 다를 때. 절댓값이 서로 다르면 어느 하나의 절댓값이 더 크다는 소리다. 절댓값이 더 큰 수가 뒤로 배치되어야 한다. 절댓값이 같으면 원래의 수가 더 작은 것이 앞에와야한다. 이 두가지를 생각하고 로직을 짜면 된다. 아래 코드를 보자. import ja..
2024.02.07 -
이번 문제는 큐의 자료구조를 파악하는 문제이다. 큐는 First In First Out으로 처음 넣는 값을 처음으로 뺄 수 있는 자료구조이다. 그래서 이번 문제는 어렵지 않다고 볼 수 있다. 주어진 숫자만큼 큐에 넣어준다. 예를 들어 6이면 1 2 3 4 5 6 순서로 큐에 넣어준다. 여기서 1을 poll() 메소드로 꺼내오고 2를 6뒤에 붙이려면 que.add(que.poll())의 형식으로 붙일 수 있다. 이 과정을 큐 안에 데이터가 하나만 남을 때까지 반복하면 쉽게 답을 구할 수 있다. 아래 코드를 보자. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOExc..
[백준] 스택, 큐 - 216_카드 2 Java[자바]이번 문제는 큐의 자료구조를 파악하는 문제이다. 큐는 First In First Out으로 처음 넣는 값을 처음으로 뺄 수 있는 자료구조이다. 그래서 이번 문제는 어렵지 않다고 볼 수 있다. 주어진 숫자만큼 큐에 넣어준다. 예를 들어 6이면 1 2 3 4 5 6 순서로 큐에 넣어준다. 여기서 1을 poll() 메소드로 꺼내오고 2를 6뒤에 붙이려면 que.add(que.poll())의 형식으로 붙일 수 있다. 이 과정을 큐 안에 데이터가 하나만 남을 때까지 반복하면 쉽게 답을 구할 수 있다. 아래 코드를 보자. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOExc..
2024.02.07 -
이번 문제는 스택이 어떤 자료구조인지를 파악하는 문제였다. 스택은 Last in, First out으로 제일 먼저 넣은 값이 제일 마지막에 나오는 자료구조이다. 그래서 입력된 값을 기준으로 1부터 순차적으로 stack에 넣은 뒤 입력된 값이 stack에 들어가는 값보다 작으면 그 때 stack에서 pop() 메소드를 사용해 배열을 완성시켜 간다. 그리고 입력되는 값이 stack의 젤 마지막에 들어간 값보다 작으면 NO를 반환하고 그렇지 않으면 pop() 메소드를 사용해 배열을 마저 완성시키면 된다. 아래 코드를 참고하자. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws..
[백준] 스택, 큐 - 1874_스택 수열 Java[자바]이번 문제는 스택이 어떤 자료구조인지를 파악하는 문제였다. 스택은 Last in, First out으로 제일 먼저 넣은 값이 제일 마지막에 나오는 자료구조이다. 그래서 입력된 값을 기준으로 1부터 순차적으로 stack에 넣은 뒤 입력된 값이 stack에 들어가는 값보다 작으면 그 때 stack에서 pop() 메소드를 사용해 배열을 완성시켜 간다. 그리고 입력되는 값이 stack의 젤 마지막에 들어간 값보다 작으면 NO를 반환하고 그렇지 않으면 pop() 메소드를 사용해 배열을 마저 완성시키면 된다. 아래 코드를 참고하자. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws..
2024.02.07 -
슬라이딩 윈도우는 창문이 열리듯 같은 범위를 유지하며 한 칸씩 이동하면서 값을 찾는 알고리즘이다. 이 문제는 초기 구간을 설정한 뒤 한 칸씩 이동을 하며 값을 찾으면 되는 문제이다. 0부터 P까지 반복문을 돌며 초기 문자열이 비밀번호에 부합하는지 확인 후 한 칸씩 이동하며 값을 찾아내면 된다. 초기 최소 개수를 설정을 해줄 때에 최소 개수가 0이면 count를 하나씩 증가 시켜줘야 값이 달라지지 않는다. 아래 코드를 보자. import java.util.*; import java.io.*; public class Main { static int count; static int[] myArr; static int[] checkArr; public static void main(String[] args) t..
[백준] 슬라이딩 윈도우 - 12891_DNA 비밀번호 Java[자바]슬라이딩 윈도우는 창문이 열리듯 같은 범위를 유지하며 한 칸씩 이동하면서 값을 찾는 알고리즘이다. 이 문제는 초기 구간을 설정한 뒤 한 칸씩 이동을 하며 값을 찾으면 되는 문제이다. 0부터 P까지 반복문을 돌며 초기 문자열이 비밀번호에 부합하는지 확인 후 한 칸씩 이동하며 값을 찾아내면 된다. 초기 최소 개수를 설정을 해줄 때에 최소 개수가 0이면 count를 하나씩 증가 시켜줘야 값이 달라지지 않는다. 아래 코드를 보자. import java.util.*; import java.io.*; public class Main { static int count; static int[] myArr; static int[] checkArr; public static void main(String[] args) t..
2024.02.04 -
이번 문제는 투 포인터로 풀면 쉽게 풀 수 있는 문제이다. 먼저 고유한 번호들을 오름차순으로 정렬시킨다. 그 후 처음에 포인트 한 개, 마지막에 포인트 한 개를 두고 그 합을 M과 비교를 하면 된다. start와 end 포인트가 있다고 가정해보자. arr[start] + arr[end] > M 이면 오름차순이므로 end--를 해준다. 그 반대의 경우라면 start++를 해준다. 만약 두 수의 합이 M과 같다면 count++와 함께 start++, end--를 같이 해준다. 아래 코드를 보자. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { Bu..
[백준] 투 포인터 - 1940_주몽 Java[자바]이번 문제는 투 포인터로 풀면 쉽게 풀 수 있는 문제이다. 먼저 고유한 번호들을 오름차순으로 정렬시킨다. 그 후 처음에 포인트 한 개, 마지막에 포인트 한 개를 두고 그 합을 M과 비교를 하면 된다. start와 end 포인트가 있다고 가정해보자. arr[start] + arr[end] > M 이면 오름차순이므로 end--를 해준다. 그 반대의 경우라면 start++를 해준다. 만약 두 수의 합이 M과 같다면 count++와 함께 start++, end--를 같이 해준다. 아래 코드를 보자. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { Bu..
2024.02.02 -
이 문제는 쉽게 풀 수 있는 문제였지만 합 배열을 생각하다보니 좀 헤맸었다. 합 배열로 투 포인터를 사용해보려고 시도를 하다 책을 봤다. 이렇게 쉽게 푼다고...? 싶을 정도로 간단한 풀이방법.. 문제를 잘 보면 연속된 숫자라고는 하지만 단 하나의 숫자만 있어도 정답 처리가 된다,. 따라서 count는 1로 선언한다. 또한 start와 end도 1부터 시작을 해 차근차근 올라간다. start와 end 까지의 합이 N보다 작으면 end를 하나 올려주고 더 크면 start를 하나 올려준다. 만약 N과 같을 경우 count를 하나 올려주고 end를 올려준다. 코드를 보자. import java.io.*; public class Main { public static void main(String[] args) ..
[백준] 투 포인터 - 2018_수들의 합5 Java[자바]이 문제는 쉽게 풀 수 있는 문제였지만 합 배열을 생각하다보니 좀 헤맸었다. 합 배열로 투 포인터를 사용해보려고 시도를 하다 책을 봤다. 이렇게 쉽게 푼다고...? 싶을 정도로 간단한 풀이방법.. 문제를 잘 보면 연속된 숫자라고는 하지만 단 하나의 숫자만 있어도 정답 처리가 된다,. 따라서 count는 1로 선언한다. 또한 start와 end도 1부터 시작을 해 차근차근 올라간다. start와 end 까지의 합이 N보다 작으면 end를 하나 올려주고 더 크면 start를 하나 올려준다. 만약 N과 같을 경우 count를 하나 올려주고 end를 올려준다. 코드를 보자. import java.io.*; public class Main { public static void main(String[] args) ..
2024.02.02 -
바로 전 문제와 마찬가지로 구간합을 이용하면 풀 수 있는 문제이다. 다만, 구간 합을 구하는 방법이 전과는 달라졌다. 먼저 A[2,2] 까지의 합을 구하는 방법을 생각해보면 S[1,2] + S[2,1] - S[1,1] + A[2,2]로 나타낼 수 있다. 이것으로 보아 합 배열을 나타내는 표현식은 S[i,j] = S[i - 1, j] + S[i, j - 1] - S[i - 1, j - 1] + A[i, j] 이다. 위에 나온 예제를 활용하여 [2,2]부터 [3,4]까지의 합을 구해보면 S[3,4] - S[3,1] - S[1, 4] + S[1, 1]으로 표현이 가능하다. 이제 공식으로 변환을 하면 [x1, y1] 부터 [x2, y2] 까지의 합은 S[x2, y2] - S[x2, y1-1] - S[x1-1, ..
[백준] 구간 합 - 11660_구간 합 구하기 Java[자바]바로 전 문제와 마찬가지로 구간합을 이용하면 풀 수 있는 문제이다. 다만, 구간 합을 구하는 방법이 전과는 달라졌다. 먼저 A[2,2] 까지의 합을 구하는 방법을 생각해보면 S[1,2] + S[2,1] - S[1,1] + A[2,2]로 나타낼 수 있다. 이것으로 보아 합 배열을 나타내는 표현식은 S[i,j] = S[i - 1, j] + S[i, j - 1] - S[i - 1, j - 1] + A[i, j] 이다. 위에 나온 예제를 활용하여 [2,2]부터 [3,4]까지의 합을 구해보면 S[3,4] - S[3,1] - S[1, 4] + S[1, 1]으로 표현이 가능하다. 이제 공식으로 변환을 하면 [x1, y1] 부터 [x2, y2] 까지의 합은 S[x2, y2] - S[x2, y1-1] - S[x1-1, ..
2024.01.31 -
구간의 합을 구하는 문제이다. 이렇게 구간의 합을 구하는 문제는 반복문을 계속 돌리게 되면 시간을 더욱 낭비하게 된다. 이러한 문제는 구간 합 배열을 선언해준뒤 적용하여 문제를 풀 수 있다. 구간 합 배열은 i번째 인덱스에 있는 값이 i번째 전의 모든 인덱스에 해당하는 값에 i번째 인덱스에 해당하는 값을 넣는 것. 선언하는 방식 ==> S[ i ] = S[ i - 1 ] + A [ i ] 위의 합 배열만 잘 활용하면 무난하게 풀 수 있는 문제이다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buf..
[백준] 구간 합 - 11659_구간 합 구하기 Java[자바]구간의 합을 구하는 문제이다. 이렇게 구간의 합을 구하는 문제는 반복문을 계속 돌리게 되면 시간을 더욱 낭비하게 된다. 이러한 문제는 구간 합 배열을 선언해준뒤 적용하여 문제를 풀 수 있다. 구간 합 배열은 i번째 인덱스에 있는 값이 i번째 전의 모든 인덱스에 해당하는 값에 i번째 인덱스에 해당하는 값을 넣는 것. 선언하는 방식 ==> S[ i ] = S[ i - 1 ] + A [ i ] 위의 합 배열만 잘 활용하면 무난하게 풀 수 있는 문제이다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buf..
2024.01.31