BOJ
-
BOJ 1561번 놀이공원 자바(java) 풀이 난이도: 골드2 BOJ 1561번 놀이공원 문제정리 놀이공원에는 총 M개의 1인승 놀이기구가 있다. 기구에는 1~N까지 번호가 매겨져 있다. 모든 놀이기구에는 운행시간이 정해져 있어, 시간이 지나면 내려야 한다. 놀이기구가 비어있으면 가장 앞에 서 있는 아이가 탑승한다. 여러 놀이기구가 비어있다면 더 적은 번호의 놀이기구를 탑승한다. 줄의 마지막 아이가 타게 되는 놀이기구 번호를 구하여라! 문제 풀이 이 문제는 대충 입력의 크기만 봐도 시뮬레이션으로 구현할 수 없습니다. 이는 x분에 몇명의 아이들까지 놀이기구를 타는지 계산하여 문제를 해결하여야 합니다. 마지막 사람이 타기전 시간이 몇분인지 이분탐색을 통해 알아내고 그 시간까지 몇명의 사람이 탔는지 계산합니..
[BOJ] 백준 1561번 놀이공원 자바(java) 풀이 (이분 탐색)BOJ 1561번 놀이공원 자바(java) 풀이 난이도: 골드2 BOJ 1561번 놀이공원 문제정리 놀이공원에는 총 M개의 1인승 놀이기구가 있다. 기구에는 1~N까지 번호가 매겨져 있다. 모든 놀이기구에는 운행시간이 정해져 있어, 시간이 지나면 내려야 한다. 놀이기구가 비어있으면 가장 앞에 서 있는 아이가 탑승한다. 여러 놀이기구가 비어있다면 더 적은 번호의 놀이기구를 탑승한다. 줄의 마지막 아이가 타게 되는 놀이기구 번호를 구하여라! 문제 풀이 이 문제는 대충 입력의 크기만 봐도 시뮬레이션으로 구현할 수 없습니다. 이는 x분에 몇명의 아이들까지 놀이기구를 타는지 계산하여 문제를 해결하여야 합니다. 마지막 사람이 타기전 시간이 몇분인지 이분탐색을 통해 알아내고 그 시간까지 몇명의 사람이 탔는지 계산합니..
2020.03.23 -
BOJ 5430번 AC 문제 자바(java) 풀이 랭크 : 실버2 백준 5430번 AC 문제 정리 AC에는 정수 배열을 위한 두 가지 함수가 있다. R(뒤집기) : 배열에 있는 숫자 순서를 뒤집는다. D(버리기) : 첫 번째 숫자를 버린다. RDD 처럼 함수를 바로 이어서 사용할 수 있다. 한 번 뒤집은 다음 두개의 숫자를 버린다. 함수 실행 후, 최종 결과를 구하여라 문제 풀이 수를 실제로 뒤집고 반복한다면 시간초과가 나게 될것입니다. 그러므로 deque를 이용하여 앞 뒤에서 숫자를 지워줍니다. 파싱하는 것이 중요합니다. 숫자는 한자리수가 아니라 최대 100,000임을 인지해야 합니다. 이것 때문에 런타임 에러를 많이 봤습니다..ㅠㅠ 배열에 주어진 수가 하나도 없을때 함수에 D가 포함되어 있다면 에러를..
[BOJ] 백준 5430번 AC 자바(java) 풀이BOJ 5430번 AC 문제 자바(java) 풀이 랭크 : 실버2 백준 5430번 AC 문제 정리 AC에는 정수 배열을 위한 두 가지 함수가 있다. R(뒤집기) : 배열에 있는 숫자 순서를 뒤집는다. D(버리기) : 첫 번째 숫자를 버린다. RDD 처럼 함수를 바로 이어서 사용할 수 있다. 한 번 뒤집은 다음 두개의 숫자를 버린다. 함수 실행 후, 최종 결과를 구하여라 문제 풀이 수를 실제로 뒤집고 반복한다면 시간초과가 나게 될것입니다. 그러므로 deque를 이용하여 앞 뒤에서 숫자를 지워줍니다. 파싱하는 것이 중요합니다. 숫자는 한자리수가 아니라 최대 100,000임을 인지해야 합니다. 이것 때문에 런타임 에러를 많이 봤습니다..ㅠㅠ 배열에 주어진 수가 하나도 없을때 함수에 D가 포함되어 있다면 에러를..
2020.03.23 -
BOJ 1874번 스택 수열 문제 자바(java) 풀이 랭크 : 실버3 풀이시간: 50분 메모리: 29832 KB 시간: 316 ms 백준 1874번 스택 수열 문제 정리 1부터 n까지의 수를 스택에 넣었다가 뽑으면서 주어진 수열을 만들어야 한다. 만들 수 있다면 push와 pop 연산 순서를 출력하고 만들 수 없다면 "NO"를 출력해라. 문제 풀이 처음에 문제 이해가 잘 안되서 헤맸었습니다. 예제 1번은 다음과 같이 동작합니다. 1. 1을 넣는다. (1) 2. 2를 넣는다. (1 2) 3. 3을 넣는다. (1 2 3) 4. 4를 넣는다. (1 2 3 4) 5. 수열의 첫번째 수 4가 stack의 맨 위의 수가 같으므로 pop한다. (1 2 3) 6. 다음 수 3이 stack의 맨 위의 수와 같으므로 p..
[BOJ] 백준 1874번 스택 수열 자바(java) 풀이BOJ 1874번 스택 수열 문제 자바(java) 풀이 랭크 : 실버3 풀이시간: 50분 메모리: 29832 KB 시간: 316 ms 백준 1874번 스택 수열 문제 정리 1부터 n까지의 수를 스택에 넣었다가 뽑으면서 주어진 수열을 만들어야 한다. 만들 수 있다면 push와 pop 연산 순서를 출력하고 만들 수 없다면 "NO"를 출력해라. 문제 풀이 처음에 문제 이해가 잘 안되서 헤맸었습니다. 예제 1번은 다음과 같이 동작합니다. 1. 1을 넣는다. (1) 2. 2를 넣는다. (1 2) 3. 3을 넣는다. (1 2 3) 4. 4를 넣는다. (1 2 3 4) 5. 수열의 첫번째 수 4가 stack의 맨 위의 수가 같으므로 pop한다. (1 2 3) 6. 다음 수 3이 stack의 맨 위의 수와 같으므로 p..
2020.03.20 -
BOJ 2517번 달리기 문제 자바(java) 풀이 랭크 : 플레티넘5 백준 2517번 달리기 문제 정리 자기보다 앞에 달리고 있는 선수들 중 평소 실력이 자기보다 좋은 선수를 앞지르는 것은 불가능하다. 평소 실력이 자기보다 좋지 않은 선수가 앞에 달리고 있다면 남은 거리 동안 앞지르는 것이 가능하다. 자신이 앞으로 얻을 수 있는 최선의 등수를 알 수 있다. 각 선수의 평소 실력이 주어진다.(클 수록 실력 上) 선수의 평소 실력이 앞에서 부터 주어질때 각 선수의 최선의 등수를 계산하여라. 문제 풀이 자신보다 앞에 있는 사람중 실력이 더 낮은 사람들의 수를 구하면 됩니다. 다음 두 가지 방법으로 풀 수 있습니다. merge sort 풀이 선수들의 실력과 index를 Num 객체아 담아 저장합니다. merg..
[BOJ] 백준 2517번 달리기 자바(java) 풀이 (merge sort 풀이, segment tree 풀이)BOJ 2517번 달리기 문제 자바(java) 풀이 랭크 : 플레티넘5 백준 2517번 달리기 문제 정리 자기보다 앞에 달리고 있는 선수들 중 평소 실력이 자기보다 좋은 선수를 앞지르는 것은 불가능하다. 평소 실력이 자기보다 좋지 않은 선수가 앞에 달리고 있다면 남은 거리 동안 앞지르는 것이 가능하다. 자신이 앞으로 얻을 수 있는 최선의 등수를 알 수 있다. 각 선수의 평소 실력이 주어진다.(클 수록 실력 上) 선수의 평소 실력이 앞에서 부터 주어질때 각 선수의 최선의 등수를 계산하여라. 문제 풀이 자신보다 앞에 있는 사람중 실력이 더 낮은 사람들의 수를 구하면 됩니다. 다음 두 가지 방법으로 풀 수 있습니다. merge sort 풀이 선수들의 실력과 index를 Num 객체아 담아 저장합니다. merg..
2020.03.19 -
BOJ 1158번 요세푸스 문제1 자바(java) 풀이 랭크 : 실버5 풀이시간: 5분 백준 1158번 요세푸스 문제1 문제 정리 1~N번까지 N명의 사람이 원 모양으로 앉아있다. k가 주어질때 k번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원에서 2번을 반복한다. N명의 사람이 모두 제거될 때까지 계속된다. 사람들이 제거 되는 순서를 출력해라. 문제 풀이 이 문제는 요세푸스 문제0번과 똑같이 제출해도 통과할 수 있습니다. 즉 naive하게 문제에서 주어진대로 구현하면 통과할 수 있습니다. 하지만 이 문제는 queue를 이용하여 작성해보았습니다. queue에서 뺄 필요 없이 ArrayList를 이용하면 뺏다 넣었다 하지 않기 때문에 더 빠르게 가능합니다. 1~N까지 queue에 모두..
[BOJ] 백준 1158번 요세푸스 문제 자바(java) 풀이(큐, 리스트)BOJ 1158번 요세푸스 문제1 자바(java) 풀이 랭크 : 실버5 풀이시간: 5분 백준 1158번 요세푸스 문제1 문제 정리 1~N번까지 N명의 사람이 원 모양으로 앉아있다. k가 주어질때 k번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원에서 2번을 반복한다. N명의 사람이 모두 제거될 때까지 계속된다. 사람들이 제거 되는 순서를 출력해라. 문제 풀이 이 문제는 요세푸스 문제0번과 똑같이 제출해도 통과할 수 있습니다. 즉 naive하게 문제에서 주어진대로 구현하면 통과할 수 있습니다. 하지만 이 문제는 queue를 이용하여 작성해보았습니다. queue에서 뺄 필요 없이 ArrayList를 이용하면 뺏다 넣었다 하지 않기 때문에 더 빠르게 가능합니다. 1~N까지 queue에 모두..
2020.03.16 -
BOJ 2164번 카드2 자바(java) 풀이 랭크 : 실버4 풀이시간: 40분 백준 2164번 카드2 문제 정리 N장의 카드가 주어지며 1~N까지의 번호를 갖는다. 1번 카드가 제일 위에, N번이 제일 뒤에 있다. 다음 동작을 카드가 한 장남을때 까지 반복한다. 제일 위에 있는 카드르 버린다. 그 다음 제일 위에 있는 카드를 제일 아래로 옮긴다. N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하여라. 문제 풀이 이 문제는 카드1의 연장선에 있는 문제입니다. 카드1을 먼저 풀어보세요!! 카드1 문제는 N이 최대 1000입니다. 하지만 카드2 문제는 N이 최대 500000입니다. 이만 주의하면 됩니다. 저는 카드1 문제를 ArrayList로 구현하였다가 카드2에 냈더니 '사간초과'가 ..
[BOJ] 2164번 카드2 자바(java) 풀이 (queue 또는 규칙찾기)BOJ 2164번 카드2 자바(java) 풀이 랭크 : 실버4 풀이시간: 40분 백준 2164번 카드2 문제 정리 N장의 카드가 주어지며 1~N까지의 번호를 갖는다. 1번 카드가 제일 위에, N번이 제일 뒤에 있다. 다음 동작을 카드가 한 장남을때 까지 반복한다. 제일 위에 있는 카드르 버린다. 그 다음 제일 위에 있는 카드를 제일 아래로 옮긴다. N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하여라. 문제 풀이 이 문제는 카드1의 연장선에 있는 문제입니다. 카드1을 먼저 풀어보세요!! 카드1 문제는 N이 최대 1000입니다. 하지만 카드2 문제는 N이 최대 500000입니다. 이만 주의하면 됩니다. 저는 카드1 문제를 ArrayList로 구현하였다가 카드2에 냈더니 '사간초과'가 ..
2020.03.15