코테 11/25/19

요새 계속 코테만 보는 것 같은 느낌적인 느낌..

1. 피포나치 재귀 호출로 구해보기

package algo.codingtests.kongstudios;
 
import java.util.Scanner;
 
public class Fibonacci {
 
    public static int fibo(int number) {
        
        if(number == 0) return 0;
        if(number == 1) return 1;
        return fibo(number - 1) + fibo(number - 2);
    }
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int number = scan.nextInt();
        System.out.println(fibo(number));
    }
    
}
 

2. 스트링 순서 바꾸기 version 1

package algo.codingtests.kongstudios;
 
import java.util.Scanner;
 
public class PartialWordReverse {
    
    public static void printWords(String str) {
        
        int i = 0;
        for(; i < str.length() && str.charAt(i) != ' '; i++) {
            System.out.print(str.charAt(i));
        }
        
        String words = "";
        for(; i < str.length(); i++) {
            if(str.charAt(i) != ' ') {
                words += str.charAt(i);
            } else {
                System.out.print(new StringBuilder(words).reverse().toString() + " ");
                words = "";
                
            }
            
        }
        
        System.out.print(words);
    }
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String str = scan.nextLine();
        System.out.println(str);
        System.out.println(new StringBuilder(str).reverse().toString());
        System.out.println("=============");
        
        printWords(str);
        
    }
}
 

 version1 에서는 앞 단어와 그리고 맨 뒤 단어는 정상적으로 출력이되고 중간 단어들은 순서를 바꿔서 출력하기

 

version2

package algo.codingtests.kongstudios;
 
import java.util.Scanner;
 
public class PartialWordReverseVowl {
    
    public static boolean isVowel(char c) {
        return (c == 'a' || c == 'A' || c == 'e'
                || c == 'E' || c == 'i' || c == 'I'
                || c == 'o' || c == 'O' || c == 'u'
                || c == 'U');
    }
    
    public static String partialWorrdReverse(String str) {
        int i = 0; 
        int j = str.length() - 1; 
        char[] str1 = str.toCharArray(); 
        while (i < j) { 
            if (!isVowel(str1[i])){ 
                i++; 
                continue; 
            } 
            if (!isVowel(str1[j])){ 
                j--; 
                continue; 
            } 
      
            char temp = str1[i]; 
            str1[i]= str1[j]; 
            str1[j]= temp; 
      
            i++; 
            j--; 
        } 
       ; 
        return String.valueOf(str1); 
    }
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String str = scan.nextLine();
        System.out.println(partialWorrdReverse(str));
    }
}
 

버젼2에서는 모음만 비교해서 바꿔주기

 

3. Stack를 사용해서 Queue방식 출력

package algo.codingtests.kongstudios;
 
import java.util.Stack;
 
public class QueueSolution {
 
    private Stack<Integer> s1 = new Stack<>();
    private Stack<Integer> s2 = new Stack<>();
    int front = 0;
 
    // Push element x to the back of queue.
    public void push(int x) {
        if (s1.empty())
            front = x;
        s1.push(x);
    }
    
    public void pop() {
        if (s2.isEmpty()) {
            while (!s1.isEmpty())
                s2.push(s1.pop());
        }
        s2.pop();    
    }
    
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
    
    public int peek() {
        if (!s2.isEmpty()) {
                return s2.peek();
        }
        return front;
    }
    public static void main(String[] args) {
        QueueSolution solution = new QueueSolution();
        solution.push(1);
        solution.push(2);
        solution.push(3);
        solution.push(4);
        solution.push(5);
        
        System.out.println(solution.peek());
    
        
    }
}
 

stack은 lifo 방식이기때문에 push했을때 원래는 5 4 3 2 1순서되로 출력이되야하지만 

push, pull, peek, empty의 조건들을 바꿔서 1이먼저 출력!

 

4. Implementing queue using stack

package algo.codingtests.kongstudios;
 
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
 
public class QueueUsingStack {
 
    public static void main(String[] args) {
        QueueStack qs = new QueueStack();
        qs.stack1 = new Stack<Integer>();
        qs.stack2 = new Stack<Integer>();
        qs.enQueue(qs, 1);
        qs.enQueue(qs, 2);
        qs.enQueue(qs, 3);
        
        System.out.println(qs.deQueue(qs));
        System.out.println(qs.deQueue(qs));
        System.out.println(qs.deQueue(qs));
        
        System.out.println("=================");
        System.out.println("using queue example");
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < 5; i++) {
            q.add(i);
        }
        
        for(Integer e : q) {
            System.out.println(e);
        }
        
        q.remove();
        System.out.println(q.peek());
    }
}
 

package algo.codingtests.kongstudios;
 
import java.util.Stack;
 
