✔ 몸짱 트레이너 라이언의 고민 [프로그래머스 1838] 문제 분석하기 이용 시간에 대해 최대로 겹치는 손님의 수를 찾아낸 후, 배치할 수 있는 최대 거리를 구하도록 함 손으로 풀어보기 구간합을 이용해 이용 시간에 대해 최대로 겹치는 손님의 수를 찾음 시간을 인덱스로 하는 배열을 생성하고, 각 회원의 시작 지점에 손님 수 1 증가, 종료 지점에 손님 수 1 감소를 해주도록 함 최대로 겹치는 손님의 수에 대해 배치할 수 있는 최대 거리를 구하도록 함 한 변의 길이가 n인 맵에 대해 2개를 배치할 때 최대 거리는 대각선인 2 * (n - 1)이므로 최대 거리에서부터 크기를 점점 줄여가며 배치할 수 있는지 판별하도록 함 배치할 수 있는 락커 수가 손님의 수와 일치할 경우 이를 최대 거리로 반환 슈도코드 작성하..
✔ GPS [프로그래머스 1837] 문제 분석하기 DP를 이용해 특정 노드에서 특정 노드까지 이동할 때의 최소 오류 변경 횟수를 저장하여 이를 이용하도록 함 손으로 풀어보기 점화식의 형태와 의미를 도출 D[start][end]는 start에서 목적지인 end를 갈 때 수정한 최소 오류 변경 횟수 점화식을 구함 D[0][gps_log[0]]은 0 start와 end가 같다면, D[start][end] = 0 start와 end가 같지 않다면, D[start][end] = MAX D[start][end] = Math.min(D[start + 1][next], result) 점화식으로 D 배열을 채운 후 D[k - 1][gps_log[k - 1]]을 반환 슈도코드 작성하기 n(거점 개수) m(도로의 개수) e..
✔ 리틀 프렌즈 사천성 [프로그래머스 1836] 문제 분석하기 알파벳 순으로 가장 먼저인 문자열 타열을 먼저 탐색하며 타일을 모두 제거할 수 있는지 확인 손으로 풀어보기 알파벳 문자 타일의 종류와 그에 따른 위치를 저장 알파벳 순으로 가장 먼저인 문자열 타일을 먼저 탐색해야 하므로 오름차순 정렬 반복문을 통해 각 타일이 삭제 가능한지 확인 직선 한 번으로 제거할 수 있는 경우와 직선 한 번과 꺾은 선 한 번으로 제거할 수 있는 경우를 확인 타일이 삭제 가능하면 삭제 후, answer에 타일을 추가하고 해당 타일의 위치를 .으로 갱신 타일이 삭제 불가능하면 다른 타일을 먼저 탐색하고 다시 타일을 탐색 모든 타일의 개수만큼 탐색했을 때도 타일이 삭제 불가능하다면 IMPOSSIBLE 반환 슈도코드 작성하기 m..
✔ 캠핑 [프로그래머스 1833] 문제 분석하기 x축을 기준으로 정렬한 후, 같을 경우 y축을 기준으로 정렬하도록 한 후 하나의 쐐기와 다른 쐐기를 골라 조합에 따라 텐트의 넓이가 0보다 큰지 확인하고, 이 안에 다른 쐐기가 있는지 비교하도록 함 손으로 풀어보기 x축을 기준으로 정렬한 후, 같을 경우 y축을 기준으로 정렬 하나의 쐐기와 다른 쐐기를 골라 조합에 따라 텐트의 넓이가 0보다 큰지 확인 이때 구간합을 이용해 텐트의 넓이나 좌표를 구하면 시간을 줄일 수 있음 텐트 안에 다른 쐐기가 있는지 비교 슈도코드 작성하기 n(쐐기의 개수) data(캠핑장에 설치된 쐐기의 x좌표와 y좌표) answer(가능한 텐트의 쐐기의 쌍의 개수) x축을 기준으로 정렬한 후, 같을 경우 y축을 기준으로 커스텀 정렬 fo..
✔ 보행자 천국 [프로그래머스 1832] 문제 분석하기 아래쪽과 오른쪽으로만 이동이 가능하므로, DP를 이용해 이전 칸에 도달할 수 있는 경우의 수를 구하도록 함 손으로 풀어보기 점화식의 형태와 의미를 도출 D[i][j][0]은 위쪽에서 아래쪽로 이동하며 i, j번째 칸에 도달할 수 있는 경우의 수 D[i][j][1]은 왼쪽에서 오른쪽으로 이동하며 i, j번째 칸에 도달할 수 있는 경우의 수 점화식을 구함 D[0][0][0], D[0][0][1]은 0 D[1][1][0], D[1][1][1]은 1 0인 경우에는 자동차가 자유롭게 지나갈 수 있으므로 D[i][j][0]은 D[i - 1][j][0] + D[i][j - 1][1], D[i][j][1]은 D[i - 1][j][0] + D[i][j - 1][1]..
✔ 브라이언의 고민 [프로그래머스 1830] 문제 분석하기 규칙에 따라 예외가 발생하는지 확인하도록 함 손으로 풀어보기 각 소문자의 위치를 구함 문자를 순서대로 탐색하며 규칙을 판단 각 규칙에 따라 올바른 단어인지, 예외가 발생하지 않는지 확인 예외가 발생할 경우 invalid 반환 탐색을 하며 저장한 대문자를 원래 단어에 추가 슈도코드 작성하기 sentence(주어진 광고 문구) answer(광고 문구의 규칙 적용 전 원래 문구) alphabetCheck(소문자 알파벳을 특수문자로 사용 유무 배열) firstRule(규칙 1 여부) secondRule(규칙 2 여부) charRule1(규칙 1일 때 특수문자로 쓰이는 소문자) charRule2(규칙 2일 때 특수문자로 쓰이는 소문자) words(규칙이 ..
✔ 도넛과 막대 그래프 [프로그래머스 258711] 문제 분석하기 들어오는 간선이 없으며 나가는 간선이 2 이상인 정점을 임의의 정점으로 찾도록 함 그리고 이를 이용해 연결된 노드를 확인하며 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프 개수를 셈 예1) 생성한 정점은 2번, 도넛 모양 그래프 1개(1), 막대 모양 그래프 1개(3, 4) 예2) 생성한 정점은 4번, 막대 모양 그래프 1개(2), 8자 모양 그래프 2개(5, 3, 8 / 12, 7, 1, 11, 10, 9, 6) 손으로 풀어보기 그래프에 따라 들어오고 나가는 간선의 정보를 초기화 들어오는 간선이 없으며 나가는 간선이 2개 이상인 정점을 임의의 정점으로 찾도록 함 나가는 간선이 0개인 정점이 있다면 막대 모양 그래프의 개수를 증..
✔ 가장 많이 받은 선물 [프로그래머스 258712] 문제 분석하기 해시맵을 통해 서로 주고받은 선물 기록을 확인하며 그에 따른 선물 지수를 계산하도록 함 그리고 선물 지수에 따라 다음달에 받을 선물의 수를 계산하도록 함 손으로 풀어보기 해시맵을 통해 서로 주고받은 선물 기록을 확인하며 그에 따른 선물 지수를 계산 선물 지수에 따라 다음달에 받을 선물의 수를 계산하도록 함 슈도코드 작성하기 friends(친구들의 이름을 담은 1차원 문자열 배열) gifts(이번 달까지 친구들이 주고받은 선물 기록을 담은 1차원 문자열 배열) answer(다음달에 가장 많은 선물을 받은 친구가 받을 선물의 수) giftRecords(친구들의 이름에 따라 주고받은 선물 기록 HashMap) giftScore(선물 지수 Ha..
