자바 알고리즘 복습 (2)

1. 학급 회장(해쉬)

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int cnt = in.nextInt();
    in.nextLine();
    char[] arr = new char[cnt];
    arr= in.nextLine().toCharArray();
    HashMap<Character, Integer> map = new HashMap<>();
    for(int i=0;i<cnt;i++){
      map.put(arr[i],map.getOrDefault(arr[i],0)+1);
    }
    System.out.println(Solution(cnt, map));
  }
  public static char Solution(int cnt, HashMap<Character, Integer>map){
    char c=' ';
    int max=Integer.MIN_VALUE;
    for(Map.Entry<Character, Integer> entry : map.entrySet()){
      if(entry.getValue()>max){
        max=entry.getValue();
        c=entry.getKey();
      }
    }
    return c;
  }
}

---

2. 아나그램(해쉬)

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    String str1 = in.nextLine();
    String str2 = in.nextLine();
    System.out.println(Solution(str1 ,str2));
  }
  public static String Solution(String str1, String str2){
    String answer ="YES";
    HashMap<Character, Integer> map1 = new HashMap<>();
    HashMap<Character, Integer> map2 = new HashMap<>();
    for(char c : str1.toCharArray()){
      map1.put(c, map1.getOrDefault(c,0)+1);
    }
    for(char c : str2.toCharArray()){
      map2.put(c, map2.getOrDefault(c,0)+1);
    }
    if(map1.equals(map2)){
      return answer;
    }else{
      return "NO";
    }
  }
}

---

3. 매출액의 종류

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int cnt = in.nextInt();
    int k = in.nextInt();
    int[] arr = new int[cnt];
    for(int i=0;i<cnt;i++){
      arr[i]=in.nextInt();
    }
    for(int a :Solution(cnt, k, arr)){
      System.out.print(a+" ");
    }
  }
  public static int[] Solution(int cnt, int k, int[]arr){
    int[] answer = new int[cnt-k+1];
    HashMap<Integer, Integer> set = new HashMap<>();
    for(int i=0;i<k;i++){
      set.put(arr[i], set.getOrDefault(arr[i], 0)+1);
    }
    answer[0]=set.size();
    
    int lt=0;
    for(int i=k;i<cnt;i++){
      set.put(arr[i], set.getOrDefault(arr[i],0)+1);
      set.put(arr[lt], set.get(arr[lt])-1);
      if(set.get(arr[lt])==0) set.remove(arr[lt]);
      answer[lt+1]=set.size();
      lt++;
    }
    return answer;
  }
}

 

---

4. 모든 아나그램 찾기

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    String str1 = in.nextLine();
    String str2 = in.nextLine();
    System.out.println(Solution(str1, str2));
  }
  public static int Solution(String str1, String str2){
    int answer=0;
    HashMap<Character, Integer> map = new HashMap<>();
    HashMap<Character, Integer> map2 = new HashMap<>();
    for(int i=0;i<str2.length();i++){
      char c = str2.charAt(i);
      map.put(c, map.getOrDefault(c,0)+1);
      char c2 = str1.charAt(i);
      map2.put(c2, map2.getOrDefault(c2,0)+1);
    }
    if(map2.equals(map)){
      answer++;
    }

    
    int lt=0;
    for(int i=str2.length();i<str1.length();i++){
      char c = str1.charAt(lt++);
      char c2 = str1.charAt(i);
      map2.put(c, map2.get(c)-1);
      if(map2.get(c)==0) map2.remove(c);
      
      map2.put(c2, map2.getOrDefault(c2, 0)+1);
      if(map2.equals(map)){
        answer++;
      } 
    }
    return answer;
  }
}

 

---

5. K번째 큰 수

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int k = in.nextInt();
    Integer[] arr = new Integer[n];
    for(int i=0;i<n;i++){
      arr[i]=in.nextInt();
    }
//    Arrays.sort(arr, Comparator.reverseOrder());
    System.out.println(Solution(n,k,arr));
  }
  public static int Solution(int n, int k, Integer[]arr){
    int answer=0;
    TreeSet<Integer> set = new TreeSet<>(Comparator.reverseOrder());
    for(int i=0;i<n;i++){
      for(int j=i+1;j<n;j++){
        for(int m=j+1;m<n;m++){
          set.add(arr[i]+arr[j]+arr[m]);
        }
      }
    }

    ArrayList<Integer> list = new ArrayList<>(set);


    if(set.size()<k) return -1;
    else return list.get(k-1);
  }
}

