본문 바로가기

Algorithm44

[알고리즘] 2020 카카오 인턴십 - 보석 쇼핑 (Two Pointers Algorithm) 1. 문제 이번 문제는 2020 카카오 인턴십에 출제된 보석 쇼핑이라는 문제이다. 2. 문제 풀이 처음에 어떤 알고리즘과 자료구조를 사용해야할지 감을 못잡아서 제대로 접근을 하지 못했었다. 이번 문제는 하나의 1차원 배열에서 left, right를 0으로 두고 left와 right를 조작해서 원하는 값을 찾는 투포인터스 알고리즘(Two Pointers Algorithm)문제이다. 1. 우선 현재 map에 들어있는 보석의 종류가 gems에 들어있는 보석의 종류보다 작을 경우 right를 1씩 증가시켜주면서map에다가 넣는다. 2. map에 들어있는 보석의 종류가 gems에 들어있는 보석의 종류와 같을 경우 left를 하나 증가 시켜주고 map에 들어있는 보석의 개수가 0개이면 map에서 해당 key를 삭제.. 2021. 1. 13.
[알고리즘] 2020 카카오 인턴십 - 수식 최대화 1. 문제 2. 문제 풀이 주어진 expression을 값과 연산으로 나누어서 list에 담는다. 연산자의 개수가 총 3개이므로 나올 수 있는 연산 순서는 6가지이다. 해당 연산 순서로 list에 담겨진 숫자들을 연산하면서 갱신한다. 연산을 여러번 반복 해야하므로 addAll 메소드를 이용하여 리스트를 깊은 복사를한다. import java.util.*; class Solution { static long answer = -1; public Long solution(String expression) { List list = new ArrayList(); //1. list에 나눠서 담음 initList(expression, list); System.out.println("list : " + list); /.. 2021. 1. 11.
[알고리즘] 2020 카카오 인턴십 - 키패드 누르기 1. 문제 2. 문제 풀이 현재 왼손과 오른손가락의 위치가 어디에 있는지 저장하면서 가운데 버튼을 누를 경우 왼손과 오른손중 어느 위치가 더 가까운지를 계산한다. 이때 거리를 계산하기 위해서는 현재 손가락 위치와 가운데 버튼 위치까지의 행과 열의 차이를 이용해서 구한다. class Solution { class Location{ int arr[][] = {{1,2,3}, {4,5,6}, {7,8,9}, {-1, 0 ,-2}}; int l = -1; int r = -2; public int getRow(int num){ for(int i=0;i 2021. 1. 11.
[알고리즘] 프로그래머스 - 섬 연결하기(탐욕법) 1. 문제 2. 문제 풀이 1. 각각의 섬이 다리로 연결된 비용을 map 배열에 저장한다. 2. 시작 섬으로 0번째 섬을 방문 했다고 표시해준다. 3. 모든 섬을 방문 하지 않았다면 모든 섬을 방문할 때 까지 최소값을 구한다. 4. 현재 방문한 섬들을 기준으로 이 섬과 연결된 다리중 가장 최소값을 선택해서 다리를 newMap 배열에 건설했다고 표시한다. 5. 4번 과정을 반복해서 answer에 각각의 최소값을 더해주고, 모든 섬을 방문하면 답이 나온다. public class Solution { int[][] map; int[][] newMap; boolean[] visit; int answer = 0; public boolean isAllVisit(){ boolean flag = true; for(in.. 2020. 10. 26.
[알고리즘] 프로그래머스 - 구명보트(탐욕법) 1. 문제 2. 문제 풀이 보트에는 2명 밖에 타지 못하므로 몸무게가 가장 많이 나가는 사람과 가장 적게 나가는 사람이 탈 경우 가장 많이 탈 수 있다. 사람들을 몸무게 순으로 정렬하고 남은 사람중 가장 많이 나가는 사람과 가장 적게 나가는 사람이 탈 경우 탈 수 있으면 같이 태우고, 같이 못타는 경우는 몸무게가 가장 많이 나가는 사람만 타게한다. import java.util.Arrays; class Solution { public int solution(int[] people, int limit) { int answer = 0; Arrays.sort(people); int s = 0; int e = people.length-1; while(s 2020. 10. 26.
[알고리즘] 프로그래머스 - 체육복 (탐욕법) 1. 문제 2. 문제 풀이 체육복을 빌릴 때 체육복이 없고, 앞에 사람이 여유분이 있다면 무조건 앞에 사람한테서 체육복을 빌린다. 만약 앞에 사람이 여유 체육복이 없고 뒤에 사람이 여유 체유복이 있으면 뒤에 사람한테 빌리도록 순서를 강제한다. import java.util.*; class Solution { private int[] person; public void greedy(int n, int[] lost, int[] reserve){ for(int i=1;i 2020. 10. 10.

티스토리툴바