본문 바로가기

알고리즘/백준123

백준 10813 공 바꾸기 (JAVA 자바 풀이) 백준 10813 공 바꾸기 (JAVA 자바 풀이) 10810 공 넣기 문제와 마찬가지로 그대로 구현해주면 된다. 풀이에 있어서 배열 내부를 먼저 초기화해주고 할 것인지, swap 하는 과정에서 초기화할 것인지를 선택할 수 있다. 후자로 하면 마지막에 초기화하지 않은 0에 대해서도 index를 설정해준 값에 대해서 한번 작업을 해주어야 한다. 먼저 초기화해주는 것이 편하다고 판단해 그렇게 풀이했다. 💡 코드 구현 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.util.stream.IntStream; publ.. 2023. 7. 2.
백준 10810 공 넣기 (JAVA 자바 풀이) 백준 10810 공 넣기 (JAVA 자바 풀이) 단순 구현 문제로서 구현해주면 된다. 범위가 전체 배열을 순회하도록 주어지면 이중 반복문이 돌면서 최대 O(n^2)까지 시간 복잡도가 높아지지만 주어지는 N,M 데이터의 최대 범위가 100으로 낮기 때문에 괜찮다. 💡 코드 구현 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.util.stream.IntStream; public class Main { private static final BufferedReader bufferedReader = new Buff.. 2023. 7. 2.
백준 16713 Generic Queries (JAVA 자바 풀이) 백준 16713 Generic Queries (JAVA 자바 풀이) 누적합 배열은 구간합 연산 뿐 아니라 R -> L 사이의 연산을 제거하여 복원 작업이 가능한 다른 연산에 대해서도 가능하다. XOR 연산 역시 이전에 구한 합이 다음 합으로 연결되므로 구간XOR 배열로 구성할 수 있고 슬라이스된 범위에 대해서도 구간합을 구하는 것과 같은 로직으로 구할 수 있다. 이를 수식화 해보면 XOR(arr[L], arr[R]) = acc[R] - acc[L-1] 구간 XOR 배열을 다음과 같이 구한다. int[] numbers = new int[N + 1]; int[] Snumbers = new int[N + 1]; for (int i = 1; i 2023. 7. 1.
백준 2910 빈도 정렬 (JAVA 자바 풀이) 백준 2910 빈도 정렬 (JAVA 자바 풀이) 문제의 조건을 요약해보면 다음과 같다. 정렬을 하되, 1) 더 많이 숫자가 앞에 오도록 2) 등장 횟수가 같으면 먼저 등장한 숫자가 앞에 오도록 두 번째 조건 때문에 까다로워진 문제이다. 카운트를 배열을 이용해 구하는 방식 중 하나는 인덱스의 카운트를 올리는 방식이다. 이 방식을 사용하면 비교적 간단하게 풀이가 가능하지만, 10억이 넘어가는 C의 범위 때문에 반드시 메모리 초과가 날 것이다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; im.. 2023. 7. 1.
백준 1302 베스트셀러 (JAVA 자바 풀이) 백준 1302 베스트셀러 (JAVA 자바 풀이) 중복되는 값을 찾는 로직을 사용하면 시간 복잡도가 급격하게 올라간다. 검색 수행을 hash로 한다면 O(n^2)은 피할 수 있고 또 시간도 넉넉하기 때문에 그렇게 해도 풀릴 수 있지만 정렬의 특성을 이용하면 보다 간단하게 풀 수 있다. 즉, 정렬이 된 후에 값들이 한 곳으로 모여 있게 된다는 특성을 이용한다. 예를 들어 아래와 같은 데이터를 받아서 정렬하면 9 table chair table table lamp door lamp table chair [chair, chair, door, lamp, lamp, table, table, table, table]로 정렬된다. 이러한 값들에 대해서 하나씩 카운팅을 해주면 한 번의 반복문으로 카운팅을 완료할 수 있으.. 2023. 6. 30.

티스토리툴바