journey

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

입출력 예

ticketsreturn

입출력 예 설명

예제 #1

["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.

예제 #2

["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.

#풀이

	class Solution {

		//티켓체크여부
		boolean[] check;
		//티켓순서가 담긴 리스트를 담을 리스트
		ArrayList<LinkedList<String>> result;

		public String[] solution(String[][] tickets) {
			String[] answer = {};

			check = new boolean[tickets.length];
			result = new ArrayList<>();
			for (int i = 0; i < tickets.length; i++) {
				//문제조건:시작티켓은 ICN
				if (tickets[i][0].equals("ICN")) {
					//arr:티켓순서를 담을 배열
					String[] arr = new String[tickets.length + 1];
					//ICN으로 시작하는 티켓들(tickets[i][0])을 배열 첫요소로 넣음
					arr[0] = tickets[i][0];
					//ICN으로 시작하는 티켓 방문처리
					check[i] = true;
					func(i, tickets, arr, 0);
					//방문처리초기화
					Arrays.fill(check, false);
				}
			}

			for (int i = 0; i < result.size(); i++) {
				if (result.get(i).size() != tickets.length + 1) {
					result.remove(i);
				}
			}

			if (result.size() > 1) {
				Collections.sort(result, new Comparator<LinkedList<String>>() {
					@Override
					public int compare(LinkedList<String> o1, LinkedList<String> o2) {
						int order = 0;
						for (int i = 0; i < o1.size(); i++) {
							if (o1.get(i).compareTo(o2.get(i)) == 0) {
								continue;
							} else {
								order = o1.get(i).compareTo(o2.get(i));
								break;
							}
						}
						return order;
					}

				});
			}
			answer = result.get(0).toArray(new String[result.get(0).size()]);
			return answer;

		}

		//now:현재티켓 tickets:티켓배열 arr:티켓순서저장배열 cnt:현재까지탐색한 티켓수
		private void func(int now, String[][] tickets, String[] arr, int cnt) {
			//티켓순서가 담긴 배열
			if (tickets.length == cnt + 1) {
				/* 따로 temp(LinkedList)를 func의 매개변수로 넣지 않고, arr배열을 넣은 이유
				 * 탐색하면서 계속 그 티켓순서가 바뀌기 때문에, LinkedList자체에 담으면 수정하기 어려움
				 * 따라서 수정하기쉬운 배열자체에 데이터를 담은 후, 종결조건때 임시리스트에 담은 후
				 * 그 임시리스트만 정답리스트에 넣음 
				 * */
				LinkedList<String> temp = new LinkedList<String>();
				for (int i = 0; i <= cnt + 1; i++) {
					temp.add(arr[i]);
				}
				result.add(temp);
				return;
			}

			for (int i = 0; i < tickets.length; i++) {
				/* 현재티켓(now)의 도착지와 다음티켓(i)의 출발지같음 &&
				 * 현재티켓(now)과 다음티켓(i)은 다름(for문이 now도 탐색하기때문) &&
				 * 다음티켓(i)이 방문되지않음
				 */
				if (tickets[now][1].compareTo(tickets[i][0]) == 0 && i != now && !check[i]) {
					arr[cnt + 1] = tickets[i][0];
					arr[cnt + 2] = tickets[i][1];
					check[i] = true;
					func(i, tickets, arr, cnt + 1);
					check[i] = false;
				}
			}
			return;

		}
	}

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

begintargetwordsreturn

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

#풀이

class Solution {

		int MIN = 100;
		boolean[] check;

		public int solution(String begin, String target, String[] words) {
			int answer = 0;
			check = new boolean[words.length];

			boolean isTarget = false;
			for (String s : words) {
				if (s.compareTo(target) == 0) {
					isTarget = true;
					break;
				}
			}
			if (!isTarget) {
				return 0;
			}

			func(begin, 0, target, words);
			answer = MIN;
			return answer;
		}

		void func(String str, int count, String target, String[] words) {

			if (str.compareTo(target) == 0 && count < MIN) {
				MIN = count;
				return;
			}

			for (int i = 0; i < words.length; i++) {
				int different = 0;
				for (int j = 0; j < str.length(); j++) {
					if (str.charAt(j) != words[i].charAt(j)) {
						different++;
					}
				}
				if (different == 1 && !check[i]) {
					check[i] = true;
					func(words[i], count + 1, target, words);
					check[i] = false;
				} else {
					continue;
				}

			}

		}
	}

dfs메서드의 for문에 different 변수를 넣었다. dfs가 매개변수로 받은 String과, 배열에 있는 다른 String과 비교해서 각 위치의 철자가 다를 경우 different를 증가시켰다. 이 때 different 가 1일경우, 즉 철자가 한개만 다를경우에 해당 String을 dfs의 다음 매개변수로 넣는다.

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

입출력 예

ncomputersreturn

입출력 예 설명

예제 #1
아래와 같이 2개의 네트워크가 있습니다.

예제 #2
아래와 같이 1개의 네트워크가 있습니다.

#풀이

import java.util.List;
import java.util.LinkedList;
import java.util.ArrayList;
	

class Solution {

		boolean[] check;
		ArrayList<LinkedList<Integer>> result;

		public int solution(int n, int[][] computers) {

			result = new ArrayList<>();
			check = new boolean[computers[0].length];

			for (int i = 0; i < computers.length; i++) {
				if (!check[i]) {
					LinkedList<Integer> list = new LinkedList<Integer>();
					result.add(list);
					dfs(i, computers, list);
				}
			}

			return result.size();
		}

		void dfs(int idx, int[][] computers, LinkedList<Integer> list) {

			// 해당 idx를 탐색함
			check[idx] = true;
			for (int i = 0; i < computers.length; i++) {
				if (i != idx && !check[i] && computers[idx][i] == 1) {
					list.add(i);
					dfs(i, computers, list);
				}
			}
			return;

		}

	}

boolean배열, ArrayList, LinkedList를 사용할 것이다.

boolean배열 : 해당 요소가 그룹에 편입되어있으면 해당요소의 boolean을 조정하는 역할

LinkedList : 그룹

ArrayList : 각 그룹(LinkedList)를 저장할 리스트

check[i]가 false일 경우(아직 그룹에 편입하지 않음) 새로운 그룹을 만들고, 이 그룹(LinkedList)를 리스트(ArrayList)에 넣어준다. 이 후 DFS를 진행한다.

DFS는 매개변수로 각 요소의 인덱스(idx), 문제에서 주어진 요소별관계를 나타낸배열(computers), 그룹(list)를 받는다. 이후 해당 idx에서 check[idx]를 방문처리한 후, for문을 돌린다. 

if문의 조건은 dfs메서드에서 매개변수로 받은 idx(현재 본인의 인덱스)를 제외 && i인덱스를 아직 방문하지않음 && idx와 i의 연결관계임

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

numberstargetreturn

입출력 예 설명

문제에 나온 예와 같습니다.

#풀이

class Solution {
		int size;
		int result;
		int answer;
		int[] arr;
		boolean[] check;

		public int solution(int[] numbers, int target) {

			size = numbers.length;
			result = target;
			arr = numbers;
			check = new boolean[size];

			answer = dfs(0, 0);

			return answer;
		}

		// deepth:깊이 num,result:target arr:배열 size:갯수(arr크기)
		int dfs(int depth, int num) {
			if (depth == size) {
				if (result == num) {
					return 1;
				} else {
					return 0;
				}
			}

			int answer = 0;
			answer += dfs(depth + 1, num - arr[depth]);
			answer += dfs(depth + 1, num + arr[depth]);

			return answer;

		}
	}

기존 배열 numbers를 보호하기 위해서 arr이라는 배열을 선언한 후 값을 모두 복사해준다. 그리고 DFS를 돌리면 된다.

문제 설명

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
  • m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

입출력 예

mnpuddlesreturn

입출력 예 설명

#풀이

class Solution {
		int[][] dp;

		public int solution(int m, int n, int[][] puddles) {

			dp = new int[m + 1][n + 1];

			for (int i = 0; i < puddles.length; i++) {
				dp[puddles[i][0]][puddles[i][1]] = -1;
			}

			dp[1][1] = 1;
			for (int i = 1; i <= m; i++) {
				for (int j = 1; j <= n; j++) {
					if (dp[i][j] == -1) {
						continue;
					}
					if (j > 1 && dp[i][j - 1] != -1) {
						dp[i][j] += dp[i][j - 1] % 1000000007;
					}
					if (i > 1 && dp[i - 1][j] != -1) {
						dp[i][j] += dp[i - 1][j] % 1000000007;
					}
				}
			}

			return dp[m][n] % 1000000007;
		}

	}

DFS재귀로 풀면 계속 시간초과가 나게되었다. 생각보다 간단하게 풀이가 가능했다. 먼저 DP배열을 만들고, 인덱스에 쉽게 접근하기 위해서 주어진 m, n보다 1씩 크게 이차원배열dp를 선언한다. 물웅덩이가 있는 곳은 -1을, 아닌곳은 0으로 초기화된다. 그 후 여느 DP문제와 마찬가지로, 현재의 배열요소의 값에 그 이전의 배열요소의 값을 더하면서 차근차근 키워가는 방식이다.

문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예

triangleresult

#풀이

class Solution {
		int[][] org;
		int[][] dp;

		public int solution(int[][] triangle) {
			org = triangle;
			dp = triangle.clone();

			for (int i = triangle.length - 2; i >= 0; i--) {
				make(dp, i);
			}

			int answer = dp[0][0];
			return answer;
		}

		void make(int[][] dp, int depth) {

			for (int i = 0; i < dp[depth].length; i++) {
				dp[depth][i] = org[depth][i] + Math.max(org[depth + 1][i], org[depth + 1][i + 1]);
			}

		}
	}

Bottom-up방식으로 풀이했다. 맨 밑변부터 탐색하고, 위로올라갈수록 밑 두 수 중 큰 수와 더한값을 dp에 넣었다.

예를 들어 위 그림에서 맨 밑 변 첫번째와 두번째 수  4 와 5중 5가 크다. 그 5값이 채택되고,  위의 2값과 더하여 7이된다. 이 7의 값을 새로운 dp배열에서 2의 위치(4번째줄 첫번째)에 넣는다. 이런식으로 점점 올라가게된다.

문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

Nnumberreturn

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

#풀이

class Solution {

		int answer = -1;

		public int solution(int N, int number) {

			cal(N, number, 0, 0);

			return answer;
		}

		void cal(int N, int number, int count, int result) {


			if (count > 8) {
				answer = -1;
				return;
			}
			if (result == number) {
				if (answer == -1 || answer > count) {
					answer = count;
				}
				return;
			}

			int dN = N;
			// i : 자릿수증가(따라서 count도 상응하게증가)
			// count가 8초과면 안되기때문(count + i + 1 < 9)
			for (int i = 0; i < 8 - count; i++) {

				cal(N, number, count + i + 1, result + dN);
				cal(N, number, count + i + 1, result - dN);
				if (result != 0) {
					cal(N, number, count + i + 1, result * dN);
					cal(N, number, count + i + 1, result / dN);
				}
				dN = dN * 10 + N;
			}

		}

	}

DFS를 이용했고, 재귀호출할 때 for문안에 자릿수를 증가하는 로직도 넣어주었다.(dN = dN * 10 + N) 여기서 i가 자릿수를 의미하기때문에(2 : i=0, 22 : i = 1, 222: i = 2) 재귀호출 할 때 count에 i+1을 더해준다. 그리고 사칙연산에 따라 재귀호출을 하게 두고, for문 조건에서 8 - count은 이유는 count가 8초과하면 안되기 때문이다. 8 - count를 풀어쓰면 '재귀호출에서 count값에 (count + i + 1)을 넣는데, 이 값이 8보다 작아야하기 때문에' 이다.

문제 설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

입출력 예

brownyellowreturn

#풀이

class Solution {
		public int[] solution(int brown, int yellow) {
			int[] answer = new int[2];

			int sqrt = (int) Math.sqrt(yellow);
			int width = sqrt;
			int length = sqrt;

			while (width >= 1 && length >= 1) {
				if (width * length > yellow) {
					length--;
					continue;
				} else if (width * length < yellow) {
					width++;
					continue;
				} else {
					if (brown == width * 2 + length * 2 + 4) {
						answer[0] = width + 2;
						answer[1] = length + 2;
						break;
					}
				}
			}

			return answer;

		}

	}

먼저, 노란색타일의 제곱근을 구한다. width 와 length에 값을 넣어준다. 이 후 이 곱(총갯수)가 주어진 yellow보다 크면 length를 하나씩 감소시키고, 작으면 width를 하나씩 증가시킨다(문제에서 가로>=세로). 만약에 yellow와 같다면, yellow의 가로세로를 알아낸 것이다. 이후 추론한 것이 정확한것인지 확인하려면 brown의 갯수까지 확인하는 과정을 거치고나면 답이 나온다.