주차 요금 계산
📑 문1) 주차장의 요금표와 차량이 들어오고(입차) 나간(출차) 기록이 주어졌을 때, 차량별로 주차 요금을 계산하려고 합니다. 아래는 하나의 예시를 나타냅니다.
- 요금표
| 기본 시간(분) | 기본 요금(원) | 단위 시간(분) | 단위 요금(원) |
|---|---|---|---|
| 180 | 5000 | 10 | 600 |
- 입/출차 기록
| 시각(시:분) | 차량 번호 | 내역 |
|---|---|---|
| 05:34 | 5961 | 입차 |
| 06:00 | 0000 | 입차 |
| 06:34 | 0000 | 출차 |
| 07:59 | 5961 | 출차 |
| 07:59 | 0148 | 입차 |
| 18:59 | 0000 | 입차 |
| 19:09 | 0148 | 출차 |
| 22:59 | 5961 | 입차 |
| 23:00 | 5961 | 출차 |
- 자동차별 주차 요금
| 차량 번호 | 누적 주차 시간(분) | 주차 요금(원) |
|---|---|---|
| 0000 | 34 + 300 | 5000 + ⌈(334 - 180) / 10⌉ * 600 = 14600 |
| 0148 | 670 | 5000+ ⌈(670 - 180) / 10⌉ * 600 = 34400 |
| 5961 | 146 | 5000 |
-
어떤 차량이 입차된 후에 출차된 내역이 없다면, 23:59에 출차된 것으로 간주합니다.
- 0000번 차량은 18:59에 입차된 이후, 출차된 내역이 없습니다. 따라서, 23:59에 출차된 것으로 간주합니다.
-
00:00부터 23:59까지의 입/출차 내역을 바탕으로 차량별 누적 주차 시간을 계산하여 요금을 일괄로 정산합니다.
-
누적 주차 시간이 기본 시간이하라면, 기본 요금을 청구합니다.
-
누적 주차 시간이 기본 시간을 초과하면, 기본 요금에 더해서, 초과한 시간에 대해서 단위 시간 마다 단위 요금을 청구합니다.
- 초과한 시간이 단위 시간으로 나누어 떨어지지 않으면, 올림합니다.
- ⌈a⌉ : a보다 작지 않은 최소의 정수를 의미합니다. 즉, 올림을 의미합니다.
주차 요금을 나타내는 정수 배열 fees, 자동차의 입/출차 내역을 나타내는 문자열 배열 records가 매개변수로 주어집니다. 차량 번호가 작은 자동차부터 청구할 주차 요금을 차례대로 정수 배열에 담아서 return 하도록 solution 함수를 완성해주세요.
제한사항
-
fees의 길이 = 4
- fees[0] = 기본 시간(분)
- 1 ≤ fees[0] ≤ 1,439
- fees[1] = 기본 요금(원)
- 0 ≤ fees[1] ≤ 100,000
- fees[2] = 단위 시간(분)
- 1 ≤ fees[2] ≤ 1,439
- fees[3] = 단위 요금(원)
- 1 ≤ fees[3] ≤ 10,000
-
1 ≤ records의 길이 ≤ 1,000
- records의 각 원소는 "시각 차량번호 내역" 형식의 문자열입니다.
- 시각, 차량번호, 내역은 하나의 공백으로 구분되어 있습니다.
- 시각은 차량이 입차되거나 출차된 시각을 나타내며, HH:MM 형식의 길이 5인 문자열입니다.
- HH:MM은 00:00부터 23:59까지 주어집니다.
- 잘못된 시각("25:22", "09:65" 등)은 입력으로 주어지지 않습니다.
- 차량번호는 자동차를 구분하기 위한, `0'~'9'로 구성된 길이 4인 문자열입니다.
- 내역은 길이 2 또는 3인 문자열로, IN 또는 OUT입니다. IN은 입차를, OUT은 출차를 의미합니다.
- records의 원소들은 시각을 기준으로 오름차순으로 정렬되어 주어집니다.
- records는 하루 동안의 입/출차된 기록만 담고 있으며, 입차된 차량이 다음날 출차되는 경우는 입력으로 주어지지 않습니다.
- 같은 시각에, 같은 차량번호의 내역이 2번 이상 나타내지 않습니다.
- 마지막 시각(23:59)에 입차되는 경우는 입력으로 주어지지 않습니다.
- 아래의 예를 포함하여, 잘못된 입력은 주어지지 않습니다.
- 주차장에 없는 차량이 출차되는 경우
- 주차장에 이미 있는 차량(차량번호가 같은 차량)이 다시 입차되는 경우
입출력 예
| fees | records | result |
|---|---|---|
[180, 5000, 10, 600] | ["05:34 5961 IN", "06:00 0000 IN", "06:34 0000 OUT", "07:59 5961 OUT", "07:59 0148 IN", "18:59 0000 IN", "19:09 0148 OUT", "22:59 5961 IN", "23:00 5961 OUT"] | [14600, 34400, 5000] |
[120, 0, 60, 591] | ["16:00 3961 IN","16:00 0202 IN","18:00 3961 OUT","18:00 0202 OUT","23:58 3961 IN"] | [0, 591] |
[1, 461, 1, 10] | ["00:00 1234 IN"] | [14841] |
입출력 예 설명
입출력 예 #2
- 요금표
| 기본 시간(분) | 기본 요금(원) | 단위 시간(분) | 단위 요금(원) |
|---|---|---|---|
| 120 | 0 | 60 | 591 |
- 입/출차 기록
| 시각(시:분) | 차량 번호 | 내역 |
|---|---|---|
| 16:00 | 3961 | 입차 |
| 16:00 | 0202 | 입차 |
| 18:00 | 3961 | 출차 |
| 18:00 | 0202 | 출차 |
| 23:58 | 3961 | 입차 |
- 자동차별 주차 요금
| 차량 번호 | 누적 주차 시간(분) | 주차 요금(원) |
|---|---|---|
| 0202 | 120 | 0 |
| 3961 | 120 + 1 = 121 | 0 +⌈(121 - 120) / 60⌉x 591 = 591 |
나의 풀이
package programmers;
import java.time.Duration;
import java.time.LocalTime;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;
public class ParkingFee {
public static int[] solution(int[] fees, String[] records) {
Map<String, ArrayList<String>> dbMap = new TreeMap<>() ;
for(int i = 0; i< records.length; i++) {
String carNumber = records[i].split(" ")[1];
String timeRecord = records[i].split(" ")[0];
if(!dbMap.containsKey(carNumber)) {
dbMap.put(carNumber, new ArrayList<>());
}
dbMap.get(carNumber).add(timeRecord);
}
System.out.println(dbMap);
for(ArrayList<String> times : dbMap.values()) {
if(times.size() % 2 != 0) {
times.add("23:59");
}
}
Map<String, Integer> durationMap = new TreeMap<>();
for(String carNumber : dbMap.keySet()) {
ArrayList<String> times = dbMap.get(carNumber);
int totalMin = 0;
for(int i = 0; i < times.size(); i +=2) {
LocalTime inTime = LocalTime.parse(times.get(i));
LocalTime outTime = LocalTime.parse(times.get(i+1));
Duration duration = Duration.between(inTime, outTime);
totalMin += (int) duration.toMinutes();
}
durationMap.put(carNumber, totalMin);
}
System.out.println(durationMap);
int[] answer = new int[durationMap.size()];
int index = 0;
for(String carNumber : durationMap.keySet()) {
int parkedMin = durationMap.get(carNumber);
System.out.println(parkedMin);
if (parkedMin <= fees[0]) {
answer[index++] = fees[1];
} else {
answer[index++] = fees[1] + (int) Math.ceil((double)(parkedMin - fees[0]) / fees[2]) * fees[3];
}
}
System.out.println(Arrays.toString(answer));
return answer;
}
public static void main(String[] args) {
int[] fees = {180, 5000, 10, 600};
String[] records = {"05:34 5961 IN", "06:00 0000 IN", "06:34 0000 OUT", "07:59 5961 OUT", "07:59 0148 IN", "18:59 0000 IN",
"19:09 0148 OUT", "22:59 5961 IN", "23:00 5961 OUT"};
solution(fees, records);
}
}
나의 생각
문제를 보면서 실제 주차장 시스템은 어떤 구조로 동작하는지 궁금해졌다. 내가 찾아본 주차 시스템은 다음과 같다.
- 센서와 카메라
- 주차장의 출입구에 설치된 센서와 카메라가 차량의 출입을 감지
- 차량이 입장할 때, 카메라는 번호판을 읽어서 차량 번호를 인식, 번호판 인식 기술(
Number Plate Recognition, NRP)을 사용하여 차량 번호와 함께 현재 시각을 데이터로 저장
- 주차장 서버 및 DB
- 감지된 차량의 정보(차량번호, 시각, 입/출차 정보 등)는 주차장의 중앙 서버나 DB에 전송
- 서버는 차랑의 입/출차 정보를 DB에 저장하며, 차량이 출차할 때 해당 차량의 입차 시간과 출차 시간을 바탕으로 주차 요그름 계산함
- 요금 결제 시스템
- 차량이 출차하려고 할 때, 요금 결제 시스템이 해당 차량의 주차 요금을 알려줌
- 사용자는 주차 요금을 결제한 후에 주차장을 빠져나갈 수 있음. 결제 방법은 현금, 카드, 모바일 결제 등 다양함
+-------------------+ +-----------------+ +--------------------+
| 센서 & 카메라 |<--->| 서버 |<--->| 데이터베이스 |
+-------------------+ +-----------------+ +--------------------+
^
|
+-------------------+
| 결제 터미널 |
+-------------------+
^
|
+-------------------+
| 관리자 인터페이스 |
+-------------------+
본론으로 들어와, 문제에서 주어진 매개변수를 어떻게 처리할 것인가를 중점으로 생각하였다.
int[] fees = {180, 5000, 10, 600};
String[] records = {"05:34 5961 IN", "06:00 0000 IN", "06:34 0000 OUT", "07:59 5961 OUT", "07:59 0148 IN", "18:59 0000 IN",
"19:09 0148 OUT", "22:59 5961 IN", "23:00 5961 OUT"};매개변수로 주어진 records는 하나의 index에 시간, 번호판, 내역을 포함하고 있으며,를 기준으로 데이터를 달리한다. 여기서 내가 생각했던 방법은 다음과 같다.
1. Map으로 key : 번호판, value는 출입 시간을 리스트로 관리할 것
2. value의 size가 홀수이면 ( 즉, 데이터가 1개 또는 3개, 5개... 로 존재할 때),
이는 OUT 시간이 명시가 안되어있다는 뜻으로, 무조건 11:59의 시간으로 계산할 것
3. 그리고 key값이 오름차순으로 정렬될 것이를 적용한 로직은 다음과 같다.
Map<String, ArrayList<String>> dbMap = new TreeMap<>() ;
for(int i = 0; i< records.length; i++) {
String carNumber = records[i].split(" ")[1];
String timeRecord = records[i].split(" ")[0];
if(!dbMap.containsKey(carNumber)) {
dbMap.put(carNumber, new ArrayList<>());
}
dbMap.get(carNumber).add(timeRecord);
}Map을 사용할때 key값을 오름차순으로 정렬하기 위해서 TreeMap<>()을 사용하면 간단히 이를 구현할 수 있다. carNumber & timeRecord는 공백을 기준으로 05:34 5961 IN과 같은 값을 가지는데 split(" ")[0] : 05:34, split(" ")[1] : 5961, split(" ")[2] : IN의 값을 가진다. 그리고 dbMap에 해당하는 carNumber이 있으면 value값만 추가되며, key가 없으면 key와 value(new ArrayList<>())를 추가한다. 마지막으로 map에 해당 carNumber에 대한 출입 시간을 추가하면 끝이다.
여기서 짚고 넘어가야할 부분이 carNumber = 0000 일때, value(출차시간 기록) 이 홀수 개로 존재하는데 이때 마지막 값에 11:59을 추가해줘야 우리가 원하는 데이터로 이용가치가 생긴다.
for(ArrayList<String> times : dbMap.values()) {
if(times.size() % 2 != 0) {
times.add("23:59");
}
}이를 위해 dbMap의 value값을 기준으로 순회를 돌아 times의 size() % 2결과가 0이 아니면 홀수이기 때문에 23:59을 추가하여 최종적인 데이터 형태를 만들수 있다.
여기서 한번 더 필터 작업을 거쳐야하는데, 우리는 출입(IN - OUT) 시간이 필요한 것이 아니라 총 머물렀던 시간이 필요한 것이다. 즉 OUT시간 - IN시간의총 합이 필요한 것이다.
{0000=334, 0148=670, 5961=146}이렇게 값을 구해야하는데 주차장에 주차한 총 합(분)은 어떻게 구할 것인가??
자바에서는 날짜와 시간을 관리하는 API가 존재하는데 LocalTime을 사용하면 입출입 Duration을 구할 수 있다.
Map<String, Integer> durationMap = new TreeMap<>();
for(String carNumber : dbMap.keySet()) {
ArrayList<String> times = dbMap.get(carNumber);
int totalMin = 0;
for(int i = 0; i < times.size(); i +=2) {
LocalTime inTime = LocalTime.parse(times.get(i));
LocalTime outTime = LocalTime.parse(times.get(i+1));
Duration duration = Duration.between(inTime, outTime);
totalMin += (int) duration.toMinutes();
}
durationMap.put(carNumber, totalMin);
}새로운 durationMap을 할당하고 dbMap.keySet()을 기준으로 순회를 돌아 List times에 이를 담으면 된다.
여기서 index 0을 기준으로 +2를 하면 IN 시간만 검출할 수 있고, OUT 시간은 i+1을 통해 자동적으로 계산이 가능하다.
java.time.Duration은 새로운 날짜와 시간 API의 일부로,
두 시점 사이의 시간 차이(시간, 분, 초, 나노초)를 나타내는 클래스다.
between(Temporal startInclusive, Temporal endExclusive):
두 시간 객체 사이의 시간 차이를 Duration 객체로 반환한다. 
이를 carNumber을 기준으로 duration을 추가하면,
이 된다.
int[] answer = new int[durationMap.size()];
int index = 0;
for(String carNumber : durationMap.keySet()) {
int parkedMin = durationMap.get(carNumber);
if (parkedMin <= fees[0]) {
answer[index++] = fees[1];
} else {
answer[index++] = fees[1] + (int) Math.ceil((double)(parkedMin - fees[0]) / fees[2]) * fees[3];
}
}마지막 로직은 int[] answer 에 duration 과 int[] fees = {180, 5000, 10, 600} 계산 로직으로 fees[0] 은 기본시간, fees[1]은 기본요금, fees[2]은 추가시간, fees[3]은 추가요금으로 이 관계식이 위 로직에 포함된다.
Math.ceil() : 올림
Math.floor() : 내림각 차량 3대(0000, 0148, 5961)에 대한 요금은 다음과 같다
더 맵게
📑 문2) 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 +
(두 번째로 맵지 않은 음식의 스코빌 지수 * 2)Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.
제한사항
- scoville의 길이는 2 이상 1,000,000 이하입니다.
- K는 0 이상 1,000,000,000 이하입니다.
- scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
- 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.
입출력 예
| scoville | K | return |
|---|---|---|
[1,2,3,9,10,12] | 7 | 2 |
입출력 예 설명
-
스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
가진 음식의 스코빌 지수 =[5, 3, 9, 10, 12] -
스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
가진 음식의 스코빌 지수 =[13, 9, 10, 12]
모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.
나의 풀이
런타임에러 발생 코드
package programmers;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
public class MoreSpicy {
public static int solution(int[] scoville, int K) {
int mixCount = 0;
ArrayList<Integer> scovilleList = new ArrayList<>();
for (int s : scoville) {
scovilleList.add(s);
}
while (scovilleList.size() > 1) {
Collections.sort(scovilleList);
if (scovilleList.get(0) >= K) {
return mixCount;
}
int first = scovilleList.get(0);
int second = scovilleList.get(1);
int mixScoville = first + (second * 2);
scovilleList.remove(0);
scovilleList.remove(0);
scovilleList.add(mixScoville);
mixCount++;
}
if (scovilleList.get(0) < K) {
return -1;
}
return mixCount;
}
public static void main(String[] args) {
int[] scoville = {1, 2, 3, 9, 10, 12};
solution(scoville, 7);
}
}
내 로직의 문제점
1. 자료구조의 선택 : 나의 코드에서는 ArrayList를 사용하고 있으며, 이후에 Collections.sort()로 정렬하는 방식을 취하고 있음.
2. 루프의 조건 : 가장 낮은 스코빌 지수를 가진 음식과 두 번째로 낮은 스코빌 지수를 가진 음식을 섞어도 K 미만인 경우, 더 이상 K 이상의 스코빌 지수를 만들 수 없음. 이런 경우를 체크하여 루프를 중단하거나 적절한 값을 반환해야 함
3. 정렬의 비효율성 : 매번 섞은 후에 전체 리스트를 다시 정렬하는 것은 비효율적
4. 코드의 복잡도 : 현재의 구현은 코드의 복잡도가 상대적으로 높음
개선 방향
ArrayList대신 PriorityQueue (우선순위 큐)를 사용하는 것이 더 적합함
1. 우선순위에 따라 요소가 정렬되는 큐
2. 기본적으로 작은 값이 가장 높은 우선순위를 가짐PriorityQueue(우선순위 큐)를 적용한 로직
package programmers;
import java.util.PriorityQueue;
public class MoreSpicy {
public static int solution(int[] scoville, int K) {
int mixCount = 0;
PriorityQueue<Integer> scovilleQueue = new PriorityQueue<>();
for(int a : scoville) {
scovilleQueue.offer(a);
}
while(scovilleQueue.size() > 1 && scovilleQueue.peek() < K) {
int first = scovilleQueue.poll();
int second = scovilleQueue.poll();
int mixScoville = first + (second * 2);
scovilleQueue.offer(mixScoville);
mixCount++;
}
System.out.println(scovilleQueue.peek());
if (scovilleQueue.peek() < K) {
return -1;
}
return mixCount;
}
public static void main(String[] args) {
int[] scoville = {1, 2, 3, 12, 10, 9};
solution(scoville, 7);
}
}
게임 맵 최단거리
📑 문3) ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.
지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.
위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.
- 첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.
- 두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.
위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.
만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.
게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.
제한사항
- maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
- n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
- maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
- 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.
입출력 예
| maps | answer |
|---|---|
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] | 11 |
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] | -1 |
나의 풀이
package programmers;
import java.util.LinkedList;
import java.util.Queue;
public class ShortestPath {
private static final int[][] DIRECTIONS = {{1,0},{-1,0},{0,1},{0,-1}};
public static int solution(int[][] maps) {
int n = maps.length;
int m = maps[0].length;
Queue<int[]> queue = new LinkedList<>();
boolean[][] visited = new boolean[n][m];
queue.offer(new int[] {0,0,1});
visited[0][0] = true;
while(!queue.isEmpty()) {
int[] current = queue.poll();
int x = current[0];
int y = current[1];
int distance = current[2];
for(int[] direction : DIRECTIONS) {
int nextX = x + direction[0];
int nextY = y + direction[1];
if(nextX == n - 1 && nextY == m - 1) {
return distance + 1;
}
if(nextX >= 0 && nextX < n && nextY >= 0 && nextY < m &&
maps[nextX][nextY] == 1 && !visited[nextX][nextY]) {
queue.offer(new int[]{nextX, nextY, distance + 1});
visited[nextX][nextY] = true;
}
}
}
return -1;
}
public static void main(String[] args) {
int[][] maps = {{1,0,1,1,1},{1,0,1,0,1},{1,0,1,1,1},{1,1,1,0,1},{0,0,0,0,1}};
solution(maps);
}
}
나의 생각
BFS (Breadth First Search) 구현 로직
-
시작 위치에서 가까운 위치부터 차례대로 탐색
-
BFS는 최단 경로 문제에서 자주 사용되며, Queue는 BFS를 구현하는데 필수적인 자료 구조
BFS와 DFS의 특징
| BFS (Breadth-First Search, 너비 우선 탐색) | DFS (Depth-First Search, 깊이 우선 탐색) | |
|---|---|---|
| 특징 | ||
| 가까운 노드부터 탐색 | O | |
| 큐(Queue)를 사용 | O | |
| 재귀 또는 스택 사용 | O | |
| 한 방향 깊게 탐색 | O | |
| 활용 사례 | ||
| 최단 경로 찾기 | O | |
| 연결 구성 요소 찾기 | O | O |
| 그래프 레벨 찾기 | O | |
| 모든 경로 찾기 | O | |
| 사이클 검출 | O | |
| 차이점 | ||
| 탐색 순서 | 시작 노드에서 가까운 노드부터 | 한 방향으로 깊게 들어가 탐색 |
| 사용하는 자료구조 | 큐(Queue) | 스택(Stack) 또는 재귀 |
| 시간 복잡도 | O(V+E) | O(V+E) |
| 공간 복잡도 | 일반적으로 DFS보다 더 많은 메모리 사용 | BFS보다 상대적으로 적은 메모리 사용 |
| 결과의 특성 | 시작 노드로부터의 최단 경로를 보장 | 최단 경로를 보장하지 않음 |
매개변수로 주어지는 int[][] maps = {{1,0,1,1,1},{1,0,1,0,1},{1,0,1,1,1},{1,1,1,0,1},{0,0,0,0,1}} 값을 바탕으로 map의 row, col 의 크기를 알 수 있다.
int n = maps.length; // row
int m = maps[0].length; // colBFS의 핵심 요소로 Queue를 선언하여 queue에 저장된 값을 차례로 순회를 돌아, 동서남북 네 방향을 모두 체크하여 목적지까지 도달하는 방법을 사용한다.
Queue<int[]> queue = new LinkedList<>();
boolean[][] visited = new boolean[n][m];
queue.offer(new int[] {0,0,1});
visited[0][0] = true;queue 처음 값은 map의 시작지점을 의미하며 마지막 값 1은 거리(distance)를 나타낸다.
visited boolean 변수는 해당하는 좌표에 방문을 했는지를 체크하기 위함이다.
따라서 시작지점을 true로 시작한다.
private static final int[][] DIRECTIONS = {{1,0},{-1,0},{0,1},{0,-1}}
- 동서남죽 네 방향을 나타내는
DIRECTIONS는 불변값을 가져야하기때문에final로 선언함으로써 배열이 한 번 초기화된 후에는 수정되지 않도록 보장하기 위함이다. static으로 선언하면 클래스 로드 시에 한 번만 메모리에 할당되며,solution메서드가 호출될 때마다 생성되지않는다. 즉, 메모리 사용과 초기화 오버헤드를 줄일 수 있다.- 클래스 레벨에서 상수를 선언하면 해당 상수가 클래스 전체에서 사용되는 중요한 요소임을 나타낸다.
while(!queue.isEmpty()) {
int[] current = queue.poll();
int x = current[0];
int y = current[1];
int distance = current[2];
for(int[] direction : DIRECTIONS) {
int nextX = x + direction[0];
int nextY = y + direction[1];
if(nextX == n - 1 && nextY == m - 1) {
return distance + 1;
}
if(nextX >= 0 && nextX < n && nextY >= 0 && nextY < m &&
maps[nextX][nextY] == 1 && !visited[nextX][nextY]) {
queue.offer(new int[]{nextX, nextY, distance + 1});
visited[nextX][nextY] = true;
}
}
}위 로직을 BFS의 동작 원리를 기반으로 설명하면
1. 초기화
- 큐에 시작 위치인 (0,0)과 시작 지점에서의 거리 1을 넣는다.
-> queue.offer(new int[]{0,0,1};
- visited[0][0]을 true로 설정하여 시작 지점을 방문한 것으로 표시
2. while(!queue.isEmpty())
- 큐에서 첫 번째 위치와 거리를 꺼낸다.
-> int[] current = queue.poll();
- 꺼낸 위치를 기반으로 4방향(DIRECTIONS)을 확인하며 다음 위치를 결정
3. 4방향 확인
- 현재 위치 (x,y)에서 4방향을 확인하며 이동할 위치 nextX, nextY를 계산
- 이때, 계산된 (nextX, nextY)가 배열의 범위 내에 있고,
아직 방문하지 않은 위치이며, 그 위치의 값이 1인 경우만 처리
4. 목적지 확인
- (nextX, nextY)가 목적지 (n-1, m-1)인 경우, 현재 거리 +1을 반환 후 종료
5. 큐에 추가
- 위의 조건에 만족하는 (nextX, nextY)를 큐에 추가하며, 해당 위치를 방문한 것으로 표시
- 이때, 거리 값은 distance + 1로 설정하여 큐에 함께 저장
6. 반복
- 위 과정을 큐가 isEmpty()가 될 때까지 반복
7. 큐가 비게되면?
- 만약 큐가 비게 되면 목적지에 도달할 수 없다는 의미이므로, -1을 반환1 0 1 1 1
1 0 1 0 1
1 0 1 1 1
1 1 1 0 1
0 0 0 0 1
동작과정
1. 시작 위치 (0,0), 거리 1을 큐에 삽입
2. (0,0)에서 이동 가능한 위치 (1,0)을 큐에 삽입
3. (1,0)에서 이동 가능한 위치 (2,0)을 큐에 삽입
4. (2,0)에서 이동 가능한 위치 (3,0)을 큐에 삽입
5. (3,0)에서 이동 가능한 위치 (3,1)을 큐에 삽입
6. (3,1)에서 이동 가능한 위치 (3,2)를 큐에 삽입
7. (3,2)에서 이동 가능한 위치 (2,2)를 큐에 삽입
8. (2,2)에서 이동 가능한 위치 (1,2)과 (2,3)을 큐에 삽입
9. (1,2)에서 이동 가능한 위치 (0,2)를 큐에 삽입 / 현재 큐 (2,3), (0,2)
10. (2,3)에서 이동 가능한 위치 (2,4)를 큐에 삽입/ 현재 큐 (0,2), (2,4)
11. (0,2)에서 이동 가능한 위치 (0,3)을 큐에 삽입/ 현재 큐 (2,4), (0,3)
12. (2,4)에서 이동 가능한 위치 (3,4)와(1,4)를 큐에 삽입/ 현재 큐 (0,3), (3,4), (1,4)
13. (0,3)에서 이동 가능한 위치 (0,4)를 큐에 삽입/ 현재 큐 (3,4),(1,4),(0,4)
14. (3,4)에서 이동 가능한 위치 (4,4)이며, 이 위치는 도착지점이므로 distance + 1을 리턴모음 사전
📑 문4) 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.
단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.
제한사항
- word의 길이는 1 이상 5 이하입니다.
- word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.
입출력 예
| word | result |
|---|---|
AAAAE | 6 |
AAAE | 10 |
I | 1563 |
EIO | 1189 |
입출력 예 설명
입출력 예 #1
- 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA", "AAA", "AAAA", "AAAAA", "AAAAE", ... 와 같습니다. "AAAAE"는 사전에서 6번째 단어입니다.
입출력 예 #2
- "AAAE"는 "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAE", "AAAAI", "AAAAO", "AAAAU"의 다음인 10번째 단어입니다.
나의 풀이
package programmers;
import java.util.ArrayList;
public class VowelDictionary {
final static char[] WORDS = {'A','E','I','O','U'};
final static int MAX_SIZE = 5;
public static int solution(String word) {
int answer = 0;
ArrayList<String> elements = new ArrayList<>();
for(int i = 0; i < WORDS.length; i++) {
if(dfs(elements, String.valueOf(WORDS[i]),word)){
break;
}
}
for(int i = 0; i < elements.size(); i++) {
if(elements.get(i).equals(word)) {
answer = i + 1;
break;
}
}
return answer;
}
public static boolean dfs(ArrayList<String> elements, String str, String target) {
if(str.length() > MAX_SIZE) return false;
System.out.println(str);
if(!elements.contains(str)) {
elements.add(str);
}
if(str.equals(target)) {
return true;
}
for(int i = 0; i < WORDS.length; i++) {
if (dfs(elements, str+WORDS[i], target)) {
return true;
}
}
return false;
}
public static void main(String[] args) {
solution("AAAAE");
}
}
나의 생각
땅따먹기
📑 문5) 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.
예를 들면,
| 1 | 2 | 3 | 5 |
|---|---|---|---|
| 5 | 6 | 7 | 8 |
| 4 | 3 | 2 | 1 |
로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.
마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.
제한사항
- 행의 개수 N : 100,000 이하의 자연수
- 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
- 점수 : 100 이하의 자연수
입출력 예
| land | answer |
|---|---|
[[1,2,3,5],[5,6,7,8],[4,3,2,1]] | 16 |
나의 풀이
런타임 발생 코드 (실패)
package programmers;
public class EatingTheLand {
static final int MAX_SIZE = 4;
public static int solution(int[][] land) {
int answer = 0;
int landScore = 0;
for(int i = 0; i < land.length; i++) {
int first = land[i][0];
int index = 0;
for(int j = 1; j < MAX_SIZE; j++) {
if(first < land[i][j]) {
first = land[i][j];
index = j;
}
}
landScore += first;
if( i == 2) {
continue;
}else {
land[i+1][index] = 0;
}
}
System.out.println(landScore);
return answer;
}
public static void main(String[] args) {
int[][] land = {{1,2,3,5},{5,6,7,8},{4,3,2,1}};
solution(land);
}
}
동적 계획법(Dynamic Programming)을 적용한 로직
package programmers;
public class EatingTheLand {
public static int solution(int[][] land) {
int N = land.length;
for (int i = 1; i < N; i++) {
land[i][0] += Math.max(land[i-1][1], Math.max(land[i-1][2], land[i-1][3]));
land[i][1] += Math.max(land[i-1][0], Math.max(land[i-1][2], land[i-1][3]));
land[i][2] += Math.max(land[i-1][0], Math.max(land[i-1][1], land[i-1][3]));
land[i][3] += Math.max(land[i-1][0], Math.max(land[i-1][1], land[i-1][2]));
}
return Math.max(land[N-1][0], Math.max(land[N-1][1], Math.max(land[N-1][2], land[N-1][3])));
}
public static void main(String[] args) {
int[][] land = {{1,2,3,5},{5,6,7,8},{4,3,2,1}};
solution(land);
}
}
