본문 바로가기

프로그래머스25

[알고리즘] 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. 문제 풀이 체육복을 빌릴 때 체육복이 없고, 앞에 사람이 여유분이 있다면 무조건 앞에 사람한테서 체육복을 빌린다. 만약 앞에 사람이 여유 체육복이 없고 뒤에 사람이 여유 체유복이 있으면 뒤에 사람한테 빌리도록 순서를 강제한다. 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.
[알고리즘] 프로그래머스 - 등굣길 (동적 계획법) 1. 문제 2. 문제 풀이 dp 배열을 먼저 초기화 하는데, 0행과 0열에 물웅덩이가 있으면 그 다음 지역으로는 갈 수 없으므로 0으로 초기화 된 값을 남겨둔다. 그리고 물웅덩이가 없을때가지 1로 초기화를 해준다. dp 배열을 채울때 물웅덩이가 있으면 0으로 바꿔주고, 나머지 경우는 코드를 참고하면 쉽게 이해할 수 있다. class Solution { private static int dp[][]; public static void calculateDp(int m, int n){ for(int i=0;i 2020. 10. 7.
[알고리즘] 프로그래머스 - 여행경로(dfs/bfs) 1. 문제 2. 문제풀이 처음에 풀때 인접행렬을 이용해서 인접행렬의 방문한 곳은 다시 방문하지 않는 형태로 풀었었다. 하지만 항공사를 여러번 방문 할 수 있기 때문에 인접행렬이아닌, 항공권을 사용했는지를 체크하는 형태로 바꾸었다. 주어진 조건중에 알파벳 순서가 앞서는 경로를 return 하라는 조건을 각 배열을 정렬해야하나 했다가 String으로 방문 가능한 경로를 ','로 이어주고 그 Stirng들을 저장한 list를 정렬하는 방식으로 수정하였다. 1. 출발 항공사가 "ICN"일 경우 그 항공권을 사용했다고 표시해주고 dfs알고리즘을 호출한다. 2. route에 현재 경로를 더해주고, 현재 사용하지 않은 티켓중에 이전 도착지와 현재 티켓의 출발지가 같다면 티켓을 사용했다고 표시하고 dfs 알고리즘을 다.. 2020. 8. 8.
[알고리즘] 프로그래머스 - 단어변환 (dfs/bfs) 1. 문제 2. 문제풀이 현재 주어진 단어를 한글자씩 수정해서 최종 목표 단어로 변환이 가능한지를 구하고, 만약 변환이 가능하다면 몇번만에 가능한지 최소 변환 횟수를 구하는 문제였다. 현재 단어에서 words 배열에 있는 단어로 변환이 가능하다면 visit 배열에 방문을했다고 표시를 한 후 dfs 탐색 방법을 이용해서 탐색을 진행한다. dfs의 base case로는 전부 방문했거나, 현재 단어와 찾는 단어가 같을 경우 탐색을 종료했다. 그리고 최소 횟수를 계속 갱신하여 최종적으로 minNum을 반환한다. 변환이 불가능할 경우 0을 반환한다. class Solution { int minNum = 999999999; public void dfs(boolean[] visit, String[] words, St.. 2020. 8. 8.

티스토리툴바