본문 바로가기

PS/Programmers30

[자바] 프로그래머스 - 분수의 덧셈 (Lv0, Java) 목차 문제 : Programmers - 분수의 덧셈 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 구현, 수학 딱히 알고리즘을 필요로 하지 않는다. 분수의 덧셈 방법만 알면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 유클리드 호제법을 이용할수도 있겠으나, 굳이 최대 분자 분모가 1000인 상황에서 쓸 필요는 없다. 그냥 단순 .. 2024. 3. 29.
[자바] 프로그래머스 - 석유 시추 ([PCCP 기출문제] 2번) (Lv2, Java) 목차 문제 : Programmers - [PCCP 기출문제] 2번 / 석유 시추 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 탐색 (BFS, DFS 등) 약간의 아이디어만 있다면 탐색 알고리즘으로 풀 수 있다. 풀이 우리가 알아야 하는건, 각 열 번호에서 접근 가능한 석유들의 합이다. cnt[X] 라는 배열을 정의해보자. 이건 X 인덱스 열에서 접근 가능한 석유들의 총 합을 뜻한다. 최종적으로 cnt[0] 부터 cnt[m-1] 까지의 값 중 가장 큰 값을 출력하면 될 것이다. 예를들어 아래와 같이 표현될 것이다. 최종적으로 cnt 배열에서 가장 큰 값이 9 이므로 9가 답이다. --- 그럼 이제 cnt[] 에 값을.. 2024. 1. 22.
[자바] 프로그래머스 - 수열과 구간 쿼리 2 (Lv0, Java) 목차 문제 : Programmers - 수열과 구간 쿼리 2 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 구현 문제에서 제시된 대로 구현해주면 됩니다. 풀이 arr[s], arr[s+1], ... , arr[e-1], arr[e] 중 k보다 큰 값들 중 가장 작은 값을 찾는 문제이다. 문제만 잘 이해했다면 반복문을 잘 사용해서 풀 수 있다. k보다 큰 값 중 '가장 작은 값'이 문제일 수 있는데, 애초에 나올 수 있는 수치보다 큰 값을 무한대로 정하고 그 값을 갱신하면서 진행하면 편하다. 이 문제의 경우 0 ≤ arr의 원소 ≤ 1,000,000 이므로 1000001 이상으로 잡으면 된다. 아니면 그냥 Intege.. 2023. 6. 16.
[자바] 프로그래머스 - 수열과 구간 쿼리 4 (Lv0, Java) 목차 문제 : Programmers - 수열과 구간 쿼리 4 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 구현 문제에서 제시된 대로 구현해주면 됩니다. 풀이 문제에서 제시된대로 구현해주면 된다. 별다른 알고리즘 없이 그냥 배열순회만 사용해 풀어도, 총 1000개의 쿼리에 대해 각 O(arr의 길이)만큼 필요하므로, O(1000^2)으로 풀 수 있다. 예를들어 [2, 2, 4, 5, 4]가 query [0, 3, 3]을 통해 [3, 2, 4, 6, 4]로 바뀌는 과정은 아래와 같다. 이하 코드는 약간 효율성을 더하기 위해 인덱스 s부터 e까지 모두 순회하지 않고, 1. s이상이면서 k의 배수인 가장 작은 수를 우선 .. 2023. 5. 10.
[파이썬] 프로그래머스 - 과일 장수 (Lv1, Python) 문제 : Programmers-과일 장수 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 개념 정렬, 그리디 그리디로 접근해서 풀 수 있다. 그리디 접근을 위해 정렬이 필요하다. 풀이 사과의 개수가 n개라고 해보자. 그렇다면 n%m 개 만큼은 버려져야 한다. 이 때 버려져야 하는 사과는 당연히 점수가 가장 낮은 사과들이다. 또한 이 문제는 m개씩 담은 상자에서 가장 점수가 낮은 사과를 기준으로 가격이 정해진다. 이 때 m개씩 짝지었을 때 낮은 사과가 가장 높게 나오는 방법은 내림차순으로 정렬 후 m개씩 고르는 방법이다(그리디). 위의 두 가지 모두 내림차순으로 정렬 후, m개씩 짝짓고 남는건 버리는 규칙에 부합한다. .. 2023. 2. 6.
[자바] 프로그래머스 - 스킬트리 (Lv2, Java) 문제 : Programmers-스킬트리 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 개념 구현, 문자열 문자열을 활용해 문제에서 제시된대로 구현하는 문제이다. 풀이 1 - 쉽게 생각해볼만한 방법! 우선 가장 쉽게 생각해볼 수 있는 방법은, skill_trees[]의 각 문자열에서 skill에 들어있는 문자열을 제외한 나머지를 모두 제거하는 방식이다. 예를들어 '입출력 예'의 경우 다음과 같이 변환한다. (skill = CBD) "BACDE" -> "BCD" "CBADF" -> "CBD" "AECB" -> "CB" "BDA" -> "BD" 그렇게되면 skill이라는 문자열에서 앞에서부터 변환한 문자열이 나온다면 가능.. 2023. 2. 3.
[자바] 프로그래머스 - 올바른 괄호 (Lv2, Java) 문제 : Programmers-올바른 괄호 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 개념 구현 보통 스택으로 설명할 것 같이 생겼는데 어차피 스택을 통한 풀이에서 넣을게 한 종류 뿐이라 딱히 필요없다. 규칙성만 잘 찾아서 구현해주면 된다. 풀이 '('를 +1, ')'를 -1이라고 생각해보자. "()()"은 anwer이 true였고. 0에서 시작해서 1, 0, 1, 0 이 된다. "(())()"은 true였고, 1, 2, 1, 0, 1, 0이 된다. ")()("은 false였고, -1, 0, -1, 0이다. "(()("은 false였고, 1, 2, 1, 2 이다. answer이 true가 되는 조건은 그럼 다음과.. 2023. 1. 29.
[자바] 프로그래머스 - 겹치는 선분의 길이 (Lv0, Java) 문제 : Programmers-겹치는 선분의 길이 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 개념 구현 if문을 통해 세 선분을 비교해도 풀 수 있으나, 아이디어만 잘 세우면 그냥 배열에 카운팅만 해서 구현해주면 된다. 풀이 선분의 수치는 -100~100 이다. 수치를 +100씩 해준다면 0~200 범위가 된다. 따라서 배열에 해당 선분이 차지하는 범위만큼 카운팅을 해줄 수 있다. 예를들어 아래와 같이 카운팅을 해줄 경우, 배열의 수치가 2 또는 3인 부분이 '두 개 이상의 선분이 겹치는 부분'이다. 주의점은 그냥 [a, b] 범위에 대해 카운팅하는건 점에 대한 카운팅이다. 이 문제에서는 겹치는 면을 찾아야하므로.. 2022. 12. 7.
[자바] 프로그래머스 - 순서쌍의 개수 (Lv0, Java) 문제 : Programmers-순서쌍의 개수 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 개념 브루트포스 n의 크기가 100만밖에 안되므로 그냥 1부터 n까지의 모든 수를 비교해보면 된다. O(n) 수학 (정수론) 좀 더 효율적으로 O(sqrt(n))으로도 풀 수 있다. 이 경우 수학적 지식이 좀 필요하다. 풀이 우선 n의 크기가 100만으로 매우 작으므로 그냥 1부터 n까지의 모든 수를 보면 된다. a를 1부터 n까지 증가시키면서, n%a == 0 이라면 b = n/a 가 되므로 answer을 1 증가시켜주면 된다. 이 경우 O(n)이 걸린다. int answer = 0; for (int i = 1; i 2022. 12. 2.
[자바] 프로그래머스 - 다음에 올 숫자 (Lv0, Java) 문제 : Programmers-다음에 올 숫자 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 개념 수학(?) 일단 등차수열과 등비수열이 뭔지는 알아야 풀 수 있다. 구현 주어진 대로 구현해주면 된다. 항상 입력은 등차수열 혹은 등비수열임이 보장된다. 또한 common의 길이는 3이상이므로 판단이 불가능한 경우도 없다. 1. 등차수열인지 아닌지(아니라면 문제 조건에 따라서 무조건 등비수열) 판단한다. 2. 등차수열이라면 공차를, 등비수열이라면 공비를 구한 후 common의 마지막 값에 공차를 더해주거나, 공비를 곱해준다. 코드 : github /** * 문제 출처: 프로그래머스 코딩 테스트 연습, https://pro.. 2022. 11. 25.