s를 함부로 split 하게 되는 경우 주어진 s 중 3People__abc 와 같은 경우 두 번 띄어쓰기를 처리하는데 어려움을 겪었다. 따라서 StringBuilder를 이용하여 i일 때 i-1 인덱스가 " "인 경우 대문자로 변환해주었다. 이 때 StringBuilder의 setCharAt()을 이용하여 i번 째 char형을 쉽게 바꿀 수 있었으며 Character.toUpperCase()를 이용하여 해당 char를 대문자로 바꿀 수 있다.
* StringBuilder의 setCharAt(int i, char c) : StringBuilder 변수의 i번째 index의 character를 c로 바꿔준다.
Character.toUpperCase(char c) : c를 대문자로 Character.toLowerCase(char c) : c를 소문자로
코드
//JadenCase 문자열 만들기
class Solution {
public String solution(String s) {
String answer = "";
s = s.toLowerCase();
StringBuilder sb = new StringBuilder(s);
for(int i=0; i<s.length(); i++){
if(s.charAt(i) == ' '){
continue;
}
if(i==0)
sb.setCharAt(i, Character.toUpperCase(s.charAt(i)));
else if(i>0){
if(s.charAt(i-1) == ' ')
sb.setCharAt(i, Character.toUpperCase(s.charAt(i)));
}
}
answer = new String(sb);
return answer;
}
}
처음에는 전체 집List, 전체 치킨집List와 visited 배열을 사용하여 전체 치킨집 중 M개를 DFS 와 백트래킹을 이용하여 구현하였다. 하지만 거리를 구하는 과정에서 전체 집에서 전체 치킨집을 돌면서 M개에 포함되지 않는 경우도 조건을 통해 거르다 보니 시간 초과가 났다.
그래서 다음에는 visited 배열을 빼고 선택된 치킨집List를 만들어 M개 만큼 선택된 치킨집 List를 만들어서 거리를 구하였더니 맞출 수 있었다.
나머지 부분은 크게 어렵지 않은 부분이여서 생략한다.
코드 (시간 초과)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
// 치킨 배달
// NxN 도시
// 1x1 칸 (0:빈칸, 1:집, 2:치킨집)
// (r, c) r,c는 1부터 시작
// 치킨 거리 : 집과 가장 가까운 치킨집 사이의 거리
// 도시의 치킨 커리는 모든 집의 치킨 거리의 합
// 치킨집 갯수 M개
// M개 이외 치킨집 폐업, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램
public class Main {
static int N; // 도시 크기 NxN(2~50)
static int M; // 최대 치킨집 갯수(1~13)
static int[][] map;
static List<int[]> hList = new ArrayList<>(); // 전체 집 위치
static List<int[]> cList = new ArrayList<>(); // 전체 치킨 집 위치
static boolean[] visited;
static int min = Integer.MAX_VALUE; // 가장 작은 도시의 치킨 거리
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str;
str = br.readLine();
N = Integer.parseInt(str.split(" ")[0]);
M = Integer.parseInt(str.split(" ")[1]);
map = new int[N+1][N+1];
StringTokenizer st;
for(int i=1; i<N+1; i++) {
str = br.readLine();
st = new StringTokenizer(str, " ");
for(int j=1; j<N+1; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
// 집 리스트
if(map[i][j] == 1) {
hList.add(new int[] {i, j});
}
// 치킨집 리스트
else if(map[i][j] == 2) {
cList.add(new int[] {i, j});
}
}
}
visited = new boolean[cList.size()];
// ==== 입력 끝 =====
dfs(0);
System.out.println(min);
}
// 치킨집이 M만큼 있는 경우의 치킨 거리 탐색
static void dfs(int depth) {
// 치킨 집이 M만큼 있는 경우
if(depth >= M) {
int distanceSum = 0;
int minDistance;
int distance;
// 각 집에서 M에 포함되는 치킨집들 중 가장 짧은 치킨 거리구하기
for(int i=0; i<hList.size(); i++) {
minDistance = Integer.MAX_VALUE;
distance = 0;
for(int j=0; j<cList.size(); j++) {
// M에 포함된 치킨집
if(visited[j]) {
distance = Math.abs(hList.get(i)[0]-cList.get(j)[0]) + Math.abs(hList.get(i)[1]-cList.get(j)[1]);
minDistance = Math.min(distance, minDistance);
}
}
distanceSum += minDistance;
}
// 가장 작은 도시의 치킨 거리 구하기
min = Math.min(min, distanceSum);
}
else {
// M과 치킨집 갯수가 같으면 폐업되는 치킨 집 없음
if(M == cList.size()) {
for(int i=0; i<cList.size(); i++) {
visited[i] = true;
}
dfs(M);
}
// list에서 치킨집 M만큼 고르기
else {
for(int i=0; i<cList.size(); i++) {
if(!visited[i]) {
visited[i] = true;
dfs(depth+1);
visited[i] = false;
}
}
}
}
}
}
코드 (합격)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
// 치킨 배달
// NxN 도시
// 1x1 칸 (0:빈칸, 1:집, 2:치킨집)
// (r, c) r,c는 1부터 시작
// 치킨 거리 : 집과 가장 가까운 치킨집 사이의 거리
// 도시의 치킨 커리는 모든 집의 치킨 거리의 합
// 치킨집 갯수 M개
// M개 이외 치킨집 폐업, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램
public class Main {
static int N; // 도시 크기 NxN(2~50)
static int M; // 최대 치킨집 갯수(1~13)
static int[][] map;
static List<int[]> hList = new ArrayList<>(); // 전체 집 위치
static List<int[]> cList = new ArrayList<>(); // 전체 치킨 집 위치
static List<int[]> selected = new ArrayList<>(); // 선택된 치킨집
static int min = Integer.MAX_VALUE; // 가장 작은 도시의 치킨 거리
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str;
str = br.readLine();
N = Integer.parseInt(str.split(" ")[0]);
M = Integer.parseInt(str.split(" ")[1]);
map = new int[N+1][N+1];
StringTokenizer st;
for(int i=1; i<N+1; i++) {
str = br.readLine();
st = new StringTokenizer(str, " ");
for(int j=1; j<N+1; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
// 집 리스트
if(map[i][j] == 1) {
hList.add(new int[] {i, j});
}
// 치킨집 리스트
else if(map[i][j] == 2) {
cList.add(new int[] {i, j});
}
}
}
// ==== 입력 끝 =====
dfs(0,0);
System.out.println(min);
}
// 치킨집이 M만큼 있는 경우의 치킨 거리 탐색
static void dfs(int idx, int depth) {
// 치킨 집을 M만큼 고른 경우
if(depth >= M) {
int distanceSum = 0;
int minDistance;
int distance;
// 각 집에서 M에 포함되는 치킨집들 중 가장 짧은 치킨 거리구하기
for(int i=0; i<hList.size(); i++) {
minDistance = Integer.MAX_VALUE;
distance = 0;
for(int j=0; j<selected.size(); j++) {
// M에 포함된 치킨집
distance = Math.abs(hList.get(i)[0]-selected.get(j)[0]) + Math.abs(hList.get(i)[1]-selected.get(j)[1]);
minDistance = Math.min(distance, minDistance);
}
distanceSum += minDistance;
}
// 가장 작은 도시의 치킨 거리 구하기
min = Math.min(min, distanceSum);
}
else {
// list에서 치킨집 M만큼 고르기
for(int i=idx; i<cList.size(); i++) {
selected.add(cList.get(i));
dfs(i+1, depth+1);
selected.remove(depth);
}
}
}
}
