📑 1. 문제설명💡 2. 풀이 과정일단 문제가 길어도 너무 길어서 나름대로 요약을 해 봤다. record 배열은 입장 또는 퇴장 정보를 담고 있는 2차원 배열이다. 입장은 ["Enter id 닉네임"] → "닉네임님이 들어왔습니다."퇴장은 ["Leave id"] → "닉네임님이 나갔습니다."닉변은 ["Change id 닉네임"]record0번 인덱스 = 행동(입장/퇴장/닉변)1번 인덱스 = id2번 인덱스 = 닉네임 여기서 중요한 것은 채팅방에 보여지는 메세지에는 최종적으로 변경된 닉네임이 보여져야 한다는 것이다. 그렇다면 한 아이디가 가장 마지막으로 사용한 닉네임이 무엇인지 조회하고 메세지를 보여줄 때 아이디값을 그 닉네임으로 바꾸는 방법으로 문제를 해결해야 한다. 닉네임 정보를 저장하기 위해서 ..
정렬(Sort)개요데이터를 오름차순 또는 내림차순으로 배열하거나 리스트의 요소를 정렬하는 과정이다. 정렬을 활용한 코딩테스트 문제는 매우 다양하다. 정렬 문제는 문제를 풀 때는 정렬 기준을 정확히 파악하고, 그에 맞는 알고리즘을 선택하는 것이 중요하다. 정렬 알고리즘, 이진 탐색, 투 포인터, 빈도수 계산 등 다양한 기술을 조합해 해결해야 하는 문제들이 많다. 주어진 조건을 Arrays.sort() 를 이용해서 정렬해야 하는 문제도 있고, 정렬 기준을 사용자 정의 객체에 맞게 지정해야 하는 경우, Comparator 인터페이스를 구현한 객체를 Collections.sort() 또는 Arrays.sort()에 전달하여 정렬하면 되고, 이 때 Java 8 이상에서는 Comparator를 람다 표현식으로 ..
그리디 알고리즘(Greedy Algorithm)개요greedy형용사 - 1. 탐욕스러운 2.욕심 많은 그리디 알고리즘(Greedy Algorithm)은 매 순간 가장 최적이라고 판단되는 선택을 반복하여 최종 해답을 구하는 알고리즘이다. 즉, 현재 단계에서의 최선의 선택이 최종적으로도 최적해(Optimal Solution)가 된다고 가정하고 문제를 해결한다. 코딩테스트에서 만날 경우 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형지역 최적해(Local Optimum) → 전역 최적해(Global Optimum) 보장 가능해야 함탐욕적 선택(Greedy Choice)과 최적 부분 구조(Optimal Substructure) 만족✅ 동적 프로그래밍(Dynamic Programming)과 차이..
📑 1. 문제설명 입출력 예 설명 💡 2. 접근방식이 문제는 저번에 풀었던 단속카메라 문제와 비슷하다. [프로그래머스] (Java) 단속카메라 (그리디/Greedy)📑 1. 문제설명💡 2. 접근방식입출력 예로 주어진 route 배열을 막대그래프로 그려 봤다. 최소한의 카메라를 배치해야 하므로 구간 종료 위치를 기준으로 오름차순 정렬 차량이 구간에서 카메라awesomepossum.tistory.com 예시 그래프는 각 미사일을 끝점 e 기준으로 오름차순 정렬시킨 모양이다.그래프에서 (3,7)와 (4,8)은 순서가 잘못되었는데 오류로 추정된다.단속카메라 문제와 요격시스템 문제의 차이는 끝점 포함 여부이고 둘 다 그리디 알고리즘으로 해결하면 된다. 문제 풀이 방법배열을 끝점 기준으로 오름차순 정렬각..
📑 1. 문제설명💡 2. 접근방식자료 만들 생각에 벌써부터 피곤하다. 하하하 문제 풀이에 앞서, 명색이 그래프 문제인 만큼 그래프에 대해 간략히 설명하고자 한다.2-1. 그래프의 구조노드: 원(circle)으로 표시하고, 숫자로 번호를 적는다.간선: 노드를 연결하는 선(segment)으로, 모든 간선이 양방향임을 보여주기 위해 화살표 없이 직선으로 그린다.return 하고자 하는 값은 1번 노드에서 가장 멀리 떨어진 노드의 수 이다.즉 1번 노드에서 다른 노드들로 이동하는 최단 거리를 계산해서 최단 거리가 가장 먼 노드들이 몇 개인지를 구해야 한다. 2-2. 해결 방법(1) 인접 리스트로 그래프 만들기 List> graph = new ArrayList(); 예를 들어 문제에서 제시된 vertex ..
📑 1. 문제설명💡 2. 접근방식n명의 선수가 있을 때, 각 선수는 모든 다른 선수와 경기를 하여 n-1번의 승패를 기록한다.즉, 전체 승패 결과만 있으면 각 선수의 상대적 위치를 정확히 판단해서 순위를 확정 할 수 있다. 승패를 통해 순위를 결정하는 방법은 간단히 말하면 모든 선수들 간의 직접적인 경기 결과를 반영하는 것이다. 예를 들어, 선수 i와 선수 j가 경기를 하여 승패가 결정되면, 그 결과를 기록한다. 플로이드 워셜(Floyd-Warshall) 알고리즘모든 쌍 최단 경로(all-pairs shortest path)를 구하는 알고리즘으로 그래프의 모든 노드 쌍에 대해 가장 짧은 경로를 찾는 알고리즘이다. 이 알고리즘을 사용하면 그래프의 모든 노드에 대해 다른 모든 노드로 가는 최단 경로를 ..
📑 1. 문제설명✏️ 2. 문제 요약문제에서 주어진 조건CAR_RENTAL_COMPANY_CAR CAR_RENTAL_COMPANY_RENTAL_HISTORY CAR_RENTAL_COMPANY_DISCOUNT_PLAN대여 중인 자동차들의 정보자동차 대여 기록 정보자동차 종류 별 대여 기간 종류 별 할인 정책 정보CAR_ID, CAR_TYPE, DAILY_FEE, OPTIONSHISTORY_ID, CAR_ID, START_DATE, END_DATEPLAN_ID, CAR_TYPE, DURATION_TYPE, DISCOUNT_RATE- 자동차 ID,- 자동차 종류,- 일일 대여 요금(원),- 자동차 옵션 리스트,- 자동차 대여 기록 ID,- 자동차 ID- 대여 시작일, - 대여 종료일- 요금 할인 정책 ID,..
