목록알고리즘/프로그래머스 (16)

안드 공부를 해볼까?

[Java] 프로그래머스 모음사전

1. 문제분석 알파벳 모음으로 길이 5이하의 단어를 만든다고 한다. 그 때 주어진 word는 몇번째 있는지 찾는 문제다. 헷갈리면 안되는것은 AAAAA, AAAAE 처럼 만들어진다고 해서 그냥 배열에 모음 4개씩, 총 25개 넣으면 난리가 난다. 문제는 길이 5 이하의 단어다. 그렇다면 바로 중복 부분수열을 통해서 구하면 된다 A가 5개 있어도 상관없고 E가 5개 있어도 상관없다. 주어진 5개의 단어로 길이 5이하의 모든 부분 수열을 구하면 된다. 2. 구현 import java.util.ArrayList; import java.util.Comparator; public class Solution { ArrayList list = new ArrayList(); public static void main(..
알고리즘/프로그래머스 2022. 9. 21. 17:40
[Java] 프로그래머스 전력망을 둘로 나누기

1. 문제 분석 송전탑에 전선을 하나를 끊어 전력망 네트워크 2개로 분리한다고 한다. 분리한 네트워크 망에서 송전탑의 개수 차이를 최소화 한다고 한다. 문제에서 트리 형태로 연결되있다고 해서 트리를 생각하다가 예시를 보고 그래프로 바꿨다. 본다면 그래프가 자동으로 생각이 난다 ㅎㅎ.. 필자는 2차원 배열로 양방향 그래프를 구현했다. 그리고 정확히 어디를 끊어야 최소가 되는지 모르므로 완전탐색을 썼다. 또한 송전탑의 개수를 구해야하므로 DFS를 사용했다. 정리를 해보면 다음과 같다. 1. 연결된 부분 중 1개를 자르기 2. 자른 시작점, 끝점을 기준으로 DFS 3. 2개의 네트워크 망 내에 있는 송전탑의 개수의 차 구하기 4. 최솟값 구하기 2. 구현 public class Solution { int ve..
알고리즘/프로그래머스 2022. 9. 21. 16:54
[Java] 프로그래머스 피로도

1. 문제 분석 피로도에 따라 던전을 최대 몇개까지 들어갈 수 있는지를 구하는 문제다. 요구피로도와 사용피로도가 있어 현재 피로도가 요구피로도보다 낮다면 던전에 들어가지 못한다. 처음 접근은 던전 배열을 정렬해서 들어가야하나 싶지만 이러면 전혀 답을 구할 수 없다. 값도 작으니 나는 완전탐색을 통해서 문제를 해결했다. 2022.09.21 - [문법/Java] - [Java] 순열 [Java] 순열 1. 개요 지난번에 조합에 이어 순열을 정리해볼려고한다. 알고리즘을 푸는 중 조합 + 순열을 사용해서 푸는 문제가 있었다. 2개 다 까먹어서 한번 더 볼겸 순열을 정리할려고 한다.. 2. 목차 - 순열 moonbari.tistory.com 던전의 개수만큼 크기를 가진 1차원 배열을 생성한다. 그리고 그 배열에 ..
알고리즘/프로그래머스 2022. 9. 21. 14:34
[Java] 프로그래머스 소수찾기

1. 문제 분석 주어진 숫자를 사용해서 소수를 만드는 것이다. 테스트케이스 1을 먼저 보자. 17로 만들 수 있는 소수는 총 7, 17, 71로 3개가 된다. 여기서 바로 구현하는 방법을 얻을 수 있다. 순서에 상관없이 모든 경우의 수를 뽑자. 순열로 소수를 판별하는 문제다. 이번 문제에서는 백트래킹으로 순열을 찾았다. 찾은 수들은 제곱근으로 소수를 찾았다. 순열관련 포스팅은 밑의 글을 참고하자. 2022.09.21 - [문법/Java] - [Java] 순열 [Java] 순열 1. 개요 지난번에 조합에 이어 순열을 정리해볼려고한다. 알고리즘을 푸는 중 조합 + 순열을 사용해서 푸는 문제가 있었다. 2개 다 까먹어서 한번 더 볼겸 순열을 정리할려고 한다.. 2. 목차 - 순열 moonbari.tistory..
알고리즘/프로그래머스 2022. 9. 21. 11:23
[Java] 프로그래머스 전화번호 목록

1. 문제 분석 전에 풀었던 완주하지 못한 선수와 비슷한 문제다. 하지만 이번 문제의 키워드는 접두어다. 필자도 접두어를 무시하고 그냥 구현했는데 계속 오류가 났다. 이번에도 해시를 사용하지 않아도 해결이 가능하지만 우리는 해시를 사용해보자(카테고리가 해시니깐..) 먼저 이번에도 고정되어야 하는 값을 찾아보자. 사실 이 문제는 어느 부분을 해도 상관이 없다고 생각한다. 접두어를 포함하는 것이니 contains를 사용할 것 이다. HashMap은 containsKey와 containsValue가 존재하기 때문에 이번 문제는 어느부분을 넣어도 상관없다. (사실 이렇게 되면 왜 HashMap을 써야하나 싶다. 2중 포문이라 시간 복잡도가 정말 나쁜데..) 접두어가 되니 앞글자 부터 하나씩 봐야한다. 만약 자신..
알고리즘/프로그래머스 2022. 5. 14. 02:47
[Java] 프로그래머스 완주하지 못한 선수

1. 문제분석 문제가 너무 쉽다. 단순히 두 배열을 비교해서 완주하지 못한 선수를 return해주면 된다. participant와 completion을 정렬하고 다른 데이터 한개만 쏙 빼면 되겠지만 이 문제의 카테고리가 "해시"이기 때문에 해시로 풀어보자. HashMap은 Key와 Value로 이루어진 자료구조이다. Key는 중복될 수 없고 한가지만 가질 수 있다. 만약 중복된 값이 들어온다면 새로 들어온 순으로 업데이트 된다. Value는 중복이 가능하다. HashMap은 Key - Value 쌍으로 데이터를 쉽게 찾기 위해 사용된다. 먼저 HashMap을 어떻게 선언해야할지 보자. 우리가 독립적으로 한가지만 가지는 것은 배열 속 데이터다. 그렇다면 중복이 안되는 Key를 participant의 데이터..
알고리즘/프로그래머스 2022. 5. 14. 01:39
[Java] 프로그래머스 큰 수 만들기

1. 문제분석 순서를 유지하면서 가장 큰 수를 뽑는 문제다. 순서가 존재하므로 정렬로 하면 안되고 나는 재귀를 생각해서 2개의 숫자를 뽑은 후 가장 큰 수를 반환할려고 했다. 계속 알고리즘적으로 생각해봤는데 암만봐도 이건 아니다 싶었다. 그래서 다른 방면으로 생각해봤다. 만약 6자리를 뽑는다면 맨 처음 수는 어디서 뽑아야할까? 말 그대로 첫번째 자리를 위해 나머지 뒤의 숫자를 이미 정해뒀다고 생각하는 것이다. 테스트케이스 3번을 보자. 4177252841이고 4개의 숫자를 뺀다고 한다. 그러면 총 6개의 숫자를 고르는 것이다. 첫번째를 뽑고 나머지 5글자는 맨 뒤에 둔다고 하자. 4 1 7 7 2 5 2 8 4 1 가 된다. 말 그대로 첫번째 숫자는 "41772", 최소 조건을 만족하기 위해 나머지 숫자..
알고리즘/프로그래머스 2022. 5. 14. 00:49
[Java] 프로그래머스 섬 연결하기

1. 문제분석 섬마다 다리를 연결하는 비용의 최솟값을 구하는 문제이다. 섬을 노드, 비용을 가중치라고 생각하면 크루스칼 알고리즘을 바로 떠올릴 수 있다. 크루스칼 알고리즘에 대해서는 나중에 글로 정리할 예정이다. 주석을 달아놨으니 이해하는데 어려움은 없을 것이다. 2. 구현 class Solution { //내가 속한 집합을 찾는 메소드 public int find(int[] parent, int i) { //자기 자신을 가르킨다? -> 부모 if (parent[i] == i) { return i; } //어딘가에 속해있다, 부모를 찾으러 가자. return find(parent, parent[i]); } //두개의 집합을 합쳐보자. public int[] union(int[] parent, int a,..
알고리즘/프로그래머스 2022. 5. 12. 23:17
Prev 1 2 Next