---

1. 올바른 괄호

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    String str = in.nextLine();
    
    System.out.println(Solution(str));
  }
  public static String Solution(String str){
    Stack<Character> stack = new Stack<>();
    for(char c: str.toCharArray()){
      if(!stack.isEmpty() && c==')' && stack.peek() =='('){
        stack.pop();
      }
      else{
        stack.push(c);
      }
    }
    if(stack.isEmpty()){
      return "YES";
    }else{
      return "NO";
    }
  }
}

---

2. 괄호문자 제거

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    String str = in.nextLine();
    System.out.println(Solution(str));
  }
  public static String Solution(String str){
    StringBuilder sb = new StringBuilder();
    Stack<Character> stack = new Stack<>();
    int Lcnt=0;
    int Rcnt=0;
    for(char c: str.toCharArray()){
      if(c=='(') Lcnt++;
      else if(c==')') Rcnt++;
      stack.push(c);
    }
    while(!stack.isEmpty()){
      if(Lcnt==Rcnt&&Character.isLetter(stack.peek())){
        sb.append(stack.pop());
      }else{
        if(stack.peek()==')'){
          stack.pop();
          Rcnt--;
        }else if(stack.peek()=='('){
          stack.pop();
          Lcnt--;
        }else{
          stack.pop();
        }
      }
    }
    return sb.reverse().toString();
  }
}

---

3. 크레인 인형뽑기 (카카오)

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int[][] arr = new int[n+1][n+1];
    for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
        arr[i][j]=in.nextInt();
      }
    }
    int k=in.nextInt();
    int[] moves = new int[k];
    for(int i=0;i<k;i++){
      moves[i]=in.nextInt();
    }
    System.out.println(Solution(n,arr,k,moves));
  }
  public static int Solution(int n,int[][] arr, int k, int[] moves){
    int answer=0;
    Stack<Integer> stack = new Stack<>();
    for(int i=0;i<k;i++){
      int j=1;
      while(j<=n&& arr[j][moves[i]]==0){
        j++;
      }
      if(j<=n){
        int result = arr[j][moves[i]];
        arr[j][moves[i]]=0;
        
        if(!stack.isEmpty()&&stack.peek() == result){
          stack.pop();
          answer+=2;
        }else{
          stack.push(result);
        }
      }
    }
    
    return answer;
  }
}

---

 

4. 후위식 연산

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    String str = in.nextLine();
    System.out.println(Solution(str));
  }
  public static int Solution(String str){
    int answer=0;
    Stack<Character> stack = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();
    for(char c : str.toCharArray()){
      if(Character.isDigit(c)){
        stack2.push(Character.getNumericValue(c));
      }else{
        if(c=='+'){
          int a = stack2.pop();
          int b = stack2.pop();
          stack2.push(a+b);
        }
        else if(c=='-'){
          int a = stack2.pop();
          int b = stack2.pop();
          stack2.push(b-a);
        }
        else if(c=='*'){
          int a = stack2.pop();
          int b = stack2.pop();
          stack2.push(b*a);
        } 
        else if(c=='/'){
          int a = stack2.pop();
          int b = stack2.pop();
          stack2.push(b/a);
        }
      }
    }
    
    return answer=stack2.pop();
  }
}

---

5. 쇠막대기

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    String str = in.nextLine();
    System.out.println(Solution(str));

  }
  public static int Solution(String str){
    int answer=0;
    int cnt=0;
    Stack<Character> stack = new Stack<>();
    for(char c: str.toCharArray()){
      if(c==')'){
        if(!stack.isEmpty() && stack.peek()=='('){          
          cnt--;
          stack.push(c);
          answer+=cnt;
        }else{
          cnt--;
          stack.push(c);
          answer++;
        }
      }
      else if(c=='('){
        cnt++;
        stack.push(c);
      }
    }
    
    return answer;
  }
}

 

---

6. 공주 구하기

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int k = in.nextInt();
    System.out.println(Solution(n,k));
  }
  public static int Solution(int n, int k){
    int answer=0;
    Queue<Integer> q = new LinkedList<>();
    for(int i=1;i<=n;i++){
      q.offer(i);
    }
    int cnt=1;    
    while(q.size()!=1){
      int c = q.poll();
      if(cnt++%k!=0){
        q.offer(c);
      }
    }
    
    return q.poll();
  }
}

 

