BOJ 2568번 전깃줄-2 문제 자바(java) 풀이 랭크 : 골드2 백준 2568번 전깃줄-2 문제 정리 교차하는 전깃줄을 없애서 전깃줄이 교차하지 않도록 하려고 한다. 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄 최소 개수 구하기 전깃줄의 개수는 최대 100,000개 이다. 문제 풀이 전깃줄의 상태를 왼쪽 기준 오름차순으로 나열하면 아래와 같습니다. A 전봇대: 1 2 3 4 6 7 9 10 B 전봇대: 8 2 9 1 4 6 7 10 어떻게 하면 제일 조금 자를 수 있을까 생각해보면 B 전봇대의 1,2,3번째 전깃줄을 자르면 3개로 제일 작게 자르는 경우가 됩니다. 왜나하면 왼쪽수는 이미 증가 상태이기 때문에 오른쪽도 오름차순 이면 전깃줄이 엉키지 않습니다. 즉 최장 증..

BOJ 6549번 히스토그램에서 가장 큰 직사각형 문제 자바(java) 풀이 랭크 : 골드1 백준 6549번 히스토그램에서 가장 큰 직사각형 문제 정리 히스토그램: 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형 각 직사각형을 같은 너비를 가지지만 높이가 다를 수 있다. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. 문제 풀이 우선 넓이를 어떻게 구해야 하는지 파악해야 합니다. 넓이는 구간에서 높이가 작은 직사각형에 depend 됩니다. 만약 1-3구간에서의 높이가 [3,1,2]라면 높이 1이 가장 작기 때문에 이 구간에서의 넓이는 1x3(구간의 길이)=3이 됩니다. 이 방식을 이용해서 1-1, 1-2, 1-3, ... 1-n 2-1, 2-2, 2-3, ... 2-n ... n..

BOJ 2565번 전깃줄 문제 자바(java) 풀이 랭크 : 실버1 백준 2565번 전깃줄 문제 정리 교차하는 전깃줄을 없애서 전깃줄이 교차하지 않도록 하려고 한다. 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄 최소 개수 구하기 전깃줄의 개수는 최대 100개 이다. 문제 풀이 전깃줄의 상태를 왼쪽 기준 오름차순으로 나열하면 아래와 같습니다. A 전봇대: 1 2 3 4 6 7 9 10 B 전봇대: 8 2 9 1 4 6 7 10 어떻게 하면 제일 조금 자를 수 있을까 생각해보면 B 전봇대의 1,2,3번째 전깃줄을 자르면 3개로 제일 작게 자르는 경우가 됩니다. 왜나하면 왼쪽수는 이미 증가 상태이기 때문에 오른쪽도 오름차순 이면 전깃줄이 엉키지 않습니다. 즉 최장 증가 수열(Lon..

BOJ 1561번 놀이공원 자바(java) 풀이 난이도: 골드2 BOJ 1561번 놀이공원 문제정리 놀이공원에는 총 M개의 1인승 놀이기구가 있다. 기구에는 1~N까지 번호가 매겨져 있다. 모든 놀이기구에는 운행시간이 정해져 있어, 시간이 지나면 내려야 한다. 놀이기구가 비어있으면 가장 앞에 서 있는 아이가 탑승한다. 여러 놀이기구가 비어있다면 더 적은 번호의 놀이기구를 탑승한다. 줄의 마지막 아이가 타게 되는 놀이기구 번호를 구하여라! 문제 풀이 이 문제는 대충 입력의 크기만 봐도 시뮬레이션으로 구현할 수 없습니다. 이는 x분에 몇명의 아이들까지 놀이기구를 타는지 계산하여 문제를 해결하여야 합니다. 마지막 사람이 타기전 시간이 몇분인지 이분탐색을 통해 알아내고 그 시간까지 몇명의 사람이 탔는지 계산합니..

BOJ 5430번 AC 문제 자바(java) 풀이 랭크 : 실버2 백준 5430번 AC 문제 정리 AC에는 정수 배열을 위한 두 가지 함수가 있다. R(뒤집기) : 배열에 있는 숫자 순서를 뒤집는다. D(버리기) : 첫 번째 숫자를 버린다. RDD 처럼 함수를 바로 이어서 사용할 수 있다. 한 번 뒤집은 다음 두개의 숫자를 버린다. 함수 실행 후, 최종 결과를 구하여라 문제 풀이 수를 실제로 뒤집고 반복한다면 시간초과가 나게 될것입니다. 그러므로 deque를 이용하여 앞 뒤에서 숫자를 지워줍니다. 파싱하는 것이 중요합니다. 숫자는 한자리수가 아니라 최대 100,000임을 인지해야 합니다. 이것 때문에 런타임 에러를 많이 봤습니다..ㅠㅠ 배열에 주어진 수가 하나도 없을때 함수에 D가 포함되어 있다면 에러를..

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..