본문 바로가기
  • 개발하는 곰돌이

BOJ114

[Kotlin] 백준 17390 : 이건 꼭 풀어야 해! 문제 링크 17390번: 이건 꼭 풀어야 해! [2, 5, 1, 4, 3]을 비내림차순으로 정렬하면 [1, 2, 3, 4, 5]이다. www.acmicpc.net 문제 해설 누적합과 부분합에 대한 기본적인 문제에 정렬이 추가되었다고 볼 수 있다. 입력 받은 배열을 오름차순으로 정렬한 후 각 인덱스에 대한 누적 합 배열을 생성하여 테스트 케이스 별로 \(L\)과 \(R\) 사이의 부분 합을 출력해주면 된다. Code import java.util.StringTokenizer fun main() = with(System.`in`.bufferedReader()) { val bw = System.out.bufferedWriter() val (n, q) = readLine().split(' ').map { it... 2022. 12. 28.
[Kotlin] 백준 25325 : 학생 인기도 측정 문제 링크 25325번: 학생 인기도 측정 학생 이름이 공백으로 구분된 문자열 A가 주어진다. 문자열 A에는 중복된 학생 이름이 존재하지 않는다. 학생 이름은 알파벳 소문자로 이루어져 있다. 각 학생이 좋아하는 학생의 학생 이름 목록 www.acmicpc.net 문제 해설 맵과 정렬을 이용하여 풀 수 있는 문제다. 풀이 과정은 다음과 같다. 맵에는 Key로 학생의 이름을, Value로 학생들의 인기도를 저장한다. 학생 이름과 인기도를 필드로 갖는 Student 클래스에 Comparable 인터페이스를 구현하여 인기도는 내림차순, 인기도가 같으면 이름 기준 오름차순으로 정렬할 수 있게 한다. 인기도 저장이 끝난 이후에는 각 학생 이름과 인기도로 Student 객체를 생성하여 별도의 리스트나 배열에 저장한다.. 2022. 12. 25.
[Kotlin] 백준 1092 : 배 문제 링크 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 문제 해설 문제를 풀기 위해 먼저 크레인의 무게 제한과 박스의 무게를 내림차순으로 정렬한다. 가장 짧은 시간 내에 모든 박스를 배로 옮기기 위해선 아직 남아있는 상자 중에 각 크레인이 옮길 수 있는 가장 무거운 상자를 옮겨야 한다. 구현 과정은 다음과 같다. 크레인의 무게 제한과 박스의 무게를 내림차순으로 정렬한다. 크레인의 가장 큰 무게제한보다 무거운 상자가 있다면 즉시 -1을 출력하고 프로그램을 종료한다. 그 외의 경우에는 현재 옮.. 2022. 12. 24.
[Kotlin] 백준 1456 : 거의 소수 문제 링크 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 문제 해설 수의 범위가 주어졌을 때 해당 범위 내에서 소수의 거듭제곱이 되는 수의 개수를 찾는 문제다. 범위가 최대 \(10^{14}\)이지만 소수는 최대 \(10^{7}\) 범위 내에서만 찾으면 된다. 소수의 거듭제곱이 범위 내에 포함되는지를 찾아야하는데 \(10^{7}=\sqrt{10^{14}}\)이므로 \(10^7\)을 초과하는 소수는 거듭제곱을 하면 범위를 벗어나기 때문이다. 따라서 우선 에라토스테네스의 체를 이용하여 \(\sqrt{B}\) 이하인 소수를.. 2022. 12. 23.
[Kotlin] 백준 25192 : 인사성 밝은 곰곰이 문제 링크 25192번: 인사성 밝은 곰곰이 첫번째 새로운 사람이 들어온 뒤 pjshwa, chansol, chogahui05은 모두 곰곰티콘으로 인사했다. 두번째 새로운 사람이 들어온 뒤 pjshwa와 chansol은 다시 곰곰티콘으로 인사했다. www.acmicpc.net 문제 해설 Set을 사용하여 풀 수 있는 문제다. 새로운 사람이 입장하고 각 유저들이 처음 입력하는 채팅은 모두 곰곰티콘 인사가 된다. 따라서 채팅을 입력한 유저의 닉네임을 Set에 저장하는 것에 성공하면(=채팅을 처음 입력한 유저라서 곰곰티콘으로 인사한 경우라면) count를 1 증가시킨다. ENTER가 입력되면 Set을 초기화하고 같은 과정을 수행하면 된다. ENTER가 입력되면 새로운 Set으로 초기화하는 방법을 사용했다. c.. 2022. 12. 21.
[Kotlin] 백준 14277 : 등차 수열과 등비 수열 문제 링크 14277번: 등차 수열과 등비 수열 예제 4의 경우에 4, 20, 100, 452, 476, 500, 524, 548, 572, 596이 정답이다. www.acmicpc.net 문제 해설 문제만 보면 "그냥 등차 수열과 등비 수열을 set에 저장하고 크기를 출력하면 되는게 아닌가?" 싶지만 입력 범위에 함정이 있다. u의 범위가 \(10^{12}\)까지, 즉 1조라는 큰 숫자이기 때문에 a와 b가 1이고 u가 \(10^{12}\)이라면 등차 수열을 구하는데만 10,000초의 시간이 걸리게 될 뿐만 아니라 1조개의 Long타입을 set에 저장하게 되므로 7TB가 넘는 엄청난 양의 메모리를 차지하게 된다. 그렇기 때문에 좀 더 수학적인 방법의 접근이 요구된다. 등차 수열에 포함되는 1 이상, u.. 2022. 12. 21.
[Kotlin] 백준 9935 : 문자열 폭발 문제 링크 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제 해설 스택을 사용하여 해결할 수 있다. 문제 해결 과정은 다음과 같다. 먼저 문자열을 앞에서부터 순회하면서 스택에 문자를 삽입한다. 스택에 문자를 삽입하는 도중에 폭발 문자열의 마지막 글자가 나타나면 폭발 문자열의 길이만큼 스택에서 문자를 제거하여 폭발 문자열인지 체크할 문자열을 만든다. 이 때 스택에서 현재 스택의 크기가 폭발 문자열의 길이보다 작을 수 있기 때문에 EmptyStackException을 방지하기 위한 체크 로직을 .. 2022. 12. 19.
[Kotlin] 백준 1806 : 부분합 문제 링크 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제 해설 부분합과 투 포인터가 결합된 문제다. 부분합에 대한 내용은 아래 포스트를 참고하면 좋다. 링크 : 누적합(Prefix Sum)과 부분합(Partial Sum) with Kotlin 누적합을 저장할 크기가 \(n+1\)인 배열을 선언하고 1번째 인덱스부터 누적합을 저장해나간다. 이후 투 포인터를 사용해서 배열 위를 이동하기 시작한다. start부터 end까지의 합이 \(S\) 이상이라면 기존 구간 길이의 최소값과 현재 구간 길이.. 2022. 12. 17.

티스토리툴바