본문 바로가기

알고리즘145

백준 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.
백준 7785 회사에 있는 사람 (JAVA 자바 풀이) 백준 7785 회사에 있는 사람 (JAVA 자바 풀이) 💡 잘못된 풀이 초기 구현한 코드는 문제의 요구사항을 그대로 따른 코드였다. 1) 입력을 받으면서 2) 리스트에 직원 객체를 넣는다. 3) 이때 이미 입력으로 받은 직원이면 상태를 업데이트해주고 4) 새롭게 들어온 직원이면 객체를 생성해서 넣어준다. 5) 역순으로 정렬하고 6) 회사에 있는 직원만 출력한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; public class Mai.. 2023. 6. 25.
백준 1181 단어 정렬 (JAVA 자바 풀이) | 문자열 길이순, 알파벳 순 정렬, 스트링 compareTo 메서드, thenComparing 메서드 백준 1181 단어 정렬 (JAVA 자바 풀이) 문제의 조건대로 정렬을 구현해주면 된다. 중복에 대한 제거는 문자열을 받으면서 배열에 저장할 때 해도 되고 마지막에 해도 된다. 가장 간단하게 컬렉션 Set을 이용해서 구현했다. 정렬은 2가지 조건을 만족해야 한다. 1. 길이순 정렬 2. 알파벳순 정렬 그 전에 시간 복잡도를 생각해보자. 데이터가 2만이고 시간은 2초이므로 넉넉한 편이다. Arrays.sort()는 참조형 타입에 대해 O(nlogn) 시간 복잡도를 보장하므로 (https://upcurvewave.tistory.com/379) 20,000개의 데이터에 대해 약 28만 번의 연산을 수행할 것이다. 문자열의 최대 길이는 50으로 주어졌기 때문에 여기에 50을 곱하면 약 1,400만으로 계산된다... 2023. 6. 25.

티스토리툴바