본문 바로가기

프로그래머스24

[파이썬] 프로그래머스 - 과일 장수 (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 필요 알고리즘 개념 수학(?) 일단 등차수열과 등비수열이 뭔지는 알아야 풀 수 있다. 구현 주어진 대로 구현해주면 된다. 항상 입력은 등차수열 혹은 등비수열임이 보장된다. 또한 common의 길이는 3이상이므로 판단이 불가능한 경우도 없다. 1. 등차수열인지 아닌지(아니라면 문제 조건에 따라서 무조건 등비수열) 판단한다. 2. 등차수열이라면 공차를, 등비수열이라면 공비를 구한 후 common의 마지막 값에 공차를 더해주거나, 공비를 곱해준다. 코드 : github /** * 문제 출처: 프로그래머스 코딩 테스트 연습, https://pro.. 2022. 11. 25.
[자바] 프로그래머스 - 종이 자르기 (Lv0, Java) 문제 : Programmers-종이 자르기 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 개념 수학 수학문제긴한데, 몇 개 공책에 그려보다보면 규칙성은 어렵지 않게 찾을 수 있을 것 같다. '종이를 겹쳐서 자를 수 없습니다.' 부분이 가장 중요한 조건이다. 이게 가능했다면 그리디 알고리즘쪽으로 갔을텐데, 겹쳐서 자를 수 없다고 했으므로 규칙성을 찾아봐야 한다. 아무튼 겹쳐서 자를 수 없으니 결국은 한땀한땀 자를 수 밖에 없다. 아래와 같이 4x3 짜리 종이를 생각해보자. 이걸 우선 가로방향으로 n개로 쪼개보자. 이 경우 n-1번 쪼개면 된다. 그리고 그 중 한 개만 세로방향으로 쪼개보자. m-1번 쪼개면 된다. 그런.. 2022. 10. 19.
[자바] 프로그래머스 - 쿠키 구입 (Lv4, Java) 문제 : Programmers-쿠키 구입 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 개념 두 포인터 (투 포인터) 투 포인터 알고리즘을 알고 있다면 어렵지 않게 풀어볼 수 있다. 일반적으로 문제를 좀 더 단순화해서 생각해보면 풀이를 생각하기 쉬운 경우가 많다. 한번 m이 고정이라고 생각해보고 어떻게 풀지 생각해보자. 그렇다면 l과 r을 적절히 조정해서 l~m의 합과 m+1~r 까지의 합을 동일하게 만드는 문제가 된다. 그리고 입력값으로 0 또는 음수가 주어지지 않으므로 단순히 l~m의 합이 m+1~r의 합보다 작다면 l을 줄이고, 그 반대라면 r을 늘려주기만 하면 된다. 즉 l과 r 두개의 포인터가 있는 투 포인.. 2022. 10. 14.
[자바] 프로그래머스 - n^2 배열 자르기 (Lv2, Java) 문제 : Programmers-n^2 배열 자르기 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 개념 구현, 수학 태그가 상당히 애매하긴한데, 그냥 단순 구현문제인 것 같다. 1. 문제에서는 2차원 배열을 만들고나서 1차원배열로 만들고, left부터 right까지를 출력하라고 했으나, 애초에 n의 최대값이 10^7이므로 2차원 배열을 만드는 순간 물리적으로 O(10^14)가 필요해서 무조건 시간초과이다. (대강 O(10^9)을 1초로 잡으면 되므로 10만초임) 2. 마찬가지로, 1차원 배열로 바꾸는것도 O(10^14)이므로 하면 안됨. 3. 그럼 남은건 left부터 right까지에 대해 right - left < 1.. 2022. 10. 14.
[자바] 프로그래머스 - 호텔 방 배정 (Lv4, Java) 문제 : Programmers-호텔 방 배정 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 개념 해시를 사용한 집합과 맵 자바의 HashMap을 적절하게 사용할 줄 알아야 한다. 근데 이렇게 알고리즘 분류만 봐서는 아마 풀이를 생각하긴 힘들 것 같다. 구현 난이도보다는 아이디어가 필요한 문제이다. 그룹 관련된 개념(유니온 파인드 등)이 있다면 좀 더 쉽게 생각해낼 수 있어보인다. 생각 과정 (오답) * 제가 풀이를 생각하는 과정이고 오답노트처럼 적어놓은 것이므로, 이하 생각 과정에 나온 알고리즘을 모두 몰라도 문제 푸는데 지장 없습니다. 그냥 바로 풀이만 보시려면 아래쪽에 '풀이'로 넘어가시면 됩니다. 아직 선택되지.. 2022. 10. 13.
[자바, JS] 프로그래머스 - 영어 끝말잇기 (Lv2, Java, JavaScript) 문제 : Programmers-영어 끝말잇기 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 개념 Set 해시셋을 사용해 이전에 나온 문자열이 중복으로 나왔는지 확인할 수 있어야 한다. 문자열, 파싱 문자열의 첫 문자와 마지막 문자를 확인할 수 있어야 한다. 문제에서 찾고자 하는 종료 조건은 아래의 두 가지 이다. 1. 이전에 나온 단어가 다시 나오는지 2. 직전에 나온 단어의 마지막 문자(character)가 이번에 보고 있는 단어의 첫번째 문자와 동일한지 '1'의 경우엔 Set을 사용해 중복 체크를 할 수 있다. 자바의 경우엔 HashSet을 사용하면 되고, js의 경우엔 Set을 사용해주면 된다. '2'의 경우엔.. 2022. 9. 23.

티스토리툴바