public class QueueStack {
 
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    
    public void push(Stack<Integer> qs, int n) {
        qs.push(n);
    }
    
    public int pop(Stack<Integer> qs) {
        if(qs.isEmpty()) {
            System.out.println("Nothing is in");
            System.exit(0);
        }
        int x = qs.pop();
        return x;
    }
    public void enQueue(QueueStack qs, int n) {
        push(qs.stack1, n);
    }
    
    public int deQueue(QueueStack qs) {
        int x = 0;
        
        if(qs.stack1.isEmpty() && qs.stack2.isEmpty()) {
            System.out.println("queue is empty");
            System.exit(0);
        }
        if(qs.stack2.isEmpty()) {
            while(!qs.stack1.isEmpty()) {
                x = pop(qs.stack1);
                push(qs.stack2, x);
            }
        }
        x = pop(qs.stack2);
        return x;
    }
}
 

queue의 enqueue 랑 dequeue사용

솔직히 이해는 조금 부족함

 

5. Two Sum Method

package algo.codingtests.kongstudios;
 
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Vector;
 
public class TwoSumMethods {
 
    public static int[] bruteForce(int[] numbers, int target) {
 
        for (int i = 0; i < numbers.length; i++) {
            for (int j = 0; j < numbers.length; j++) {
                if (numbers[i] + numbers[j] == target) {
                    return new int[] { i, j };
                }
            }
        }
        return new int[] {};
    }
 
    public static int[] sortedMethod(int[] numbers, int target) {
        
        Arrays.sort(numbers);
        int left = 0;
        int right = numbers.length - 1;
        while(left < right) {
            System.out.println(numbers[left] + numbers[right]);
            if(numbers[left] + numbers[right] == target) {
                return new int[] {left, right};
            } else if(numbers[left] + numbers[right] < target) {
                left++;
                System.out.println("left +");
            } else {
                right--;
                System.out.println("right -");
            }
        }
        return new int[] {};
    }
 
    public static int[] hashMethod(int[] numbers, int target) {
        Map<Integer, Integer> numMap = new HashMap<>();
        for(int i = 0; i < numbers.length; i++) {
            int complement = target - numbers[i];
            if(numMap.containsKey(complement)) {
                return new int[] {numMap.get(complement), i};
            } else {
                numMap.put(numbers[i], i);
            }
        }
        return new int[] {};
    }
    
//    public static Vector<Integer> twoSum(Vector<Integer> nums, int target) {
//        Vector<Integer> vec = new Vector<Integer>(100);
//        for(Integer e : nums) {
//            System.out.println(e);
//        }
//        for(int i = 0; i < nums.size(); i++) {
//            int complement = target - nums.get(i);
//            if(vec.contains(complement)) {
//                Vector<Integer> vecs = new Vector<Integer>();
//                vecs.add(0, vec.get(complement));
//                vecs.add(1, i);
//                return vecs;
//            } else {
//                vec.add(nums.get(i), i);
//            }
//        }
//        return new Vector<Integer>();
//    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        
        int[] numbers = new int[n];
        for (int i = 0; i < n; i++) {
            numbers[i] = scan.nextInt();
        }
//        Vector<Integer> numbers = new Vector<Integer>();
//        for (int i = 0; i < n; i++) {
//            numbers.add(i, scan.nextInt());
//        }
        int target = scan.nextInt();
//        twoSum(numbers, target);
//        System.out.println("asdfasdfsd");
//        for(Integer e : twoSum(numbers, target)) {
//            System.out.println(e);
//        }
//
        int[] result = hashMethod(numbers, target);
 
        
        if (result.length == 2) {
            System.out.println(result[0] + "    " + result[1]);
        } else {
            System.out.println("found no results");
        }
    }
}
 

6. Happy Number

package algo.codingtests.kongstudios;
 
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
 
public class HappyNumber {
 
    public static int checkSquare(int n) {
        int squareNum = 0;
        while(n != 0) {
            squareNum += (n % 10) * (n % 10);
            n /= 10;
        } 
        return squareNum;
    }
    
    public static boolean isHappyNumber(int n) {
        Set<Integer> st = new HashSet<Integer>();
        System.out.println("number before is " + n);
        while(st.add(n)) {
//            n = checkSquare(n);
            int squareNum = 0;
            while(n != 0) {
                squareNum += (n % 10) * (n % 10);
                n /= 10;
            } 
            n = squareNum;
            System.out.println("after check is " + n);
        }
        return (n == 1);
    }
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        System.out.println(isHappyNumber(n) ? "happy":"not happy");
    }
}
 

 

 

코테 하면서 오늘 새로운것들 많이 배웠다

stack queue사용법, happy number algo, two sum algo 그리고 string reverse조건으로 결정하기