본문 바로가기

Algorithm/Programmers

(25)
[프로그래머스] 전화번호 목록, 알고리즘 문제풀이, Hash, 해시 이전에 파이썬으로 풀었던 방식은, 정렬 후에 두개의 for 문을 사용하되 해당 순서의 길이보다 긴 것들만 찾아보는 식으로 풀었었다. 21년 3월 효율성 테스트케이스 추가되면서 안되는 듯해서 연습하다가 java로 다시 풀었다. Hash 문제라서 HashSet을 사용했는데, 단어 하나하나에서 각 전체의 substring을 구하는건 비효율적으로 보였으나, 문자열 자체를 비교하는 것 보다는, substring 에서 잘라낸 문자열을 hash 에 있는지 없는지 확인하는 것으로 찾는 것이 더 빨랐다. package algorithm_sites.programmers; import java.util.HashSet; public class hash_02_phone_number_prefix { public static vo..
프로그래머스 - 여행경로,DFS,백트래킹, 그리디,알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, Leetcode, search, greedy,acmicpc,bfs,backtracking,깊이우선탐색 // DFS 문제에서 backtracking인 것은 알았는데, stack으로 푸려다가 며칠간 고통받다가 그냥 재귀로 품 // Process // 1. Input tickets, make map // 2. Sort adjacents (알파벳순으로 들러서 먼저 나오는 것을 찾아가도록) // 3. DFS, backtracking. Start from ICN // 4. Return airport names 포인트는.. 안쓰는 티켓이 없어야 한다는 것. 그래서, DFS로 돌면서 그냥 연결된 공항을 그냥 다 순회한다는 개념이 아니라.. - 각 공항에서 연결된 공항을 따라가면서 방문한 공항은 제거해준다(방문 제외 개념). - 이 때, 더이상 공항에서 연결되어 방문할 공항이 없으면, 모든 티켓을 쓴 상황이어야 한다 (..
탐욕법 06 - 단속카메라, 프로그래머스, 알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, 풀이과정, Leetcode, 릿코드, 코딩테스트, Tech interview, search, greedy // Process // 1. Input routes (in, out) array // 2. Make routeList and sort using out position // 3. Iterate all // 3.1. Check if i's in position is before current picked out position // 3.1.1. If not -> change out position to i's out position, and add cameraCount // 4. Return cameraCount import java.util.*; class Solution { public int solution(int[][] routes) { int cameraCount = 0; // 2. List r..
탐욕법 05 - 섬 연결하기, 프로그래머스, 알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, 풀이과정, Leetcode, 릿코드, 코딩테스트, Tech interview, search, greedy 최소신장트리 (Minimum Spanning Tree, MST) 문제였는데, 처음보는거라서 Kruskal, Prim 방식 2가지가 있다고 해서 2가지로 풀어두었다. import java.util.*; // Kruskal mst // Process // 1. Input n, costs // 2. Sort using cost (ascending way) // 3. Iterate costs // 3.1. Check edge is valid or not // 3.1.1. If valid -> add cost to totalCost // 3.1.2. If not -> next // 4. Return totalCost class Solution { public int solution(int n, int[][] co..
탐욕법 04 - 구명보트, 프로그래머스, 알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, 풀이과정, Leetcode, 릿코드, 코딩테스트, Tech interview, search, greedy // Process // 1. Input // 2. Sort people in ascending way // 3. Iterate till front and rear index are met // 3.1. Check if front and rear index value can take the same boat // 3.1.1. If so -> move both indices // 3.1.2. If not -> move rear index // 3.2. ++boatCount // 4. Return boatCount import java.util.*; class Solution { public int solution(int[] people, int limit) { int boatCount = 0; int fr..
탐욕법 03 - 큰수만들기, 프로그래머스, 알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, 풀이과정, Leetcode, 릿코드, 코딩테스트, Tech interview, search, greedy // 문제에서 예를 들 때 전체 조합을 나열하고 가장 큰 것을 골라서 순서가 변해도 상관 없을 것 같으나, // 실제로 답은 순서는 건드리지 않고 찾아나가야함. // Process // 1. Input // 2. 결과 숫자를 만들 때 까지 반복한다. // 2.1. 결과 숫자를 만들 때 필요한 최소 길이를 남기고 서브스트링을 만든다. // 2.2. 서브스트링에서 가장 큰 숫자를 찾아서 더한다. 이 때, 해당 인덱스를 기억해서 다음번에 여기부터 서브스트링을 만든다. // 2.3. 가장 큰 수를 결과에 더해둔다. // 2.4. 인덱스를 바꾼다. // 3. 결과 반환한다. class Solution { public String solution(String number, int k) { StringBuilder ..
탐욕법 01 - 체육복, 프로그래머스, 알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, 풀이과정, Leetcode, 릿코드, 코딩테스트, Tech interview, search, greedy // Process // 1. Input n, lost, reserve // 2. Convert to list // 3. Remove overlapped students // 4. Iterate while lost and reserve are remained // 4.1. Check around(+-1) value of reserve is in lost array // 4.1.1. If so -> Remove both, and count student // 5. Return student import java.util.*; class Solution { public int solution(int n, int[] lost, int[] reserve) { int student = 0; // 2. List l..
완전탐색 03 - 카펫, 프로그래머스, 알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, 풀이과정, Leetcode, 릿코드, 코딩테스트, Tech interview, Heap, 힙, 정렬, sort, search # Process # 1. Input brown, yellow numbers # 2. Check the number of edges (brown) # 2.1. If so -> Check the number of inner sector (yellow) # 2.1.1. If so -> append to answer (width, height) # 3. Return valid size import math def solution(brown, yellow): answer = [] # 2. init_brown = math.ceil(brown / 2) end_brown = 3 for width_brown in range(init_brown, end_brown-1, -1): height_brown = (brown -..