본문 바로가기
순위검색 - 프로그래머스 (Java, Level 2) 처음 풀이 간단한 문제라고 생각했다. 하나의 query마다, 모든 지원자들을 비교해가면서 몇 명이 해당하는지 셌다. solution() public int[] solution(String[] info, String[] query) { int[] answer = new int[query.length]; int index = 0; for (String conditions : query) { String[] condition = conditions.replaceAll("and ", "").split(" "); answer[index++] = find(condition[0], condition[1], condition[2], condition[3], condition[4], info); }//for end re.. 2022. 5. 2.
거리두기 확인하기 - 2021 카카오 채용연계형 인턴십 (Java, Level 2) 처음 풀이 1. 한 고사장을 char[][] 배열에 담고, 지원자의 위치를 int[] 형태로 list에 저장한다. 2. 한 고사장 내 모든 지원자들끼리 거리두기가 지켜졌는지 확인한다. - 한 고사장 내에서 한 명이라도 거리두기가 지켜지지 않았으면 0 -> 맨허튼 거리가 1이면 무조건 false, 2이면, 두 지원자 사이가 파티션일 때만 true, 아니면 false고 3이상이면 true다., solution() public void solution(String[][] places) { int[] answer = new int[5]; char[][] map = new char[5][5]; List pLocList = new ArrayList(); for (int i = 0; i < 5; i++) { pLoc.. 2022. 4. 30.
메뉴 리뉴얼 - 프로그래머스 (Java, Level 2) 처음 풀이 1. 모든 주문에 대해 코스요리 메뉴 수에 따른 주문 조합과 그 조합 횟수를 map에 저장한다. -> 주문이 "XYZ", "XWY" 이고, 코스요리 메뉴수가 2개라면, , , 이 저장 된다. -> 주문 조합은 재귀로 구한다. 2. 저장된 map에서 횟수가 2이상이면서 가장 큰 주문 조합을 list에 저장한다. 3. 모든 코스요리 메뉴 수에서 같은 작업을 한다. 4. list를 알파벳 순으로 정렬하고, 배열로 옮긴다. solution() //메뉴 수에 맞는 메뉴 조합과 주문 횟수 저장할 map Map menuListMap; public String[] solution(String[] orders, int[] course) { List answerList = new ArrayList(); menu.. 2022. 4. 29.
빛의 경로 사이클 - 월간 코드 챌린지 시즌3 (Java, Level 2) 처음 풀이 1. grid를 각 격자별로 나눠서 2차원 배열에 저장한다.(map), 격자 1개당 up, right, down, left 시계 방향에 대한 정보를 담을 3차원 배열을 만든다. 2. 현재 이동방향과 격자에 따라 이동하면서 재귀적으로 경로 길이를 저장하는 메소드를 만든다. (move) - 재귀중단조건은 현재 이동하는 경로에 저장된 값이 0이 아닌 경우이다. 이미 지나간 경로이기 때문이다. - 재귀중단조건을 만났다는 건 하나의 순환 경로가 만들어진 것이므로 현재까지 이동거리를 list에 저장한다. 3. 현재 이동방향과 도착할 다음 격자에 따라 다음 이동방향을 결정하는 메소드를 만든다. (changeDir) - "S"면 방향 그대로, "L"이면 반 시계 방향이므로 현재 direction index에.. 2022. 4. 26.
소수찾기 - 프로그래머스 (Java, Level 2) 처음 풀이 dfs로 숫자들을 배열한다. 숫자 배열하는 중간중간 소수인지 확인하고 소수면 Set에 저장한다. 최종적으로 Set의 size를 리턴한다. 1. solution() 전역 변수들 초기화 Set primeSet; String[] numStrArr; boolean[] isUsed; StringBuilder sb; public int solution(String numbers) { int totalLength = numbers.length(); primeSet = new HashSet(); numStrArr = new String[totalLength]; isUsed = new boolean[totalLength]; sb = new StringBuilder(); for (int i = 0; i < to.. 2022. 4. 10.
줄 서는 방법 - 프로그래머스 (Java, Level 3) 전체적인 흐름 - k번째의 수를 구할 때, 현재 자리에서 숫자 1개당 나올 수 있는 배열 수 (criteria 변수)를 구한다. - 남은 k번째와 criteria를 나눈 값의 올림값이 현재 자리에서 몇 번째 그룹에 속하는지, 즉, 남은 숫자들 중 몇 번째 숫자가 와야하는지 알려준다. - k를 현재 자리의 criteria를 나눈 나머지 값으로 세팅한다. 즉, 현재 자리에서, 속한 그룹의 직전 그룹까지의 배열의 수를 빼주는 것이다. - 이 과정이 k==0이 될 때까지 반복한다. public int[] solution(int n, long k) { //1~n까지 담을 list List numList = new ArrayList(); //index와 수를 맞추기 위해 index 0 채움 numList.add(0.. 2022. 4. 8.
그래프 구현 방식 그래프 구현 방식에는 2가지가 있다. 1. 인접 행렬 2. 인접 리스트 최단 거리 알고리즘 1. BFS - 간선 가중치가 없을 때 2. 다익스트라 - 간선 가중치가 있을 때 3. 벨만-포드 - 음의 가중치가 있을 때 4. 플로이트 워셜 - 모든 정점에서 모든 정점까지의 최단거리를 구할 때 https://velog.io/@ehdrms2034/알고리즘-최단-경로-알고리즘-다익스트라-벨만-포드-플로이드-알고리즘 2022. 3. 31.
[3차] 압축 - 2018 KAKAO (Java, Level 2) 처음 풀이 1. 사전 생성 후 알파벳 등록 - Map에 기본 알파벳을 값과 함께 저장 - 뒤로 새로운 문자열 나오면 계속 추가 //사전 Map dictionary = new HashMap(); for (int i = 65; i < 91; i++) { dictionary.put((char)(i)+"", i-64); }//for end 2. 문자열 탐색 - 색인값을 추출하지 않은 인덱스서부터 탐색 - 간격을 하나씩 벌리면서 주어진 문자열을 자른 후 사전에 있는지 확인 - 자른 문자열이 사전에 없으면, 직전 간격으로 자른 문자열의 색인 번호를 출력, 현재 자른 문자열을 사전에 등록, 현재 자른 문자열에 포함되지 않은 문자로 인덱스를 이동 - 간격을 벌리다가 만일 문자열 인덱스를 넘어가면, (try~catch).. 2022. 3. 25.
후보키 - 2019 KAKAO BLIND RECRUITMENT (Java, Level 2) 처음 생각 - 컬럼들을 조합하여 한 조합 당 각 컬럼의 문자열을 합친 다음 이를 Set에 삽입한다. Set의 사이즈가 전체 튜플의 수와 같다면 튜플을 유일하게 식별할 수 있다는 의미이므로 후보키가 되는 컬럼 조합이다. - 모든 컬럼 조합에 대한 유일성 조사를 어떻게 할 것인가? 컬럼이 4개라 하면 0 1 2 3 01 02 03 12 13 23 012 013 023 123 1234처럼 컬럼 갯수가 다른 조합까지 어떻게 식으로 표현해야 하나? - 만일, 유일성을 만족하는 컬럼 조합이 0 01 12 123일 때 어떤 식으로 저장해야 최소성을 검사할 수 있을까? int[]? 새로운 객체? 등등 해결되지 않거나 지나치게 복잡해보이는 흐름이 많았다. 참고 풀이 위에서 하던 고민을 해결해주는 개념이 있었다. 바로 비.. 2022. 3. 22.
AVL 트리 vs Red-Black 트리 BST(Binary Search Tree, 이진탐색트리)는 key 삽입 순서에 따라서 트리의 모양 및 균형이 많이 달라진다. BST에서 검색 시간복잡도는 보통 O(logN), 즉 트리의 높이 값이다. 하지만 트리의 모양이 한 쪽으로 치우친 최악의 상황이라면 BST의 이점을 하나도 살리지 못하고 시간 복잡도가 O(N)이 된다. AVL 트리, Red-Black 트리 모두 BST(Binary Search Tree, 이진탐색트리)의 단점을 보완하기 위한 자료구조이다. AVL 트리는 트리 높이를 이용한 BF(Balance Factor, 균형도)를 노드마다 계산하여 삽입/삭제 시에 균형을 맞춘다. Red-Black 트리는 각 노드에 Red 혹은 Black을 배치해 다양한 규칙을 이용해 트리의 균형을 맞춘다. 두 트.. 2022. 3. 19.

티스토리툴바