코딩 테스트
백준 11505 자바 - 구간 곱 구하기
www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 세그먼트를 이용해서 구간의 곱을 구하면 된다. 문제에서 신경쓸 부분으로는 1. 입력받은 값은 항상 1,000,000,007보다 낮으므로 항상 나머지가 된다. 2. 입력받은 값은 최대 1,000,000 이므로 곱을 누적하면 숫자가 커지므로 tree에 저장할때는 나머지값으로 셋팅한다. 3. 두수 곱의 나머지는 두수의 나머지의 곱과 같다(단 나누는 수보다..
백준 1194 자바 - 달이 차오른다, 가자. 문제
www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 이문제의 해결점은 방문 여부를 3차원배열로 만들고 소지한 키들을 비트마스크로 하여 방문한 지점에 가지고 있는 키목록으로 방문한 적이 있는지 없는지를 셋팅하는 것이다. import java.io.*; import java.util.*; // 달이 차오른다, 가자. 문제 - 1194번 class Dot { int x; int y; int key; int time; public Dot(..
백준 17143 자바 - 낚시왕 문제
www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 생각보다 푸는데 오래걸렸는데 그이유로 1. map을 int로 하고 상어의 크기로 상어의 유무만을 처리할려고함. 2. ArrayList의 인자 값을 remove를 save하게 하는 방식을 몰랐음 1. 이부분이 문제로 다가온 이유는 둘 이상의 상어가 동일한 지점으로 이동하는 경우에 크기가 큰 상어를 남기고 다른 상어를 삭제해야하는데, 이동을 하면서 map에 작은 상어가 먼저 처리되서 있을때 큰상..
프로그래머스 - 큰수 만들기 문제 - 자바
programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr k 가 0이 될때 까지 앞서 들어온 값들과 비교해가면서 큰수를 만든다고 생각하면된다. 수 = 1924, k= 2인 경우 1입력 - {1} 9입력 - {9} (기존에 있던 1을 제거됨) 2입력 - {9, 2} 4입력 - {9, 4} (기존에 있던 2을 제거됨) // 프로그래머스 큰수 만들기 문제 class BiggestNumber { public String solution(String number, int k) { char[] result = new char[number.length() - k]; Stack stack = new Stack(); for(..
프로그래머스 - 조이스틱 문제 - 자바
programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 1. 문자 전체를 A에서 해당 문자를 만드는데 조작횟수를 구한다. - 문자에서 - 'A'를 뺀 값과 'Z' - 문자 + 1(A에서 Z가는) 둘 중 작은값이 조작횟수가 됨 2. 각 위치에서 - 각 위치의 다음 부터 A가 연속으로 있는 갯수를 구함. - 처음부터 i번째 까지 갔다가 다시 처음으로 오는 방식과 처음부터 반대로 갔다가 다시 i번째 까지가는 방식 중..
프로그래머스 - 디스크 컨트롤러 문제 - 자바
programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 작업리스트를 시작요청이 빠른순, 소요시간이 짧은 순으로 정렬하고 우선순위 큐를 소요시간이 짧은 순으로 정렬되게 셋팅 후 작업 리스트의 첫번째 작업을 큐에 넣고 큐를 순회하면서 현재 시간과 총 시간을 계산한다. 여기서 visited배열을 통해서 큐에 넣을 값들을 체크한다. import java.util.*; class Process implements Comparable{..
프로그래머스 - 더 맵게 문제 - 자바
programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 우선순위 큐를 이용한 간단한 구현 문제로 1. 스코빌 지수가 낮은순서대로 우선순위를 가지도록 우선순위 큐를 만들고 2. 각 음식의 지수를 우선순위 큐에 넣는다. 3. 지수가 가장 작은 음식의 지수가 목표인 K미만이면 - 우선순위큐에 두개 이상의 음식이 있는지 확인한다. 1) 우선순위 큐에 음식이 하나만 있는 경우 K 이상의 음식을 만들수 없으므로 -1 - 두 음식..
백준 1655 자바 - 가운데를 말해요 문제
www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 우선순위 큐를 이용해서 heap을 만들어서 처리하는 방법 maxheap은 큰 값이 우선 minheap은 작은 값이 우선 입력 값을 maxheap에 1개 추가후 minheap에 추가하면서 두개의 길이를 지속적으로 맞춰줌. maxheap의 최대값이 minheap의 최소값보다 크다면 둘을 swap 한다. maxheap의 최대값이 중간값이 된다. 문제의 예시의경우 swap이 발생하지는 않음 1 입력 [..