처음 접해보는 구조의 문제였고 효율성 테스트까지 상당히 어려웠다.. 프로그래머스 가사 검색 코딩테스트 연습 - 가사 검색 programmers.co.kr 문제는 노래 가사에 사용된 단어들 중, 특정 키워드가 포함된 문자가 몇 개 있는지 찾아내는 문제였다. 여기서 쿼리가 주어지고 그 쿼리에 맞는 단어가 몇개 있는지 찾아내는 것이다. 여기서 쿼리에서는 젤 앞이나 뒤에 "?"라는 문자가 포함될 수 있다. "?"의 개수는 자유롭다. 단, 가운데에 "?"가 포함되는 경우는 없고 앞 뒤에 전부 포함되는 경우도 없다. 그렇다면, 쿼리가 주어지고 각 쿼리당 일치하는 가사가 몇 개나 있는지 찾는 문제였다. 가장 처음에 생각했던 방식은 단순하게 O(n^3)으로 풀 수 있는 방식이었다. 그냥 모든 쿼리마다 단어들을 하나씩 ..

효율성 테스트까지 있는 문제로 처음 DP로 풀어야겠다고 생각하고 풀이를 시작하였다. 프로그래머스 점프와 순간 이동 코딩테스트 연습 - 점프와 순간 이동 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈 programmers.co.kr 문제는 N칸을 이동해야한다. 그러나 조건이 있다. (현재까지 온 거리) * 2에 해당하는 위치로 순간이동이 가능하고 이 경우에는 건전지의 소비량이 들지 않는다. 그러나 K칸을 이동하게 되면 이 경우에는 K 만큼의 건전지가 소비된다. 그러므로 순간이동을 하는 것이 효율적이다. 여기서 N칸을 이동하려고 할 때, 가장 건전지의 사용..

우선 순위 큐(Priority Queue) 자료구조를 기억하고 있으면 쉽게 풀 수 있는 문제였다. 프로그래머스 더 맵게 문제 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 문제는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶어한다. 모든 음식의 스코빌 지수를 K이상으로 만들기 위해서는 스코빌 지수가 가장 낮은 두 개의 음식을 특별한 방법으로 섞어서 새롭게 만들 수 있다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) 이..

백준 10844번 동적 계획법(Dynamic Programming)으로 풀 수 있는 문제이다. 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제는, 45656이란 수가 있다. 이 수를 잘보면 각 자리수마다 1씩 차이나는 것을 알 수 있다. 이런 수를 계단 수라고 한다. 그렇다면 길이가 N개인 계단 수는 몇 개가 나올 수 있는지 구하는 것이 문제이다. 단, 마지막 정답에 1,000,000,000으로 나눈 나머지를 출력한다. 이 문제를 풀면서 주의해야할 점은 0으로 시작하는 숫자는 없다는 것이다. 즉, 0~9까지의 각 자리수가 있지만 첫 자리에는 0이 절대 올 수 없다는 것이다. 그렇다면 DP로 풀기 위해 먼저 첫 자리 수 ..

백준 11053번 동적 계획법(Dynamic Programming)으로 풀 수 있는 문제이다. 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제는, 수열 A에서 이를 어떻게하면 가장 긴 부분 수열로 나열할 수 있고, 이의 길이를 출력으로 보여주는 문제이다. 처음 문제의 풀이 과정을 생각할 때, 너무 단순하게 생각했다. 왜 이 문제를 DP을 이용해서 풀어야하는지 몰라서 소팅을 실행하고 중복된 숫자만 제거해서 최종적으로 남은 숫자의 ..

SWIFT로 Hash 문제에 대해서는 풀어봤었습니다. 하지만 Java로는 Hash 자료구조 문제를 풀어본 적이 없어서 프로그래머스의 문제를 풀어보았습니다. 프로그래머스 위장 문제 코딩테스트 연습 - 위장 programmers.co.kr 문제는 스파이가 매일 다른 옷의 조합을 입어야 하는데, 처음 clothes 이차원 배열의 형태로 (옷의 종류, 옷의 이름)이 주어지고 이를 이용해서 만들 수 있는 조합의 수를 찾는 것입니다. 단, 스파이는 꼭 한 종류의 옷을 하나는 입어야합니다. 즉, 하나도 안 입는 경우는 존재하지 않습니다. Hash문제이기 때문에, 우선 문제를 해결하기 위해 (key, value)의 형태로 HashMap을 만들어야합니다. HashMap clothes_set = new HashMap();..