Problem Solving

문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이배열에서 연속된 부분이 있으면 하나로 압축한 배열로 리턴해야하는 문제이다. 1. 이전에 기록되었던 값에 대한 변수를 선언한다.0~9까지의수가 나올 수 있으므로, -1로 초기화 했다. 2. 이전에 기록되었던 값과 다르면, 동적 배열에 넣고 이전 값을 갱신한다. 3. 동적배열 크기만큼, int 배열을 만든다. 4. 값을 복사하고 리턴한다. 소스코드import java.util.ArrayList;public class Solution { public int[] solution(int[] arr) { int before = -1; ..

문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이기존 풀이이 문제는 로봇 강아지가 산책을 하는데, 방향과 거리에 대한 정보로 이동을 시켜서 최종 로봇 강아지의 좌표를 구하는 문제이다. 1. 방향 문자열에 대한 인덱스를 Map을 사용한다.Map을 사용하면 String에 대한 Integer값을 저장할 수 있어서 용이했고,String값(방향 문자열)에 대한 인덱스를 찾는데 O(1)연산이 걸려서 사용했다. 2. 2차원 String 배열 map을 만들고, 로봇 강아지의 시작점(sx, sy)을 기록한다. 3. String의 split 메소드를 사용해서 방향과 거리에 대한 값을 가져온다. 4. 좌표를 움직여서, 장애..

문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이이 문제에서는 초침을 기준으로 분침과 시침이 겹칠 때, 알람이 울리는데, 시작 시간과 종료 시간이 주어질 때, 몇번의 알람이 울리는지 계산하는 문제이다. 시간, 분, 초마다 1초가 지났을때, 각도가 얼마나 증가하는지 생각한다. 기준 계산시간 기준12시간에 360도를 회전하는 것을 생각해보면12 * 3600 : 360 = 1 : xx = 1/120, 1초에 1/120도 회전 분 기준60분에 360도를 회전한다.60 * 60 : 360 = 1 : xx = 1/10, 1초에 1/10도 회전 초기준60초에 360도를 회전한다.60 : 360 = 1 : xx= 6,..

문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이돗자리가 깔려있지 않은 구역에서 최대 정사각형의 길이를 구해서, mat에서 최대 길이 이하의 값을 가지는 돗자리 길이 중 최댓값을 구하는 문제이다. 필자는 이 문제에서 어떤 영역의 최대 영역을 구할때, dp를 이용해서 최대 길이를 구할 수 있다고 생각했다. 1. dp에서 어렵게 만드는 것은 어떤 점에 해당하는 최대 정사각형의 길이를 구하는 것이다. 2. 테이블을 정의dp[i][j] = (i, j)를 정사각형 우측 하단의 점일때, 가질 수 있는 정사각형 길이 3. 원하는 답을 낼 수 있는지 파악해본다.dp를 전부 순회하면서 가지는 최댓값이 돗자리를 펼 수 있..

문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이 4개의 속성을 가지는 데이터가 있는데 하나의 속성에 대해 val_ext 보다 작은 값을 추출하고 sort_by 속성 오름차순으로 정렬하는 문제이다. 데이터가 500개이기때문에, 정렬을 하든, 선형으로 순회하든 상관이 없다. 1. HashMap을 이용해서 2차원 배열에 어떤 인덱스에 있는지 기록한다.어차피 4개의 속성을 넣기도하고, 다른 풀이를 보면 List로 구현해서 찾으신 분들이 있었는데, HashMap을 사용하면, O(1)연산으로 찾을 수 있을 것이라고 생각했다. 2. ext 속성에 해당하는 val_ext 값이 작은 데이터를 ArrayList에 넣어준..

문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이어떤 퍼즐의 난이도와 사람의 숙련도를 통해 퍼즐을 해결하려고 한다.퍼즐을 해결하는데 걸리는 시간이 있는데, 그 시간을 제한시간(limit)이내에 완료하는 사람의 숙련도의 최솟값을 구하는 문제이다. 퍼즐의 난이도는 30만개의 데이터가 있고, 숙련도는 10만개의 데이터가 나올 수 있다.여기에서 숙련도를 1부터 10만까지 보면서 퍼즐을 제한시간 이내에 해결할 수 있을까? 라는 것을 생각해보면, 시간초과가 난다. 그러면 어떻게 이 문제를 해결할 수 있을까?=> 바로 이분 탐색이다!! (O(logN)) 숙련도가 어느 값이 제한 시간 이내에 들어올지 알 수 없으므로,..

문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이여기에서 세로로 시추를 해서, 세로로 인접한 면에 있는 석유를 시추할때, 최대 석유 시추량을 구하는 문제이다.나는 bfs를 이용해서 석유를 시추하는 덩어리(영역)마다 번호와 시추하는 양을 기록해야한다고 생각했다. 단 석유가 land 배열에서 1의 값을 가지기 때문에 2부터 시작하는 값을 영역의 번호를 매길 수 있다고 생각했다.최악의 경우 영역의 번호가 제일 큰 경우 약 120000 값을 가지기 때문에, int로 해도 된다. 1. 위치에 대한 클래스(Point)를 만든다. 2. 석유 시추량을 담을 배열, 방문 여부 배열, 석유가 담겨 있는 상태에 대한 배열을..

문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이진수가 보물이 위치한 곳을 찾아서 이동하는데, 직선으로 2칸을 뛰어넘을 수 있는 기회는 1번 사용해 보물이 위치한 곳으로 최단 거리를 이동하는 문제이다. 1. 배열을 선언한다.지도 배열(구멍이 있는지 없는지 여부)방문 배열(뛰어넘은 경우, 뛰어 넘지 않았을 경우) 2. 구멍의 위치를 기록한다.마지막 인자 true -> 뛰어넘은 기회 사용마지막 인자 false -> 뛰어넘은 기회 사용하지 않음 3. 큐를 만들어서 시작 위치와 경로 정보를 저장해서 bfs를 수행한다.목적지를 만나면 최단 거리이므로, 바로 answer에 기록하고 while문을 빠져나온다. 3-1..

문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이주문을 처리하면서, 손님이 몇명이 최대로 기다리는지 구하면 되는 문제이다. 1. 주문이라는 클래스를 생성한다.주문시작시간음료제조시간 2. 주문 배열을 만들어서, 주문시작시간, 음료제조시간을 기록한다. 3. 각 주문마다 주문시작시간과 제조시간을 더해서, 몇명의 손님이 받는지 투포인터를 이용해서 기록한다.s : 현재 주문 인덱스e : 주문 할때까지 들어오는 주문의 인덱스 e - s : s 주문 인덱스에 대해, 기다리는 사람의 수 4. e - s 최댓값을 찾는다. 소스코드class Solution { private static class Order { ..

문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이교육받은 사원의 능력치의 합이 사원의 능력치가 되는데, 능력치의 합을 최소화 시켜야하는 문제이다.그러면, 능력치가 낮은 사원을 계속 꺼내서 더하면 능력치의 합이 최소화 될 것이라는 생각이 든다. 데이터가 100만개이고, 능력치가 낮은 사원을 바로 찾아야한다 => 우선순위 큐를 사용해야할 것 같다는 생각이 든다.log연산으로 가장 능력치 수치가 낮은 사원을 찾을 수 있기 때문이다. 1. 사원의 능력치를 우선순위 큐에 넣는다. 2. number만큼 반복문을 수행하면서, 가장 낮은 능력치를 가진 사원 둘을 뽑아서 더한 값을 다시 2번 넣어준다. 3. 우선순위 큐..