목록분류 전체보기 (95)

안드 공부를 해볼까?

[Java] 프로그래머스 전화번호 목록

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

1. 개요 지난 알고리즘 풀이 때 subString을 사용해서 문제를 풀고있는데 너무 오랜 시간이 걸렸다. 좀 더 확실하게 알고 까먹지 않기 위해 정리해본다. 2. subString(int beginIndex) subString은 1가지 매개변수를 가진형태와 2가지 매개변수를 가진 형태, 2가지가 존재한다. 먼저 첫번째를 보자. 주석을 보면 문자열을 자르고 return을 한다, 그리고 매개변수는 String의 idx부터 시작한다. String num = "012345678"이 있다고 하자. 그렇다면 매개변수에 2를 넣어주면 num의 3번째 부터 시작하는 것이다. 배열의 인덱스 처럼 0부터 시작한다고 생각하자. 그렇다면 이해하기 쉽다. public class main { public static void ..
문법/Java 2022. 5. 14. 02:01
[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
[Java] 프로그래머스 구명보트

1. 문제파악 구명보트로 탈출을 하는데 여기서 조건을 잘 살펴봐야한다. 1. 무게 제한을 넘어가면 보트를 같이 탈 수 없다. 2. 구명보트는 작아서 최대 2명만 탈 수 있다. 항상 문제를 잘 보고 분석하는 방법으로 해결해야하는데 매일 대충보고 풀어 이번에도 오래 걸렸다. 최대 2명만 탈 수 있다.. 문제를 잘 보도록 하자 그렇다면 보트의 최솟값을 구할려면 어떻게 접근해야할까? 1. 정렬 후 앞에서 부터 하나씩 찾기 만약 [70,50,80,50]이라고 생각하자. 정렬 후 배열은 [50,50,70,80]이 된다. 앞에서 부터 하나씩 값을 가져오고 인원이 2명이 넘거나 무게가 초과되면 다음 인덱스로 넘어가게 구현한다. 하지만 이게 가장 최솟값을 구하는 방법일까? [40,40,40,200,200,200]와 제한..
알고리즘/프로그래머스 2022. 5. 11. 23:17
[Java] 프로그래머스 가장 큰 수

1. 문제 파악 주어진 배열을 통해 숫자를 만들고 이중 가장 큰수를 선택하는 문제다. 처음은 배열을 정렬하면 끝이지 않나? 싶었지만 테스트케이스 2를 보면 30이 3보다 값이 크지만 뒤로간다. 그럼 이제 3과 30을 비교해본다고 하자. 두 개를 붙이면 303과 330이 된다. 303과 330중 큰 수는 330이다. 앞의 숫자 + 뒤의 숫자와 뒤의 숫자 + 앞의 숫자를 비교해서 정렬하면 된다. 2. 구현 import java.util.*; public class main { public static void main(String[] args) { int[] times = new int[]{3,30,34,5,9}; System.out.println(new Solution().solution(times)); ..
알고리즘/프로그래머스 2022. 5. 10. 03:19
[Java] 프로그래머스 입국심사

1. 문제분석 문제를 보고 심사관의 수 만큼 배열을 생성해 사람이 들어갈 수 있는 공간을 만들려고 했다. 하지만 입국심사를 기다리는 사람이 10억명까지 나오고 시간 또한 10억분이 나온다. 한개씩 데이터를 사용하기엔 너무 오랜시간이 걸리기 때문에 이분탐색을 사용한다. 이분탐색은 우리가 아는 이진탐색과 동일하다. 1부터 12까지, 우리가 찾고자 하는 데이터가 9라고 생각해보자. 그렇다면 1과 12의 가운데에서 값을 찾아가는 것이다. 가운데 값은 (start + end) / 2로 쉽게 구할 수 있다. 이제 end가 찾고자하는 값보다 큰지, 작은지를 구하면 조건에 맞지 않는 값 절반이 버려진다. mid가 찾고자하는 값보다 크기 때문에 mid의 뒤에 값은 버려도 상관없다. 또한 mid까지 값을 비교했으니 mid..
알고리즘/프로그래머스 2022. 5. 10. 00:00
Prev 1 ··· 8 9 10 11 12 Next