Solve005
문제번호: 2108(통계학)
풀이
- 평균은 Math함수를 이용한다.
Math.round()을 사용해서 소수 첫번째 자리에서 반올림을 한 다음, 정수 값을 리턴해주록 캐스팅을 해준다.(평균을 나눌때 소수점 계산을 위해 double형으로, Math.round()를 거친 후에 리턴값으로 long형을 반환하므로 int로 캐스팅) - 중간값을 계산할때는 해당 문제의 입력이 홀수 개라고 했으므로 단순히 정렬 후, ArrayList의 size에서 1을 빼고 2로 나눈 값을 인덱스로 해서 값을 반환하면 된다.
- 빈도값 계산은 쉽지 않았다. 가장 먼저 해당 값이 몇번 사용됐는지 map을 이용해서 파악을 했다. 그 다음 map을 돌면서 가장 많이 사용된 횟수를 저장하고, 두번째 빈도값 조건을 파악하기 위해 해당 map을 Treemap을 이용해 정렬한다. 그리고 정렬된 Treemap에서 다시 최대로 사용된 값을 찾는다.
- 여기서 첫 풀이때 잘못 생각한 것이 최대값이 두번 연속으로 나오면 그때의 key가 답인줄 알았는데 이전에 저장해둔 max값이 아니면 그 값은 최대값이 아니므로 이전에 저장한 max값과 같을때라는 조건을 추가해야한다.
예시로 가장 많이 나온 수의 빈도가 3이고, 정렬된 Treemap의 빈도 값이 2,2,3 일때 첫풀이대로 하면 두번째 2의 key를 반환하게 된다. 위의 조건 하나를 추가하면 3의 key를 정확히 반환한다.
범위는 정렬하고 가장 뒤의 값과 첫번째 값을 빼면 된다.
import java.util.*;
public class boj_2108 {
static Scanner sc = new Scanner(System.in);
static ArrayList<Integer> arr = new ArrayList<>();
static int[] answer;
public static void main(String[] args) {
int testCase = Integer.parseInt(sc.nextLine());
answer = new int[testCase];
for (int i = 0; i < testCase; i++) {
int input = sc.nextInt();
arr.add(input);
answer[i] = input;
}
Collections.sort(arr);
System.out.println(average());
System.out.println(median());
System.out.println(frequent());
System.out.println(gap());
}
static int average() {
int sum = 0;
for (int i = 0; i < arr.size(); i++) {
sum += arr.get(i);
}
if (sum >= 0) {
return (int)Math.round((double) sum / arr.size());
}
else {
return (int)-Math.round((double) (-sum) / arr.size());
}
}
static int median() {
return arr.get((arr.size() - 1) / 2);
}
static int frequent() {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < arr.size(); i++) {
map.put(answer[i], map.getOrDefault(answer[i], 0) + 1);
}
int maxValue = Integer.MIN_VALUE;
for (Map.Entry<Integer, Integer> x : map.entrySet()) {
if (x.getValue() > maxValue) {
maxValue = x.getValue();
}
}
TreeMap<Integer, Integer> sortMap = new TreeMap(map);
int max = Integer.MIN_VALUE;
int result = 0;
for (Map.Entry<Integer, Integer> x : sortMap.entrySet()) {
if (x.getValue() > max) {
max = x.getValue();
result = x.getKey();
}
else if (x.getValue() == max && x.getValue() == maxValue) {
return x.getKey();
}
}
return result;
}
static int gap() {
if (arr.size() == 1) {
return 0;
}
else
return arr.get(arr.size() - 1) - arr.get(0);
}
}문제번호: 프로그래머스-정렬(H-index)
풀이
문제가 이상하다. H-index의 정의를 다시 살펴보니 논문 작성자의 논문 중 가장 많이 인용된 순으로 정렬해서 1번부터 해당 논문의 번호를 매기고, 번호가 1씩 증가되면서 논문의 인용된 횟수가 작아지는 번호가 H-index라고 한다.
n번과 x회 인용된 논문이 있다고 할때, 조건들은 n과 x가 같을때, n이 x보다 커졌을 경우(이 두가지의 경우는 바로 알 수 있었다), 그 다음 마지막으로 논문의 개수와 n이 동일해졌는데 여전히 x가 큰 경우에는 논문의 개수가 H-index가 된다는 것을 놓쳐서 조금 해맸다.
import java.util.*;
public class H_index {
public static void main(String[] args) {
int[] citations = {24, 22};
int answer = 0;
Arrays.sort(citations);
Integer[] citationsA = new Integer[citations.length];
for (int i = 0; i < citations.length; i++) {
citationsA[i] = citations[i];
}
List<Integer> citationsB = Arrays.asList(citationsA);
Collections.reverse(citationsB);
for (int i = 0; i < citations.length; i++) {
if (i + 1 == citationsA[i]) {
answer = i + 1;
break;
}
else if (i + 1 > citationsA[i]) {
answer = i;
break;
}
else if (i == citations.length - 1 && i + 1 < citationsA[i]) {
answer = citations.length;
}
}
System.out.println(answer);
}
}문제번호: 11497(통나무 건너뛰기)
풀이
배열을 정렬한 다음, 배열의 첫번째 값부터 인덱스가 짝수면 front, 인덱스가 홀수면 rear부터 가운데로 새로운 정렬을 시도했다. 이렇게 하면 각 인덱스 값들의 차이를 최소화 할 수 있다고 생각했다.
import java.util.*;
public class boj_11497 {
static Scanner sc = new Scanner(System.in);
static StringTokenizer st;
public static void main(String[] args) {
int testCase = Integer.parseInt(sc.nextLine());
for (int i = 0; i < testCase; i++) {
int num = Integer.parseInt(sc.nextLine());
st = new StringTokenizer(sc.nextLine(), " ");
int[] arr = new int[num];
int j = 0;
while(st.hasMoreTokens()) {
arr[j] = Integer.parseInt(st.nextToken());
j++;
}
System.out.println(solution(arr, num));
}
}
static int solution(int[] arr, int num) {
Arrays.sort(arr);
int[] newArr = new int[num];
int front = 0;
int rear = num - 1;
for (int i = 0; i < num; i++) {
if (i % 2 == 0) {
newArr[front] = arr[i];
front++;
}
else {
newArr[rear] = arr[i];
rear--;
}
}
int max = Integer.MIN_VALUE;
for (int i = 0; i < num - 1; i++) {
int result = 0;
if (newArr[i] - newArr[i + 1] < 0) {
result = -(newArr[i] - newArr[i + 1]);
}
else
result = newArr[i] - newArr[i + 1];
if (result > max) {
max = result;
}
}
return max;
}
}문제번호: 1920(수 찾기)
풀이
선형탐색으로 하면 최대입력이 들어왔을때 100억번의 연산이 발생하여, 시간초과가 발생하므로 이진탐색으로 풀어야 한다.
이진탐색을 위해 기준 배열은 정렬을 해주고 다른 배열의 값 x를 처음부터 하나씩 반복하며 이진탐색을 실행한다.
first, mid, last를 각각 설정하고 first와 last를 mid값보다 x보다 크면 first를 mid + 1, 작으면 mid - 1로 설정해주면 된다.
package Solve005;
import java.io.*;
import java.util.*;
public class boj_1920 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
public static void main(String[] args) throws IOException{
int n = Integer.parseInt(br.readLine());
int nArr[] = new int[n];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < n; i++) {
nArr[i] = Integer.parseInt(st.nextToken());
}
int m = Integer.parseInt(br.readLine());
int mArr[] = new int[m];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < m; i++) {
mArr[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < mArr.length; i++) {
System.out.println(solution(nArr, mArr[i]));
}
}
static int solution(int[] nArr, int x) {
if (nArr[0] > x || nArr[nArr.length - 1] < x) {
return 0;
}
int first = 0;
int mid = 0;
int last = nArr.length - 1;
while (first <= last) {
mid = (first + last) / 2;
if (nArr[mid] == x) {
return 1;
}
else if (nArr[mid] < x) {
first = mid + 1;
}
else if (nArr[mid] > x) {
last = mid - 1;
}
}
return 0;
}
}문제번호: 1039(교환)
풀이
완전탐색을 이용해서 풀이했다.
except: n이 10이하면 바꿀 수 없고 또 n이 100보다 작으면서 10의 배수라면 바꿔봤자 앞에 0이 나오므로 예외 처리한다.
swap: 문자열을 StringBuilder에 저장해서 새로 생성한 다음 단순히 바꿔준다. 그 다음 바꾼 StringBuilder의 첫 인덱스에 0이 오면 해당 값은 버리고, 0이 아니면 다음 nextQu에 집어넣는다.
K번을 바꿔야 하므로 K번을 반복하며 각 회수가 지나갈때 qu에 넣을 것을 기억하기 위해 nextQu를 생성한다. 여기서 모든 swap된 값을 다 넣는다면 어마어마한 시간이 걸리므로 contain메서드를 사용해서 이미 nextQu값에 중복된 값이 들어가 있다면 pass한다.
package Solve005;
import java.io.*;
import java.util.*;
public class boj_1039 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static List<Integer> nextQu = new ArrayList<>();
static Queue<Integer> qu = new LinkedList<>();
static int swap(int n, int x, int y) {
StringBuilder nTemp = new StringBuilder(Integer.toString(n));
char temp = nTemp.charAt(x);
nTemp.setCharAt(x, nTemp.charAt(y));
nTemp.setCharAt(y, temp);
if (nTemp.charAt(0) == '0') {
return 0;
}
return Integer.parseInt(nTemp.toString());
}
static boolean except(StringBuilder n) {
int num = Integer.parseInt(n.toString());
if (num < 10) {
return true;
}
if (num < 100 && num % 10 == 0) {
return true;
}
return false;
}
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine(), " ");
StringBuilder n = new StringBuilder(st.nextToken());
int k = Integer.parseInt(st.nextToken());
if (except(n)) {
System.out.println(-1);
return;
}
qu.add(Integer.parseInt(n.toString()));
for (int i = 0; i < k; i ++) {
while (!qu.isEmpty()) {
int cur = qu.poll();
for (int x = 0; x < n.length() - 1; x++) {
for (int y = x + 1; y < n.length(); y++) {
int num = swap(cur, x, y);
if (num == 0) {
continue;
}
if (!nextQu.contains(num)) {
nextQu.add(num);
}
}
}
}
for (int j = 0; j < nextQu.size(); j++) {
qu.add(nextQu.get(j));
}
nextQu.clear();
}
int max = Integer.MIN_VALUE;
while (!qu.isEmpty()) {
int cur = qu.poll();
if (cur > max) {
max = cur;
}
}
System.out.println(max);
}
}문제번호: 1713(후보 추천하기)
풀이
frame 리스트, 각 후보의 번호를 index로 해서 추천받은 횟수를 나타내는 cnt배열을 이용한다.
리스트에 빨리 넣은 것일수록 오래된 것임을 이용하고 cnt를 돌면서 최소 추천횟수를 찾아서 pivot으로 사용한다. 최소 횟수를 찾았으면 frame 리스트를 처음부터 탐색하면서 frame 리스트에 들어있는 값을 인덱스로 사용하여 추천받은 횟수와 최소 횟수가 같다면 해당 번호를 지워버리고 cnt는 0으로 만든다.( 리스트는 왼쪽에 있을수록 오래전에 넣은것이기 때문에)
package Solve005;
import java.io.*;
import java.util.*;
public class boj_1713 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static List<Integer> frame = new ArrayList<>();
static int[] cnt = new int[101];
public static void main(String[] args) throws IOException {
int frameCnt = Integer.parseInt(br.readLine());
int recommend = Integer.parseInt(br.readLine());
int[] num = new int[recommend];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < recommend; i++) {
num[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < recommend; i++) {
if (frameCnt == 0) {
if (frame.contains(num[i])) {
cnt[num[i]]++;
continue;
}
// 가장 추천 적은 거 값 뽑기
int min = Integer.MAX_VALUE;
for (int j = 0; j < cnt.length; j++) {
if (cnt[j] != 0 && min > cnt[j]) {
min = cnt[j];
}
}
for (int j = 0; j < frame.size(); j++) {
if (cnt[frame.get(j)] == min) {
cnt[frame.get(j)] = 0;
frame.remove(j);
frame.add(num[i]);
cnt[num[i]]++;
break;
}
}
}
else {
if (!frame.contains(num[i])) {
frame.add(num[i]);
cnt[num[i]]++;
frameCnt--;
}
else {
cnt[num[i]]++;
}
}
}
Collections.sort(frame);
StringBuilder answer = new StringBuilder();
for (int i = 0; i < frame.size(); i++) {
answer.append(frame.get(i) + " ");
}
System.out.println(answer);
}
}문제번호: 1062(가르침)
풀이
백트래킹을 이용해서 풀자.
알파벳 26개중에 K개 만큼 선택을 한 다음, 단어들을 탐색하면서 해당 단어를 읽을 수 있는지, 없는지 판단한다.
백트래킹할때마다 단어의 개수를 세서 max값 보다 크게 되면 갱신해준다.
package Solve005;
import java.io.*;
import java.util.*;
public class boj_1062 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static List<String> word;
static boolean[] alpha = new boolean[26];
static int cnt = 0;
static int max = 0;
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
word = new ArrayList<>();
alpha['a' - 97] = true;
alpha['n' - 97] = true;
alpha['t' - 97] = true;
alpha['i' - 97] = true;
alpha['c' - 97] = true;
for (int i = 0; i < n; i++) {
String input = br.readLine();
word.add(input.substring(4, input.length() - 4));
}
if (k < 5) {
System.out.println(0);
}
else {
bt(0, 0, k - 5);
System.out.println(max);
}
return;
}
static void bt(int start, int wordCnt, int end) {
cnt = 0;
if (wordCnt == end) {
for (int i = 0; i < word.size(); i++) {
boolean isIn = false;
String x = word.get(i);
for (int j = 0; j < x.length(); j++) {
char y = x.charAt(j);
if (alpha[y - 97]) {
continue;
}
else {
isIn = true;
break;
}
}
if (!isIn) {
cnt++;
}
}
if (max < cnt) {
max = cnt;
}
return;
}
else {
for (int i = start; i < 26; i++) {
if (!alpha[i]) {
alpha[i] = true;
bt(i, wordCnt + 1, end);
alpha[i] = false;
}
}
}
}
}
문제번호: 3055(탈출)
풀이
BFS를 이용하자.
먼저 물이 있는 곳과 두더지의 현재 위치를 각각 waterqu, ddgqu에 담고 두더지는 물이 있는 곳에 갈 수 없기 때문에 BFS를 돌릴 때, 물을 먼저 퍼뜨리고 그 다음에 두더지를 퍼뜨린다. (시간초과로 인해 방문한 곳은 방문하지 않도록 해야한다.)
또 각각 한번씩 번갈아가면서 퍼뜨려야 하므로 현재 waterqu, ddgqu에 들어있는 값만큼만 while문을 돌린다.
두더지가 비버의 굴에 도달하지 못했는데 ddgqu에 들어있는 값이 없다면 이제 두더지는 이동할 곳이 없다는 뜻이므로 끝낸다.
package Solve005;
import java.io.*;
import java.util.*;
public class boj_3055 {
static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static List<Integer>[] cnt;
static List<Boolean>[] visited;
static int[] dx = {0, 0, -1, 1};
static int[] dy = {1, -1, 0, 0};
static Queue<point> waterQu = new LinkedList<>();
static Queue<point> ddgQu = new LinkedList<>();
public static void main(String[] args) throws IOException {
st = new StringTokenizer(sc.readLine(), " ");
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int obX = 0;
int obY = 0;
cnt = new ArrayList[r];
visited = new ArrayList[r];
for (int i = 0; i < r; i++) {
cnt[i] = new ArrayList<>();
visited[i] = new ArrayList<>();
for (int j = 0; j < c; j++) {
cnt[i].add(0);
visited[i].add(false);
}
}
for (int i = 0; i < r; i++) {
String s = sc.readLine();
for (int j = 0; j < c; j++) {
if (s.charAt(j) == '*') {
visited[i].set(j, true);
waterQu.offer(new point(i, j));
}
if (s.charAt(j) == 'S') {
cnt[i].set(j, 1);
ddgQu.offer(new point(i, j));
}
if (s.charAt(j) == 'D') {
obX = i;
obY = j;
}
if (s.charAt(j) == 'X') {
cnt[i].set(j, -2);
}
}
}
bfs(r, c, obX, obY);
}
static void bfs(int r, int c, int obX, int obY) {
while (true) {
int wqSize = waterQu.size();
while (wqSize != 0) {
point p = waterQu.poll();
for (int i = 0; i < 4; i++) {
int x = p.x + dx[i];
int y = p.y + dy[i];
if (0 <= x && x < cnt.length && 0 <= y && y < cnt[0].size()) {
if (x == obX && y == obY || visited[x].get(y)) {
continue;
}
if (cnt[x].get(y) != -2) {
visited[x].set(y, true);
waterQu.offer(new point(x, y));
}
}
}
wqSize--;
}
int dqSize = ddgQu.size();
while (dqSize != 0) {
point ddg = ddgQu.poll();
for (int i = 0; i < 4; i++) {
int x = ddg.x + dx[i];
int y = ddg.y + dy[i];
if (0 <= x && x < cnt.length && 0 <= y && y < cnt[0].size()) {
if (visited[x].get(y) || cnt[x].get(y) != 0)
continue;
if (x == obX && y == obY) {
System.out.println(cnt[ddg.x].get(ddg.y));
return;
}
cnt[x].set(y, cnt[ddg.x].get(ddg.y) + 1);
ddgQu.offer(new point(x, y));
}
}
dqSize--;
}
if (ddgQu.isEmpty()) {
System.out.println("KAKTUS");
return;
}
}
}
}
class point {
int x;
int y;
public point (int x, int y) {
this.x = x;
this.y = y;
}
}문제번호: 프로그래머스-디스크 컨트롤러
풀이
먼저 들어오는 시간을 기준으로 오름차순으로 정렬 후에, 같다면 weight가 작은 순서대로 정렬을 또한다. (이렇게 처리를 해야 가장 최소시간을 들여 task들을 처리할 수 있다.)
그러면 이제 timer를 0부터 돌면서 현재 timer와 시작 시간이 같은 요소들을 모두 qu에 넣어주며 qu는 시작 시간과 관계없이 weight가 작은 것부터 처리하도록 정렬 시킨다.
스케쥴러 block변수를 통해 현재 스케쥴러가 처리하고 있는 task가 있는지 확인을 하고 없으면 qu에서 하나빼서 처리한다.(현재 timer보다 시작시간이 더 앞이라면 그 시간만큼 기다리고 있던 task므로 해당 딜레이의 값을 더해준다.)
timer가 증가할때마다 block을 1빼주면서 다음 task를 처리할 수 있도록 설정한다.
package Solve005;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
public class 디스크_컨트롤러 {
public static void main(String[] args) {
int[][] jobs = {{24, 10}, {28, 39}, {43, 20}, {37, 5}, {47, 22}, {20, 47}, {15, 34}, {15, 2}, {35, 43},{ 26, 1}};
PriorityQueue<task> qu = new PriorityQueue<>();
Arrays.sort(jobs, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[0] < o2[0]) {
return -1;
}
else if (o1[0] == o2[0]) {
if (o1[1] < o2[1]) {
return -1;
}
}
return 0;
}
});
// delay는 task가 들어오고 대기하는 시간
// timer는 현재 진행중인 시간
// jobCnt는 전체 task 갯수
// block은 현재 처리중인 task의 weight;
// cnt는 각 task의 weigh합
int delay = 0;
int timer = 0;
int jobCnt = jobs.length;
int block = 0;
int cnt = 0;
// timer가 0부터 돌면서 시작 시간이 timer와 같으면 qu에 넣는다.
while (true) {
for (int[] job : jobs) {
if (timer == job[0]) {
qu.offer(new task(job[1], job[0]));
jobCnt--;
} else if (jobCnt == 0)
break;
}
// 현재 처리중인 task가 없는데 qu에 무언가가 있다면 실행
while (block == 0 && !qu.isEmpty()) {
task x = qu.poll();
// 현재 timer보다 task시작시간이 작다면 대기시간이므로 delay에 더해줌
if (timer > x.start) {
delay += (timer - x.start);
}
// cnt는 현재 처리중인 task의 weight를 더해주고 block에 해당 weight를 더해주면 block이 0이 되기전까진 다른 task 처리안됨
cnt += x.weight;
block = x.weight;
}
// 처리하는 것도 없고 job의 개수도 0이고 qu를 다 비우고 처리를 완료했다면
if (block == 0 && jobCnt == 0 && qu.isEmpty()) {
break;
}
// 순회마다 증가
timer++;
// block이 0이 아니면 task를 처리중이므로 하나씩 뺴줌줌
if (block != 0) {
block--;
}
}
System.out.println(Math.round(cnt + delay) / jobs.length);
}
}
class task implements Comparable<task> {
int weight;
int start;
public task(int weight, int start) {
this.weight = weight;
this.start = start;
}
@Override
public int compareTo(task task) {
if (this.weight > task.weight)
return 1;
else
return -1;
}
}Author And Source
이 문제에 관하여(Solve005), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sksk713/Solve005저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
