문제 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 풀이 먼저 퀵 정렬로 구현하였다가 시간 초과로 실패하였다. 해결 방법을 찾던 중에 https://www.acmicpc.net/board/view/31887 이 공지글을 보았고, 이 문제를 풀기 전에 먼저 읽어보는 것을 추천한다. 이 문제는 시간 복잡도가 O(NlogN)인 정렬인 병합정렬이나 힙 정렬, 기수 정렬, 카운팅 정렬을 사용해야한다. 버블 정렬, 선택 정렬, 삽입 정렬 등은 시간 복잡도가 O(N^2)이므로 시간 초과한다. 퀵 정렬은 평범하..

문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 N을 만들기 위한 3가지 방법은 다음과 같다. 1. N가 3으로 나누어 떨어지면, 3으로 나눈다. 2. N가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 뺀다. 이를 식으로 표현하면, 1. dp[n] = dp[n/3] + 1 2. dp[n] = dp[n/2] + 1 3. dp[n] = dp[n-1] + 1 이고, 3나누기 -> 2나누기 -> 1빼기의 차례대로 연산을 사용하는 횟수가 적어질 것이다. 따라서 우선 dp[n]을 dp[n-1] + 1인 경우로 저장하고, 2의 배수이면 dp[n/2] + 1, 3의 배수이면 dp[n/3] + 1 으로 계산해준다. 코드 im..

문제 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 풀이 이 문제는 문제의 설명에 따라 구현하면 되는 문제이다. 우선 알파벳의 개수인 26을 길이로 하는 check 배열을 만들어준다. check[0] = a, check[1] 은 b, ... check[25] = z 를 의미하는 것이다. check[문자 - 'a']를 통해 문자를 체크 할 수 있다. 반복문에서 문자를 체크해주며 이번 문자가 전 문자와 같다면 continue로 생략한다. check 배열이 true이면 이 문자열은..

문제 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 이 문제는 자바에서 기본적으로 제공하는 Stack을 이용해 풀이 할 수 있지만, 이번에는 배열과 포인터 역할을 하는 변수를 이용하여 구현해 보았다. 입력받은 N크기의 stack 배열을 생성하고, 사용자의 입력에 맞게 함수를 처리한다. push(n) 함수는 ptr을 1 증가시키고 stack[ptr]에 n을 저장한다. pop() 함수는 ptr이 -1이면 -1을 반환하고, 아니라면 stack[ptr]을 반환하고 ptr을 1 빼준다. size..

문제 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 풀이 한수는 각 자리수가 등차수열이 만들어지는 숫자다. 예를 들어 123은 자리수가 1 씩 증가하는 등차수열이므로 한수이다. 입력된 숫자 N이 100 미만이라면 모두 한수이므로 출력할 cnt는 N이다. 입력된 숫자 N이 100 이상인 경우에는 백의 자리: i/100, 십의 자리 : (i/10)%10, 일의 자리 i%10를 비교한다. 각 자리수를 비교하여 차이가 같다면 한수이므로 cnt를 1 증가시켜준다. 코드 fun main() { val br = System..