myBlog

> 문제설명

leetcode.com/problems/vowel-spellchecker/

문제 내용을 요약하자면 다음과 같다.

목표 String배열 wordlist와 질의 String배열 queries가 주어졌을 때, 각 질의 String배열을 다음과 같은 연산을 통해 정답 String배열을 return하면 된다.

1. 목표 String과 질의 String이 완벽히 일치하면 그대로 정답 배열에 추가.

2. 대소문자에 관계없이 일치하는 경우, 목표 String배열중 가장 앞의 String을 정답 배열에 추가.

3. 대소문자에 관계없이 vowel(모음, [AaEeIiOoUu])이 위치와 개수 상관 없이 다른 경우, 모음을 제외한 자음이 모두 일치하는 String을 목표 String배열의 가장 앞쪽에서 찾아 정답 배열에 추가.

4. 위 경우가 아닌 경우 빈 String을 정답 배열에 추가.

> Solution

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashSet;

class Solution {
    public String[] spellchecker(String[] wordlist, String[] queries) {
        LinkedHashSet<String> wordSet = new LinkedHashSet<>();
        HashMap<String, String> vowelMap = new HashMap<>();
        HashMap<String, String> upperMap = new HashMap<>();

        for(String word : wordlist){
            wordSet.add(word);
            upperMap.putIfAbsent(word.toUpperCase(), word);
            vowelMap.putIfAbsent(word.replaceAll("[AaEeIiOoUu]", "*").toUpperCase(), word);
        }

        ArrayList<String> ansList = new ArrayList<>();
        for(String query : queries){
            if(wordSet.contains(query)) {
                ansList.add(query);
                continue;
            }

            if(upperMap.containsKey(query.toUpperCase())){
                ansList.add(upperMap.get(query.toUpperCase()));
                continue;
            }

            String str = query.replaceAll("[AaEeIiOoUu]", "*");
            if(vowelMap.containsKey(str.toUpperCase())){
                ansList.add(vowelMap.get(str.toUpperCase()));
                continue;
            }

            ansList.add("");
        }
        return ansList.toArray(new String[0]);
    }
}

문제 설명 보기

leetcode.com/problems/reordered-power-of-2/

> Desc

입력된 숫자의 자리를 자유롭게 교체해 2의 제곱 승 꼴의 숫자로 만들수 있는지 물어보는 문제다.

>IDEA

1. 숫자의 위치를 자유롭게 바꾼다.

순열 (Permutation)

2. 2의 제곱 승 꼴의 숫자

비트연산자 활용

>Solution(Permutation)

class Solution {
    boolean permutation(String prefix, String str){
        if(str.length() == 0) {
            if ((Integer.parseInt(prefix) | Integer.highestOneBit((Integer.parseInt(prefix))) )== Integer.highestOneBit((Integer.parseInt(prefix)))) return true;
        }
        for(int idx = 0; idx < str.length(); idx++){
            if (!prefix.startsWith("0")) {
                if (permutation(prefix + str.charAt(idx), str.substring(0, idx) + str.substring(idx + 1)))
                    return true;
            }
        }
        return false;
    }

    public boolean reorderedPowerOf2(int N) {
        String str = String.valueOf(N);
        return permutation("", str);

    }
}

> Result

대충 어떻게 시간초과를 면했는지 모르겠다.

그래서 모범답안을 컨닝해봤다.

class Solution {
    public boolean reorderedPowerOf2(int N) {
        int[] A = count(N);
        for (int i = 0; i < 31; ++i)
            if (Arrays.equals(A, count(1 << i)))
                return true;
        return false;
    }

    // Returns the count of digits of N
    // Eg. N = 112223334, returns [0,2,3,3,1,0,0,0,0,0]
    public int[] count(int N) {
        int[] ans = new int[10];
        while (N > 0) {
            ans[N % 10]++;
            N /= 10;
        }
        return ans;
    }
}

2의 제곱승 꼴의 숫자를 10진수로 표현했을 경우, 사용된 각 자릿수의 숫자의 개수를 세어 비교한다.

문제 설명 보기

programmers.co.kr/learn/courses/30/lessons/49191

> IDEA

A -> B이며 B->C라면, A->C가 성립되는 단방향 그래프에서, 다른 모든 정점과 연결된 정점의 개수를 구하는 문제입니다.

모든 정점에서부터 모든 정점까지 도착하는 경우의 수를 모두 세어야 함으로 플로이드 워셜 알고리즘을 통해 해당 문제가 진짜로 표현하고자 하는 그래프를 그린 다음, 다른 정점과 연결이 안되어있는 정점을 제외하며 답을 세어줍니다.

간선의 가중치가 없으므로 boolean형 인접행렬로 그래프를 표현합니다.

> Solution (Floyd-Warchall)

class Solution {
    public int solution(int n, int[][] results) {
        boolean[][] fw = new boolean[n][n];

        for(int[] intArr : results){
            fw[intArr[0]-1][intArr[1]-1] = true;
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                for(int k = 0; k < n; k++){
                    if(fw[j][i]&& fw[i][k]) fw [j][k] = true;
                }
            }
        }

        int answer = 0;

        for(int i = 0; i < n; i++){
            boolean bl = false;
            for(int j = 0; j < n; j++){
                if(i==j) continue;
                if(fw[i][j] == false && fw[j][i] == false){
                    bl = true;
                    break;
                }
            }
            if(!bl)answer++;
        }

        return answer;
    }
}

>> 문제설명

leetcode.com/problems/keys-and-rooms/

> 0개 이상의 간선을 가진 단일 방향 그래프에서 모든 정점을 탐색할 수 있는지를 묻는 문제입니다.

