프로그래머스 알고리즘 - 더 맵게 ☞ 프로그래머스 '더 맵게' 문제링크 음식 중에 가장 덜 매운 2가지의 음식을 반복적으로 선택해야 합니다. 우선순위 큐(Priority Queue)를 사용하면 가장 덜 매운 2가지 음식을 찾기 편합니다. 우선순위 큐에 대한 내용은 이전 포스팅에 있습니다. ☞ 우선순위 큐 - Java에서 다루기 풀이코드 (java) class Solution { public int solution(int[] scoville, int K) { int answer = 0; PriorityQueue priorityQueue = new PriorityQueue(); //우선순위 큐에 음식 담아주기 for (int i : scoville) { priorityQueue.add(i); } //가장 덜..
Forbidden Zero ☞ 문제 링크 입력받은 정수의 다음 숫자를 구하면 됩니다. 다만 숫자 중에 0이 포함되어 있으면 안됩니다. 예를들어 9의 다음 숫자는 0을 포함한 10이 아닌 11이 되어야 하고, 99의 다음 숫자는 100이 아닌 111이 되어야 합니다. 입력 값에 1을 더한 숫자를 구하고, 그 숫자의 0이 있으면 그 0을 1로 바꿔주는 방식으로 0이 없는 다음 숫자를 구할 수 있습니다. 저는 숫자를 char로 바꾸고, char를 하나씩 비교해가며 0인 char를 1로 바꿔주는 방법을 선택 했습니다. 반환할때는 다시 정수로 변환합니다. 풀이코드 (java) public class Main { public static void main(String[] args) { Scanner sc = new..
프로그래머스 알고리즘 - 베스트 앨범☞ 프로그래머스 베스트 앨범 문제 링크 문제 설명과 제한사항을 빠짐없이 이해해야 실수 없이 코딩이 가능합니다. 장르(genre)를 먼저 나열 하는데 이에 기준이 장르의 속한 모든 노래들의 재생횟수(plays)입니다. 그러나 장르 내에서 노래를 정렬 할 때는, 많이 재생된 최상위 노래를 최대 2개까지 보여줍니다. 함정에 빠질 수도 있는 것이 최대2개입니다. 1개만 있을 경우 1개만 나와야하며, 노래들은 이름 없이 인덱스로 구분하게 됩니다. 문제풀이(java) 장르(genre)와 노래(song)에 해당 하는 클래스를 만들어서 해당 정보들을 기입하고, 내림차순 정렬시에 Collections.sort를 사용하는 방법을 선택했습니다. 클래스를 둘로 나누어서 풀어보니 한 장르의 ..
프로그래머스 알고리즘 - 위장☞ 프로그래머스 위장 문제 링크 입출력 예제를 자세히 보게 되면 출력은 경우의 수가 몇개인지 반환하면 되는 문제이므로 실제로 어떤 조합으로 꾸려야 하는지는 중요하지 않습니다. 같은 종류의 의상이 몇개인지 파악하고 의상 종류의 갯수를 모두 곱하면 경우의 수를 구할 수 있습니다. 다만, 적어도 한가지 의상은 입어야 하므로 아무것도 입지 않은 경우 한가지를 제외 합니다. 예를들어 첫번째 입력 예제 같은 경우, eyewear : blue_sunglasses (1가지)headgear : yellow_hat, green_turban (2가지)총 3가지 의상이 있습니다만, 입지 않은 경우의 수도 고려 해야 하므로,eyewear : 2가지headgear : 3가지라고 판단합니다. 2x3은 ..
프로그래머스 알고리즘 - 완주하지 못한 선수☞ 프로그래머스 완주하지 못한 선수 문제 링크 문제를 풀기위한 로직은 여러가지가 존재할 것이고, 많이 어렵진 않았습니다. 다만 문제에서 효율성 검사도 진행하기 때문에 효율성에 대한 고민이 없다면은 시간 초과가 나오게 됩니다. (실제로 가벼운 마음으로 무식하게 풀었더니 시간 초과가 나왔습니다.) 힌트는 문제의 분류에 있습니다. 바로 '해시'를 이용하는 것인데요. 자바에서의 HashMap만 사용하여도 검색시간이 많이 줄어서 바로 통과 할 수 있습니다. 문제가 조금 모호하긴 합니다. 동명이인인 선수가 존재하나 완주하지 못한 선수는 오직 한명이기 때문에 동명이인인 선수가 몇명인지만 확인하면 됩니다. (이럴꺼면 문제 이름이 '완주하지 못한 선수'보다는 '마지막으로 들어온..
해시 (Hash) 해시란 데이터를 다루는 기법 중에 하나로 검색과 저장이 아주 빠르게 진행됩니다! 아주 빠르게 진행될 수 있는 이유는 데이터를 검색할 때 사용할 key와 실제 데이터의 값이 (value가) 한 쌍으로 존재하고, key값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도가 O(1)에 수렴하게 됩니다. 해시 함수, 해시 알고리즘, 해시코드? 데이터의 key값을 배열의 인덱스인 정수로 변환하기 위해서는 일련의 과정이 필요합니다. 예를들어 데이터를 문자열로 받게 되었을 때 문자 한글자 한글자의 아스키 코드 값을 더하는 과정으로 문자열을 정수 값으로 변환할 수 있습니다. (만약, hello 라는 문자열을 정수형 key 값으로 바꾼다면, h + e + l + l + o -> 10..
프로그래머스 알고리즘 - 단어변환 ☞ 단어변환 문제 링크 문제의 핵심은 각 word를 노드로 두고, 변환 가능한 word간에는 간선(edge)로 연결해둔 다음에 그래프 탐색을 진행하면 어렵지 않은 문제 였습니다.☞ 그래프(Graph) DFS 탐색 구현하기 문제풀이 코드의 전체적인 틀은 그래프 탐색을 응용합니다. class Graph { private Word[] words; . . . } 입력값의 문자를 이용한 만든 클래스 Word를 그래프 탐색의 노드(Node)로 치환합니다. class Word { private String name; private List changeable; //인접 노드(Word)들을 저장하는 리스트 private boolean visited; . . . } 주어진 word와 기..
프린터큐 ☞ 문제링크 Document를 클래스로 선언해야겠다는 생각만 했다면, 나머지는 큐의 기능을 문제 그대로 구현만 하면 되는 문제 였습니다. 문제 풀이 전략 (java) Document(문서) 클래스를 선언한다. class Document { } Document는 필드값으로 sequence(순서)와 importance(중요도)를 갖는다. class Document { private int sequence; private int importance; } 입력값을 기준으로 Document 인스턴스들이 담겨있는 큐를 정의한다. public static int solution(int N, int M, int[] importance) { Queue documentQueue = new LinkedList();..