프로그래머스 알고리즘 - 베스트 앨범☞ 프로그래머스 베스트 앨범 문제 링크 문제 설명과 제한사항을 빠짐없이 이해해야 실수 없이 코딩이 가능합니다. 장르(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..
백준 알고리즘 - 케빈 베이컨의 6단계 법칙 (1389번)
케빈 베이컨의 6단계 법칙 ☞ 문제링크최단 경로 문제로 BFS탐색을 이용해서 풀어야 하는 문제였습니다. 문제의 예시로 그래프를 만들면 아래와 같습니다. 문제 풀이 (java) 그래프 탐색에서의 노드를 케빈 베이컨 게임의 참가한 유저로 치환하여 클래스를 만들어 줍니다. class User { private int index; private List friends; private boolean checked; . . . } 일반 노드와 다른 점은 step이라는 필드가 선언되어 있습니다. 이건 케빈 베이컨 점수를 계산하기 위해서 선언된 필드 입니다. 자세한 사항은 아래에서 설명 하겠습니다. class User { private int index; private List friends; private boole..
프로그래머스 알고리즘 - 단어변환 ☞ 단어변환 문제 링크 문제의 핵심은 각 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와 기..
순열(permutation) 알고리즘
순열(permutation) 순열이란 서로 다른 n 개 중 r 개를 골라 순서를 고려해 나열한 경우의 수를 말합니다.예를들어, 집합의 원소가 {A, B, C} 일때, 3개의 원소를 모두 사용하여 순서를 고려해 나열하는 경우의 수는 A B C, A C B, B A C, B C A, C B A, C A B로 총 6가지 경우가 나오게 됩니다. 순열 알고리즘 순열의 모든 경우를 빼먹지 않고 고려하기 위해서는 아래와 같은 로직으로 찾아갑니다. 0번째 인덱스 원소를, 0번째 부터 n-1번째까지 위치를 바꿉니다. ( A B C를 기준으로 이 과정을 진행하면 A B C, B A C, C B A 가 됩니다.)1번 과정을 진행해서 나온 경우들을, 1번째 인덱스 원소를, 1번째 부터 n-1번째까지 위치를 바꿉니다.이러한 과..
프린터큐 ☞ 문제링크 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();..