"+", "-" 없이 주어지 두 수의 합계를 구하는 문제이다. 비트 연산자를 이용하여 해결해야 한다.
십진수를 더할 때 자리수 별로 더하고 다음 자릿수로 넘겨서 더해주는 방식에 착안해서 해결해보았다. "^" 연산자를 사용해서 0과 1의 합계를 더해주고, "&" 연산자를 사용해서 1과 1의 합계 부분을 구한 이후 자릿수 올리기를 반복해주었다. 최종 코드는 아래와 같이 하여 통과하였다.
public class Solution {
public int getSum(int a, int b) {
while(b != 0){
int temp = a;
a = a ^ b;
b = b & temp;
b = b << 1;
}
return a;
}
}
주어진 구간의 사이즈에 대하여 주어진 쿼리 값이 포함되는 구간 중 가장 작은 구간을 찾는 문제이다. 다양한 방식으로 문제 풀이를 시도하다 시간 초과를 통과하지 못했다. 문제의 Discussion 부분을 참조하여 다른 사람들의 의견들을 보던 중 세그먼트 트리 알고리즘에 대해 알게 되었다.
관련하여 블로그들을 보며 공부했다. 해당 알고리즘은 특정 구간의 대한 값들을 구간 기준으로 저장하는 트리에 대한 내용이었다. 루트 노드를 전체 구간으로, 자식 노드는 mid 값을 기준으로 구간을 반씩 나누며 구간에 대한 값을 저장하는 방식이었다. 해당 문제에선 주어진 구간의 size 값을 저장하고 최소 값을 기준으로 답을 찾아야 했기에 해당 알고리즘을 이용하여 풀이해 보았다.
트리의 구간은 문제에서 주어진 최대값을 기준으로 트리를 구성한 이후, 세그먼트 트리를 수정 하는 메서드, 값을 찾는 메서드를 완성해주었다. 이 후 아래의 코드를 완성하여 통과 할 수 있었다.
import java.util.*;
public class Solution {
int[] sgTree;
public int[] minInterval(int[][] intervals, int[] queries) {
int min = 1;
int max = 10_000_000;
int treeSize = (max - min) * 4;
sgTree = new int[treeSize];
Arrays.fill(sgTree, max);
for(int[] interval : intervals){
int left = interval[0];
int right = interval[1];
int size = right - left + 1;
updateTree(1, min, max, left, right, size);
}
int[] answer = new int[queries.length];
for(int i = 0; i < queries.length; i++){
int size = queryTree(1, min, max, queries[i]);
answer[i] = size == max ? -1 : size;
}
return answer;
}
private void updateTree(int index, int start, int end, int left, int right, int size){
if(right < start || left > end){
return;
}
if(start >= left && end <= right){
sgTree[index] = Math.min(sgTree[index], size);
return;
}
int mid = start + (end - start) / 2;
updateTree(index * 2 ,start, mid, left, right, size);
updateTree(index * 2 + 1, mid + 1, end, left, right, size);
}
private int queryTree(int index, int start, int end, int find){
if((start == end)){
return sgTree[index];
}
int result = sgTree[index];
int mid = start + (end - start) / 2;
if(mid >= find){
result = Math.min(result, queryTree(index * 2, start, mid, find));
}else{
result = Math.min(result, queryTree(index * 2 + 1, mid + 1, end, find));
}
return result;
}
}
하지만 문제를 통과한 이후에 속도가 다른 정답에 비해 떨어지는 것을 확인했다. 다른 솔루션들을 확인할 결과 세그먼트 트리를 사용하지 않는 방식이 더욱 효율적이었다. 각 구간의 값과 쿼리의 값 모두 최소값으로 정렬하고 PriorityQueue를 통하여 하나씩 뽑는 방식이었다. 해당 코드의 방식은 아래와 같다.
class Solution {
public int[] minInterval(int[][] intervals, int[] queries) {
int[][] reorderQueries = new int[queries.length][2];
for(int i = 0; i < queries.length; i++) {
reorderQueries[i][0] = queries[i];
reorderQueries[i][1] = i;
}
Arrays.sort(reorderQueries, (a, b) -> a[0] - b[0]);
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> (a[1] - a[0]) - (b[1] - b[0]));
int i = 0;
int[] results = new int[queries.length];
Arrays.fill(results, -1);
for(int[] query : reorderQueries) {
while(i < intervals.length && query[0] >= intervals[i][0]) {
queue.offer(intervals[i]);
i++;
}
while(!queue.isEmpty() && queue.peek()[1] < query[0]) {
queue.poll();
}
if(!queue.isEmpty()) {
results[query[1]] = queue.peek()[1] - queue.peek()[0] + 1;
}
}
return results;
}
}
비록 문제는 비효율적으로 풀었으나, 세그먼트 트리라는 새로운 알고리즘을 공부할 수 있었다.
주어진 문자열이 패턴에 맞는 문자열인지 확인하는 문제이다. 주어지는 패턴은 '.' 일 경우 같은 모든 문자에 대칭 되고, '*' 일 경우 앞 글자 하나와 함께 묶여 해당 문자가 여러 개 가능하다는 뜻이다. DP로 해결이 가능하고 이전에 풀었던 다른 문제들의 경험 덕분에 풀 수 있었다. 아래의 두 문제와 점화식을 만들어 가는 방식이 비슷하다.
각 문자의 부분 문자열을 기반으로 DP 배열의 초기화와 점화식을 세워줄 수 있다. 특정 문자열 s의 인덱스 j 와 패턴 p의 문자열 i일 때를 생각해 보자. "." 또는 각 문자가 해당 인덱스에서 같을 경우 dp 배열의 true,false 값은 (i - 1)(j - 1)의 값과 같다. 왜냐하면 각 글자가 추가 되기 전에 같았다면 새로운 글자가 똑같이 생긴 경우이기 때문이다. 그리고 각 글자가 다를 경우 당연히 false가 된다.
별이 있는 패턴의 경우 해당 패턴의 i - 1 일 때의 값이 참인 경우에 참이 된다. 패턴의 새로운 문자열과 별개로 참이기 때문이다. 또한 j - 1 이 참일 경우 별문자의 문자값과 j의 문자값이 같을 경우 참이 된다. 그 이전까지의 문자가 패턴에 부합할 때 별 문자의 문자 새로 생겼다고 판단할 수 있기 때문이다. 아래에 임의의 값을 가지고 True, False 값을 찾아가는 배열을 만든 경우이다. i인 row가 늘어나는 경우를 패턴, j인 col이 늘어나는 경우가 문자열을 나타낸다.
""
a
b
b
e
""
T
F
F
F
F
a
F
T
F
F
F
*b
F
T
T
T
F
e
F
F
F
T
T
g
F
F
F
F
F
확인해 보아야 하는 관계는 각 글자가 같을 때 (i - 1). (j - 1)의 값을 참조 해야 한다는 것, 별패턴일 경우엔 (i - 1)의 값과 문자가 같을 때 (j - 1)의 값을 참조 해야 한다는 점이다.
해당 규칙을 이용해서 최종적으로 통과한 코드는 아래와 같다. 별표의 경우 문자 + 별로 두 글자의 인덱스를 차지하므로 대문자로 치환하여 비교문을 작성했다.
주어진 문자열을 주어진 사전 안의 있는 단어로 분해할 수 있는지 물어보는 문제이다. 최초 문제 풀이시 DFS로 시도하였으나 시간 초과가 발생하였다. DP 카테고리의 문제이므로 DP로 풀어볼 아이디어를 찾았다.
주어진 문자열을 한글자씩 늘려 i번재 글자 까지가 분해할 수 있는지 확인해 가는 방식으로 했다. dp[i]를 특정 위치에서 양쪽으로 나눈다면 왼쪽과 오른쪽이 모두 분해 가능할 때 dp[i] 또한 분해 가능하다고 할 수 있다. 따라서 dp[i]에서의 값을 확인하기 위해서 i 까지의 각 위치 j를 기준으로 하여 왼쪽 구간이 분해 가능한지 기존 dp배열에서 확인한 후 뒷 구간은 사전 내에서 찾아보았다. 글자 수를 늘리면서 dp배열을 확인해 왔기 때문에 0번 인덱스에서 j 번 인덱스까지는 확인되고 저장되어 있기 때문에 빠른 속도로 체크가 가능하다. 아래는 최종적으로 통과한 코드이다.
import java.util.*;
public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for(int i = 0; i < dp.length; i++){
for(int j = 0; j <= i; j++){
if(dp[j] == true){
String check = s.substring(j, i);
if(wordDict.contains(check)){
dp[i] = true;
break;
}
}
}
}
return dp[s.length()];
}
}
주어진 티켓을 모두 사용해서 여행 계획을 짜는 문제이다. 이 때 완성된 여행 일정의 문자의 사전 순서가 빠른 순서인 것이 최종 정답이다.
문자의 속도가 중요하여 PriorityQueue를 이용해서 BFS를 처음에 시도했다. 하지만 시간 초과에 걸려 다른 방법들을 시도하다가 결국 정답 정보를 찾아보게 되었다. 사전 순서를 지키기 위해 PriorityQueue를 이용하고 DFS를 하는 방식이었다. 이 때 각 티켓, 사전 순으로 순환 하고 순환이 완료 된 이후에는 정답 리스트에 문자열을 추가한다.
PriorityQueue 에서 poll 하면서 순환하기 때문에 DFS 메서드에 최종 진입한 역은 다음 그래프가 없기 때문에 정답에 바로 추가 된다. 이처럼 메서드가 재귀적으로 역순 순환될 때 완료한 순서대로 정답이 추가된다. 이 때 역순으로 되기 때문에 addFirst 함수를 이용해서 역으로 정답에 담아 리턴 했다. 아래는 최종 통과 코드이다.
import java.util.*;
public class Solution {
List<String> answer;
public List<String> findItinerary(List<List<String>> tickets) {
Map<String, PriorityQueue<String>> graphs = new HashMap<>();
answer = new ArrayList<>();
int ticketCnt = 0;
for(List<String> ticket: tickets){
String from = ticket.get(0);
String to = ticket.get(1);
if(!graphs.containsKey(from)){
graphs.put(from, new PriorityQueue<>());
}
graphs.get(from).add(to);
}
dfs("JFK", graphs);
return answer;
}
private void dfs(String airport, Map<String, PriorityQueue<String>> graphs){
PriorityQueue<String> graph = graphs.get(airport);
while(graph != null && !graph.isEmpty()){
dfs(graph.poll(), graphs);
}
answer.addFirst(airport);
}
}
시작 단어부터 끝 단어까지 한 글자씩 변경할 때 몇 회에 변경 가능한지 묻는 문제이다. 이 때 변경 가능한 문자열은 리스트로 주어진다.
문제를 해결하기 위해서 BFS를 사용하여 해결하였다. 최소 거리를 묻는 문제이기 때문에 가까운 거리 부터 체크하는 BFS가 적절하고, 그래프의 형태는 각 글자를 각 알파벳으로 변경했을 때 주어진 리스트에 있는지로 확인해서 순차적으로 확인할 수 있다. 이 때 방문 체크는 문자열로 해야 하기 때문에 Set을 이용해 주었다.
import java.util.*;
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Queue<Object[]> que = new ArrayDeque<>();
Set<String> isExist = new HashSet<>();
que.add(new Object[]{beginWord, 1});
wordList.forEach(word -> isExist.add(word));
int answer = 0;
while(!que.isEmpty()){
Object[] info = que.poll();
String str = (String)info[0];
int cnt = (int)info[1];
if(cnt > wordList.size() + 1){
return answer;
}
if(str.equals(endWord)){
answer = cnt;
break;
}
char[] charArr = str.toCharArray();
for(int i = 0; i < charArr.length; i++){
char save = charArr[i];
for(int j = 0; j < 26; j++){
charArr[i] = (char)(j + 'a');
String next = new String(charArr);
if(isExist.contains(next) && (charArr[i] != save)){
que.add(new Object[]{next, cnt + 1});
isExist.remove(next);
}
}
charArr[i] = save;
}
}
return answer;
}
}
주어진 사전의 단어를 이용하여 주어진 문장 내의 문자열을 사전 속 단어로 변경하는 문제이다. Trie 자료구조를 이용할 수 있다. 주어진 사전의 단어들을 저장한 이후, 문장 내에서 해당 단어를 prefix로 갖고 있는 단어들을 교환해준다. 단어를 검사하며 길이를 확인하고 substring 하여 문자열을 대체해주었다.
import java.util.*;
public class Solution {
public String replaceWords(List<String> dictionary, String sentence) {
Trie root = new Trie();
for(String word: dictionary){
Trie head = root;
for(int i = 0; i < word.length(); i++){
char c = word.charAt(i);
if(head.next[c - 'a'] == null){
head.next[c - 'a'] = new Trie();
}
head = head.next[c - 'a'];
if(i == word.length() - 1){
head.isLast = true;
}
}
}
String[] sentenceArr = sentence.split(" ");
for(int i = 0; i < sentenceArr.length; i++){
String word = sentenceArr[i];
Trie head = root;
int length = 0;
for(int j = 0; j < word.length(); j++){
char c = word.charAt(j);
if(head.next[c - 'a'] == null) break;
head = head.next[c - 'a'];
length++;
if(head.isLast){
sentenceArr[i] = word.substring(0, length);
break;
}
}
}
StringBuilder sb = new StringBuilder();
for(String word: sentenceArr){
sb.append(word);
sb.append(" ");
}
return sb.toString().trim();
}
private static class Trie{
Trie[] next;
boolean isLast;
Trie(){
next = new Trie[26];
isLast = false;
}
}
}
체스판에 모든 퀸이 서로 공격할 수 없는 위치에 두는 방법을 묻는 문제이다. 퀸은 가로, 세로, 대각선으로 자유롭게 움직일 수 있으므로 해당 위치에 대한 방문 체크를 해주며 백트래킹을 하면 풀 수 있다. 가로, 세로, 대각선을 방문 체크하기 위해서 각 8방향의 배열을 만들어서 while문으로 해당 방향을 체크해주었다. 또한 row의 수는 n 이므로 row마다 퀸이 하나 씩 놓인다는 사실을 알 수 있다. 그러므로 0번 row에서 마지막 row까지 방문 체크를 하며 탐색 할 수 있다면 해당 문제의 조건에 부합하는 경우라는 것을 체크할 수 있다. 아래는 최종적으로 통과한 코드이다.
import java.util.*;
public class Solution {
final String QUEEN = "Q";
final String EMPTY = ".";
int[] dr = {0, 1, 0, -1, 1, 1, -1, -1};
int[] dc = {1, 0, -1, 0, 1, -1, 1, -1};
boolean[][] visited;
List<List<String>> answer;
int n;
public List<List<String>> solveNQueens(int n) {
this.n = n;
answer = new ArrayList<>();
visited = new boolean[n][n];
for(int col = 0; col < n; col++){
visited[0][col] = true;
dfs(0, col);
visited[0][col] = false;
}
return answer;
}
private void dfs(int row, int col){
if(invalid(row, col)){
return;
}
int nextRow = row + 1;
if(nextRow == n){
List<String> result = new ArrayList<>();
StringBuilder resultRow = new StringBuilder();
for(int i = 0; i < n; i++){
for(int j = 0; j < visited.length; j++){
String value = visited[i][j] ? QUEEN : EMPTY;
resultRow.append(value);
}
result.add(resultRow.toString());
resultRow.setLength(0);
}
answer.add(result);
return;
}
for(int nextCol = 0; nextCol < n; nextCol++){
if(!visited[nextRow][nextCol]){
visited[nextRow][nextCol] = true;
dfs(nextRow, nextCol);
visited[nextRow][nextCol] = false;
}
}
}
private boolean invalid(int row, int col){
for(int i = 0; i < dr.length;i ++){
int nextRow = row + dr[i];
int nextCol = col + dc[i];
while(nextRow >= 0 && nextRow < n
&& nextCol >= 0 && nextCol < n){
if(visited[nextRow][nextCol]) return true;
nextRow = nextRow + dr[i];
nextCol = nextCol + dc[i];
}
}
return false;
}
}