---

 

 

7. 교육과정 설계

 

(1) 큐 안쓰고 배열로

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    String str1 = in.nextLine();
    String str2 = in.nextLine();
    System.out.println(Solution(str1, str2));
  }
  public static String Solution(String str1, String str2){
    String answer= "NO";
    int lt=0;
    int rt=0;
    while(lt<str1.length()&&rt<str2.length()){
      char c = str2.charAt(rt);
      if(str1.indexOf(c) !=-1 && str1.charAt(lt) != c) return answer;
      else if(str1.charAt(lt) == c){
        lt++;
      }
      rt++;
    }
    if(lt!=str1.length()) return "NO";
    else return "YES";
  }
}

 

 

(2) indexOf없이

import java.util.*;

public class Main {
  public static void main(String[] args){
    Scanner in = new Scanner(System.in);
    String str1 = in.nextLine(); // 선순위 과목
    String str2 = in.nextLine(); // 교육과정
    System.out.println(Solution(str1, str2));
  }
  
  public static String Solution(String str1, String str2){
    int lt = 0;
    int rt = 0;

    while (lt < str1.length() && rt < str2.length()) {
      char c = str2.charAt(rt);
      if (str1.charAt(lt) == c) {
        lt++;
      }
      rt++;
    }

    if (lt == str1.length()) {
      return "YES";
    } else {
      return "NO";
    }
  }
}

 

(3) 연결리스트 활용

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    String str1 = in.nextLine();
    String str2 = in.nextLine();
    System.out.println(Solution(str1, str2));
  }
  public static String Solution(String str1, String str2){
    Queue<Character> q = new LinkedList<>();
    Queue<Character> q2 = new LinkedList<>();
    for(char c:str1.toCharArray()){
      q.offer(c);
    }
    for(char c:str2.toCharArray()){
      q2.offer(c);
    }
    while(!q.isEmpty()){
      if(q2.peek() == q.peek()){
        q.poll();
        q2.poll();
      }else if(q2.peek() != q.peek() && q.contains(q2.peek())){
        return "NO";
      }else if(!q2.isEmpty()){
        q2.poll();
      }else{
        return "NO";
      }
    }
    
    return "YES";
  }
}

 

 

+) 조건 단순히 -- 같으면 선순위 큐 교육과정 큐 동시에 제거, 다르면 교육과정 큐에서만 제거

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    String str1 = in.nextLine();
    String str2 = in.nextLine();
    System.out.println(Solution(str1, str2));
  }

  public static String Solution(String str1, String str2) {
    Queue<Character> queue1 = new LinkedList<>();
    Queue<Character> queue2 = new LinkedList<>();

    for (char c : str1.toCharArray()) {
      queue1.offer(c);
    }

    for (char c : str2.toCharArray()) {
      queue2.offer(c);
    }

    while (!queue1.isEmpty() && !queue2.isEmpty()) {
      if (queue1.peek().equals(queue2.peek())) {
        queue1.poll();
        queue2.poll();
      } else {
        queue2.poll();
      }
    }

    return queue1.isEmpty() ? "YES" : "NO";
  }
}

 

 

---

8. 응급실

import java.util.*;

class Pat {
  int num;
  int prior;

  public Pat(int num, int prior) {
    this.num = num;
    this.prior = prior;
  }

  public static Comparator<Pat> PatComp = new Comparator<Pat>() {
    @Override
    public int compare(Pat p1, Pat p2) {
      return p2.prior - p1.prior;
    }
  };
}

public class Main {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int m = in.nextInt();
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
      arr[i] = in.nextInt();
    }
    System.out.println(Solution(n, m, arr));
  }

  public static int Solution(int n, int m, int[] arr) {
    int answer = 0;
    PriorityQueue<Pat> pq = new PriorityQueue<>(Pat.PatComp);
    Queue<Pat> q = new LinkedList<>();
    for(int i = 0; i < n; i++) {
      Pat pat = new Pat(i, arr[i]);
      pq.offer(pat);
      q.offer(pat);
    }
    
    int cnt = 0;
    while(!q.isEmpty() && !pq.isEmpty()) {
      if(q.peek().prior != pq.peek().prior) {
        q.offer(q.poll());
      } else {
        Pat pat= q.poll();
        pq.poll();
        cnt++;
        if(pat.num == m) {
          answer = cnt;
          break;
        }
      }
    }
    
    return answer;
  }
}