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

Algorithm118

[Kotlin] 프로그래머스 : 테이블 해시 함수 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해설 문제를 해결하기 위해 가장 먼저 배열을 조건에 맞게 정렬해야한다. 2번 조건에 col번째 컬럼의 값을 기준으로 오름차순 정렬하고, 값이 동일하면 첫 번째 컬럼의 값을 기준으로 내림차순 정렬하라는 언급이 있으므로 data를 해당 조건에 맞게 정렬한다(코드의 3번째 줄). 이후 row_begin번째 튜플부터 row_end번째 튜플까지의 \(S_i\)를 구하여 별도의 배열 또는 리스트에 저장한다(코드의 4~11번째 줄). 마지막으로 각 \(S_i\)에 대하여 XOR 연산을 수행하여 반환한다. .. 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.
투 포인터(Two Pointer) with Kotlin 투 포인터(Two Pointer) 투 포인터(Two Pointer) 알고리즘은 배열이나 리스트에서 두 개의 점을 이동시키면서 원하는 결과를 얻어내는 알고리즘이다. 예를 들어 부분합을 구하는 문제에서 배열과 부분합을 구할 특정 인덱스가 주어지는 것이 아니라 특정 값이 주어지고 부분합이 주어진 값과 일치하는 구간의 수 또는 구간의 최대/최소 길이를 구해야 하는 경우를 생각해볼 수 있다. 이 경우에 누적합이 계산된 배열이 있어도 단순히 이중 반복문으로 답을 찾게 되면 \(O(n^{2})\)의 시간 복잡도를 갖게 되어 배열의 크기가 10만 정도만 되더라도 100억회의 연산을 해야하기 때문에 굉장히 비효율적이다. 이럴 때 투 포인터를 사용하는 것이 대안이 될 수 있다. 투 포인터는 각각 구간의 시작과 끝을 가리키.. 2022. 12. 18.

티스토리툴바