> BFS, DFS 와 같은 그래프 탐색 알고리즘을 사용하여 모든 정점의 방문 여부를 체크합니다.

> Solution(BFS)

import java.util.Arrays;
import java.util.List;

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        LinkedList<Integer> openList = new LinkedList<>();
        HashSet<Integer> isOpened = new HashSet<>();
        
        isOpened.add(0);
        openList.add(0);

        while (!openList.isEmpty()){
            int size = openList.size();
            for(int i = 0; i < size; i++){
                for(int room : rooms.get(openList.pollFirst())){
                    if(!isOpened.contains(room)){
                        openList.add(room);
                        isOpened.add(room);
                    }
                }
            }
        }

        return isOpened.size() == rooms.size() ? true : false;
    }
}

>> 문제설명

leetcode.com/problems/wiggle-subsequence/

> 일차원 배열로 주어진 input에서, 계차수열이 양수와 음수가 번갈아 나오도록 하는 가장 긴 subSequence를 구하는 문제이다.

> 문제 설명 상, 순서를 바꾸지 않는다면 원소를 0개 이상 제거한 것이 주어진 배열에 대한 subSequence다.

> IDEA

배열에서 이전 숫자보다 현재 숫자가 크면 계차가 양수, 아니면 계차가 음수이므로 현재 숫자와 이전 숫자 비교를 선형으로 진행하였다.

이 과정에서, 숫자가 계속 늘어나는건 계차의 부호가 바뀌지 않기 때문에 isGrowing이라는 Boolean 변수를 선언해 상태를 관리했다.

>Solution

class Solution {
    public int wiggleMaxLength(int[] nums) {
        int ans = 1;
        boolean isGrowing =true;
        if(nums.length < 2) return nums.length;
        for(int idx = 1; idx < nums.length; idx++){
            if(nums[idx] > nums[idx-1]){
                if(isGrowing == false){
                    ans++;
                } else if(ans == 1) ans++;
                isGrowing = true;
            } else if (nums[idx] < nums[idx-1]){
                if(isGrowing == true){
                    ans++;
                } else if(ans == 1) ans++;
                isGrowing = false;
            }
        }
        return ans;
    }
}

>> 문제설명

leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

> 1차원 배열로 주어진 변동하는 주식 가격을 받아 가장 쌀 때 사고, 가장 비쌀때 파는 문제다.

> 주식을 사거나 팔때 수수료가 발생한다.

> IDEA1

문제에서는 현재 상태를 주식을 판 상태(주식을 살 수 있는 상태)와 주식을 산 상태(주식을 사서 들고 있는 상태) 두가지로 분류 할 수 있다.

현재 상태가 가질 수 있는 가장 큰 이익을 저장하며 마지막 상태에서 가질 수 있는 가장 큰 이익값을 반환한다. (동적 계획법)

> Solution

class Solution {
    public int maxProfit(int[] prices, int fee) {
        // Set initial state.
        int sellState = 0;
        int buyState = -prices[0];

        for(int idx = 1; idx < prices.length; idx++){
            sellState = Math.max(
                    sellState // 판 상태 -> 판 상태
                    , prices[idx]-fee+buyState// 산 상태 -> 판 상태
            );
            buyState = Math.max(
                    sellState - prices[idx]// 판 상태 -> 산 상태
                    , buyState // 산 상태 -> 산 상태
            );
        }
        return Math.max(buyState, sellState);
    }
}

> IDEA2

주식 가격으로 생각한다면, 저점에서 사서 고점에 파는걸 반복하면 가장 많은 이득을 가지게 된다.

두개의 변수를 관리한다.

하나는 저점에서 산 주식을 현재 가격에 팔았을때 최대로 가지는 수익.

하나는 전고점 대비 하한가, 즉 매수타이밍의 가격.

두개의 변수를 관리하여 문제를 해결 할 수도 있다.

문제 설명 보기

>>programmers.co.kr/learn/courses/30/lessons/43163

주어진 String 배열 안에서 진행 할 수 있는 Node가 한글자만 다른 String인 탐색 유형의 문제이다.

Queue를 사용한 BFS를 통해 해결했다.

import java.util.HashSet;
import java.util.LinkedList;

class Solution {
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        HashSet<String> isTraveled = new HashSet<>();
        LinkedList<String> nextStr = new LinkedList<>();

        nextStr.add(begin);

        while(!nextStr.isEmpty()){
            int size = nextStr.size();
            for(int i = 0; i < size; i++){
                String str = nextStr.pollFirst();
                if(str.equals(target)) return answer;
                for(String word : words){
                    int cnt = 0;
                    for(int idx = 0; idx < word.length(); idx++){
                        if(str.charAt(idx) == word.charAt(idx)){
                            cnt++;
                        }
                    }
                    if(cnt == str.length()-1 && !isTraveled.contains(word)){
                        isTraveled.add(word);
                        nextStr.add(word);
                    }
                }
            }
            answer++;
        }

        return 0;
    }
}

>> 문제설명

leetcode.com/problems/swapping-nodes-in-a-linked-list/

정말 single linked list에서 2개의 node를 swap하려고 하다가 결국 숫자만 바꾸기로 했다.

객체를 swap하는건 무척 어렵지만 그냥 숫자만 바꾸는건 간단하다.

이대로 통과가 되는걸 보니 문제에서도 이걸 의도한 듯 하다..

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        ArrayList<ListNode> nodeList = new ArrayList<>();
        ListNode next = head;
        while(next != null){
            nodeList.add(next);
            next = next.next;
        }
        int tmp = nodeList.get(k-1).val;
        nodeList.get(k-1).val = nodeList.get(nodeList.size()-k).val;
        nodeList.get(nodeList.size()-k).val = tmp;

        return head;
    }
}