[09월 1주차] 알고리즘 스터디

1. k진수에서 소수의 개수 구하기

09-04 일

출처 - https://school.programmers.co.kr/learn/courses/30/lessons/92335

프로그래머스

 

================================= 86점 =================================

• 소수인지 확인하는 메서드를 만든다.
• k진수로 바꾸는 while문 => 다음부터는 k진법으로 바꿀 때, Integer.toString(n, k)를 쓰도록 하자!
• 0이 나올 때마다 pre0Idx를 업데이트해준다.
• 어느 부분이 틀렸을까?
  • 0이 하나도 없는 경우
  • p가 소수인 경우 / 합성수인 경우 두가지가 있으니까 합성수인 경우는 return  0을 해줘야 하는데 이 부분을 안 넣었다. 

<hide/>
public class Test1 {
    public static int solution(int n, int k) {
        int answer = 0;
        String prime = "";

        if(n == 1){
            return 0;
        }
        // k진수로 바꾼다.
        while(n > 0){

            int r = n % k;
            int q = n / k;
            n = q;
            String s = String.valueOf(r);
            prime = s + prime;
        }
//        System.out.println(prime);

//        boolean b = false;
        int pre0idx = -1;
        int curr0idx = 0;

        while (curr0idx < prime.length()){

            if(prime.charAt(curr0idx) == '0'){
//                System.out.println("curr: " + curr0idx);
                if(curr0idx - pre0idx == 1){    // '00'인 경우
                    pre0idx  = curr0idx;
                    ++curr0idx;
                    continue;
                }
//                System.out.println("curr: " + curr0idx);
                String candidate = prime.substring(pre0idx + 1, curr0idx); // 이전에

//                System.out.println("candidate: " + candidate);

                // candidate를 숫자로 바꾸고 소수인지 확인
                long c = Long.parseLong(candidate);
                if(isPrime(c)) {
                    ++answer;
//                    System.out.println("ans " + answer);
                }
                pre0idx = curr0idx;
            }
            ++curr0idx;
        }

//        System.out.println("pre " + pre0idx);
//        System.out.println("curr " + curr0idx);

        // 0이 하나도 없는 경우는? n이 소수인지 확인한다.
        if(pre0idx == -1) {
//            System.out.println("0이 하나도 없는 경우");
            long p = Long.parseLong(prime);
            if (isPrime(p)) {
                return 1;
            }
        }
        String candidate = prime.substring(pre0idx, prime.length());
//        System.out.println("candidate: " + candidate);
        long c =  Long.parseLong(candidate);
            if(isPrime(c)) {
                ++answer;
            }
        return answer;
    }

    public static boolean isPrime(long n){
        if(n <= 1){
            return false;
        }
        for(int i = 2; i <= (int) Math.sqrt(n); ++i){
            if(n % i == 0){
                return false;
            }
        }
        return true;
    }
    
    public static void main(String[] args) {
        System.out.println(solution(437674, 3));    // 3
        System.out.println(solution(110011, 10));   // 2
        System.out.println(solution(204050, 10));   // 2
        System.out.println(solution(885733, 3));    // 1
    }
}

 

  MySol) 100점

<hide/>
// 0904 일
// https://school.programmers.co.kr/learn/courses/30/lessons/92335

public class Test1 {
    public static int solution(int n, int k) {
        int answer = 0;
        String prime = "";
        if(n == 1){
            return 0;
        }
        
        // k진수로 바꾼다.
        while(n > 0){
            int r = n % k;
            int q = n / k;
            n = q;
            String s = String.valueOf(r);
            prime = s + prime;
        }
//        System.out.println(prime);

        int pre0idx = -1;	// 이전 0의 위치
        int curr0idx = 0;	// 현재 위치를 의미한다.

        while (curr0idx < prime.length()){
            if(prime.charAt(curr0idx) == '0'){
//                System.out.println("curr: " + curr0idx + ", pre0idx " + pre0idx);
                if(curr0idx - pre0idx == 1){    // '00'인 경우
                    pre0idx  = curr0idx;
                    ++curr0idx;
                    continue;
                }
                
                String candidate = prime.substring(pre0idx + 1, curr0idx); // 후보
//                System.out.println("candidate: " + candidate);
                // candidate를 숫자로 바꾸고 소수인지 확인
                long c = Long.parseLong(candidate);
                if(isPrime(c)) {
                    ++answer;
//                  System.out.println("ans " + answer);
                }
                pre0idx = curr0idx; // 현재 0이 있는 경우이므로 pre를 현재 인덱스로 업데이트
            }
            // if문 종료
            ++curr0idx;
        }
//        System.out.println("pre " + pre0idx);
//        System.out.println("curr " + curr0idx);

        // 0이 하나도 없는 경우는? n이 소수인지 확인한다.
        if(pre0idx == -1) {
//            System.out.println("0이 하나도 없는 경우");
            long p = Long.parseLong(prime);
            if (isPrime(p)) {
                return 1;	// 소수이면서 0이 없는 경우
            }
            return 0;   // 합성수이면서 0이 없는 경우- 이 부분 추가해야 테스트 케이스 4개 맞는다.
        }
        
        // 맨 마지막 후보를 넣어준다.
        String candidate = prime.substring(pre0idx, prime.length());
//        System.out.println("candidate: " + candidate);
        long c =  Long.parseLong(candidate);
        if(isPrime(c)) {
            ++answer;
        }
        return answer;
    }
    public static boolean isPrime(long n){
        if(n <= 1){
            return false;
        }
        for(int i = 2; i <= (int) Math.sqrt(n); ++i){
            if(n % i == 0){
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        System.out.println(solution(437674, 3));    // 3
        System.out.println(solution(110011, 10));   // 2
        System.out.println(solution(204050, 10));   // 2
        System.out.println(solution(885733, 3));    // 1
    }
}

• k진법으로 바꾼 결과를 isPrime()에 넣어서 확인할 때 long으로 해야한다. 숫자가 커질 수 있음
• curr0idx는 1씩 커지기 때문에 사실상 currIdx에 더 가깝다. 
• pre0Idx는 현재 인덱스보다 작은 0 중에 가장 큰 인덱스를 의미한다.
• 나중에 알게 됐는데 Integer.toString(n, k) 를 이용하면 n을 k진법으로 바꿔준다.

 

  Sol) Gui - Deque 이용

스터디원 블로그 - https://guiwoo.tistory.com/

<hide/>
class Solution {
    public int solution(int n, int k) {
        String target = converter(n,k);
        String[] thing = target.split("0");
        int cnt = 0;
        for(String s : thing){
            if(isPrime(s,k)){
                cnt++;
            }
        }
        return cnt;
    }
    boolean isPrime(String s,int k){
        if(s.length() == 0)return false;
        long num = Long.parseLong(s);
        if(num == 1) return false;
        for(long i=2;i*i<=num;i++){
            if(num%i == 0) return false;
        }
        return true;
    }

    String converter(int n,int k){
        Deque<String> q = new ArrayDeque<>();
        while(n>0){
            int tmp = n/k;
            int rest = n%k;
            n= tmp;
            q.addFirst(Integer.toString(rest));
        }
        return String.join("",q);
    }
}

• 가장 빠른 방법
• 역시 Deque가 좋기는 좋다..

 

 

  Sol) Gyu - Deque 이용

<hide/>
import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
   
    int answer;
    public  int solution(int n, int k) {
        answer = 0;
        String convertCode = Integer.toString(n, k);
        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        Deque<Character> deque = new ArrayDeque<>();
        deque.offerFirst('0');

        for (int i = 0; i < convertCode.length(); i++) {
            if (deque.size() > 2 && deque.peekFirst() == '0' && deque.peekLast() == '0') {
                deque.pollFirst();
                deque.pollLast();
                primeCheck(sb1, sb2, deque);
                deque.offerFirst('0');
                deque.offer(convertCode.charAt(i));
                continue;
            }
            deque.offer(convertCode.charAt(i));
        }

        if (!deque.isEmpty()) {
            if (!deque.isEmpty() && deque.peekFirst() == '0') {
                deque.pollFirst();
            }
            if (!deque.isEmpty() && deque.peekLast() == '0') {
                deque.pollLast();
            }
            primeCheck(sb1, sb2, deque);
        }
        return answer;
    }

    public  boolean isPrime(String number) {
        long n = Long.parseLong(number);
        if (n <= 1) {
            return false;
        }
        for (long i = 2; i <= (long) Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public  void primeCheck(StringBuilder sb1, StringBuilder sb2, Deque<Character> deque) {
        int startIdx = 0;
        int endIdx = deque.size() - 1;
        while (!deque.isEmpty()) {
            char c = deque.pollFirst();
            sb1.append(c);
            if (startIdx > 0 && startIdx < endIdx) {
                sb2.append(c);
            }
            startIdx += 1;
        }

        if (!sb2.toString().contains("0") && !"".equals(sb1.toString()) && isPrime(sb1.toString())) {
            answer += 1;
        }
        sb1.setLength(0);
        sb2.setLength(0);
    }
}

• Deque를 이용하면 시간이 더 짧다.
• 보다시피 내 코드랑 비교했을 때 시간이 10배 정도 차이가 난다.

 

 

 

2.  주차 요금 계산

09-05 월

출처 - https://school.programmers.co.kr/learn/courses/30/lessons/92341

프로그래머스

 

 MySol) 0.xx ~ 9.6x ms

• 출력부 없는 버전 - 주석, main() 제거

<hide/>
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    public int[] solution(int[] fees, String[] records) {
       
        int[] answer = {};
        Map<String, Integer> map = new HashMap<>();    // 차량번호와 시간

        for(int i = 0; i < records.length; ++i){
            int idx = records[i].indexOf(" ");
            String carNo = records[i].substring(6, 10).trim();     // 버스 번호를 의미한다.
            String time = records[i].substring(0, 5);

            int hour = Integer.parseInt(time.substring(0, 2));
            int minute = Integer.parseInt(time.substring(3, 5));
            int total = 60 * hour + minute;

            String inOut = records[i].substring(11).trim();    //in 또는 아웃

            if(inOut.equals("IN")){
                map.put(carNo,  map.getOrDefault(carNo, 0)- total);  // 마이너스 넣고
                continue;
            }

            if(inOut.equals("OUT")){
                map.put(carNo, map.getOrDefault(carNo, 0) + total);
            }
        }

        PriorityQueue<String> pq = new PriorityQueue<>();

        // 출차 기록이 없는 경우
        for(String key : map.keySet()){
            if(map.get(key) <= 0){
                map.put(key, map.getOrDefault(key, 0) + 23 * 60 + 59);
            }
            pq.add(key);
        }

        answer = new int[map.size()];
        for (int i = 0; i < answer.length; i++) {
            int curMinute = map.get(pq.poll());
            if (curMinute <= fees[0]) {
                answer[i] = fees[1];
            } else {
                answer[i] = (int) (fees[1]
                    + Math.ceil((double) (curMinute - fees[0]) / fees[2]) * fees[3]);
            }
        }
        return answer;   
                        
    }
}

• 출력부 포함

<hide/>
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
public class Test2 {
    public static int[] solution(int[] fees, String[] records) {
        int[] answer = {};
        Map<String, Integer> map = new HashMap<>();    // 차량번호와 시간
        
        for(int i = 0; i < records.length; ++i){
            int idx = records[i].indexOf(" ");
//            System.out.println(records[i].substring(6, 10));
            String carNo = records[i].substring(6, 10).trim();     // 버스 번호를 의미한다.
            String time = records[i].substring(0, 5);

            int hour = Integer.parseInt(time.substring(0, 2));
            int minute = Integer.parseInt(time.substring(3, 5));
            int total = 60 * hour + minute;

            String inOut = records[i].substring(11).trim();    //in 또는 아웃
//            System.out.println(hour +"  " +minute + " total " + total + " carNo[" + carNo + "] inout[" +inOut+ "]" );

            if(inOut.equals("IN")){
                map.put(carNo,  map.getOrDefault(carNo, 0)- total);  // 마이너스 넣고
//                System.out.println("carNo " + carNo + " total " + map.get(carNo));
//                System.out.println();
                continue;
            }
            if(inOut.equals("OUT")){
                map.put(carNo, map.getOrDefault(carNo, 0) + total);
//                System.out.println("carNo " + carNo + " total " + map.get(carNo));
            }
//            System.out.println();
        }
//        System.out.println(map.toString());

        PriorityQueue<String> pq = new PriorityQueue<>();
        // 출차기록이 없는 경우
        for(String key : map.keySet()){
            if(map.get(key) <= 0){
                map.put(key, map.getOrDefault(key, 0) + 23 * 60 + 59);
            }
            pq.add(key);
        }
//        int basicFee = fees[1];
//        int idx = 0;
        answer = new int[map.size()];

        for (int i = 0; i < answer.length; i++) {
            int curMinute = map.get(pq.poll());
            if (curMinute <= fees[0]) {
                answer[i] = fees[1];
            } else {
                answer[i] = (int) (fees[1]
                    + Math.ceil((double) (curMinute - fees[0]) / fees[2]) * fees[3]);
            }
        }
        // 기본 시간
//        for(String key : map.keySet()){
//            if(map.get(key) <= fees[0]){
//                map.put(key, basicFee);
//                answer[idx++] = basicFee;
//                continue;
//            }
//            int total = map.get(key);
//
//            int addFee = ( ( (total - fees[0]) + (fees[2] - 1)) / fees[2]) * fees[3];
//            map.put(key, basicFee + addFee);
//            answer[idx++] = basicFee + addFee;
//        }
        // treeMap 정렬 가능 !

//        System.out.println(map.toString());
        return answer;
    }

    public static void main(String[] args) {

        int[] fee = {180, 5000, 10, 600};
        String[] records = {"05:34 5961 IN",
            "06:00 0000 IN",
            "06:34 0000 OUT",
            "07:59 5961 OUT",
            "07:59 0148 IN",
            "18:59 0000 IN",
            "19:09 0148 OUT",   // 11시간 10분 => 670
            "22:59 5961 IN",
            "23:00 5961 OUT"};
        System.out.println(Arrays.toString(solution(fee, records)));

        fee = new int[]{120, 0, 60, 591};
        records = new String[]{
            "16:00 3961 IN",
            "16:00 0202 IN",
            "18:00 3961 OUT",
            "18:00 0202 OUT",
            "23:58 3961 IN"
        };
        System.out.println(Arrays.toString(solution(fee, records)));

        fee = new int[]{1, 461, 1, 10};
        records = new String[]{
            "00:00 1234 IN"
        };
        System.out.println(Arrays.toString(solution(fee, records)));
    }
}

• 차량이 들어오는 경우는 시간을 (-), 차량이 나가는 경우는 (+) 해서 총 주차한 시간을 구한다.
• 시간은 분 단위로 바꾸는 것이 계산하기 편리한다. 
• 마지막에 PQ<String>를 이용해서 차량 번호가 작은 것부터 먼저 뽑아서 answer에 value를 넣는다.
  • PQ에서 하나씩 뽑으면 차량 번호가 작은 것부터 뽑히니까 작은 것부터 answer에 넣으면서 처리한다.
• 차량 출차된 내역이 없는 경우는  for문이 끝난 다음에 total 시간이 마이너스 인 경우에 해당한다. out이 있어야만 총 시간이 + 될 것이기 때문이다. 

 

 

  Sol) Ia

스터디원 블로그 - https://velog.io/@kormeian

<hide/>
public static int[] solution(int[] fees, String[] records) {
   Map<String, Integer> map = new HashMap<String, Integer>();
   for (String record : records) {
      StringTokenizer st = new StringTokenizer(record, " ");
      StringTokenizer timeToken = new StringTokenizer(st.nextToken(), ":");
      int minute = Integer.parseInt(timeToken.nextToken()) * 60 + Integer.parseInt(
         timeToken.nextToken());
      String carNum = st.nextToken();
      if (st.nextToken().equals("IN")) {
         map.put(carNum, map.getOrDefault(carNum, 0) - minute);
      } else {
         map.put(carNum, map.getOrDefault(carNum, 0) + minute);
      }
   }
   PriorityQueue<String> queue = new PriorityQueue<String>();
   for (String s : map.keySet()) {
      if (map.get(s) <= 0) {
         map.put(s, map.getOrDefault(s, 0) + 1439);
      }
      queue.add(s);
   }
   int[] answer = new int[queue.size()];
   for (int i = 0; i < answer.length; i++) {
      int curMinute = map.get(queue.poll());
      if (curMinute <= fees[0]) {
         answer[i] = fees[1];
      } else {
         answer[i] = (int) (fees[1]
            + Math.ceil((double) (curMinute - fees[0]) / fees[2]) * fees[3]);
      }
   }
   return answer;
}

• 로직이 나와 거의 같다.
• 처음에 이 문제를 못 풀다가 pq로 정렬하는 방법을 힌트로 주셔서 나중에 겨우 풀 수 있었다.
• StringTokenizer: 사용자가 지정하는 구분자를 경계로해서 문자열을 나눠준다. 
  • StringTokenizer(st.nextToken(), ":")
  • nextToken() 을 할 때 마다 구분자 기준으로 다음에 오는 값을 읽어 온다.'
  • 내가 사용한 subString 보다 훨씬 간단한 느낌이다. subString()은 인덱스 번호를 맞춰야되야해서 StringTokenizer가 이 문제 푸는데 더 적합하다.
  • map.getOrDefault()는 내 코드와 동일하게 들어갔다.
  • 기존에 있는 value에 값을 더하거나 빼야하기 때문에 메서드가 꼭 필요하다.

 

 

  Sol) 0.7 ~ 7.4 ms

스터디원 블로그 - https://guiwoo.tistory.com/

<hide/>
import java.util.*;
class Solution {
    class InAndOut{
        String time;
        int carNum;
        boolean isIn;

        public InAndOut(String time, int carNum, boolean isIn) {
            this.time = time;
            this.carNum = carNum;
            this.isIn = isIn;
        }

        @Override
        public String toString() {
            return time +" "+ carNum + " "+ isIn;
        }
    }
    public int[] solution(int[] fees, String[] records) {
        Map<Integer, List<InAndOut>> map = new TreeMap<>();
        for(String x : records){
            String[] input = x.split(" ");

            String time = input[0];
            int carNumber = Integer.parseInt(input[1]);
            boolean isIn = Objects.equals(input[2], "IN");
            if(!map.containsKey(carNumber)){
                map.put(carNumber,new ArrayList<>());
            }
            map.get(carNumber).add(new InAndOut(time,carNumber,isIn));
        }
        int[] result = new int[map.keySet().size()];
        int cnt = 0;
        for (Map.Entry<Integer,List<InAndOut>> m : map.entrySet()){
            int carNum= m.getKey();
            int price = calFee(getTotalTime(m.getValue()),fees);
            System.out.println(carNum +" "+ price);
            result[cnt++] = price;
        }
        System.out.println(Arrays.toString(result));
        return result;
    }
    //기본시간, 기본요금, 단위시간,단위요금
    int calFee(int totalTime,int[] fees){
        int total = 0;
        if(totalTime <= fees[0]) return fees[1];
        total += fees[1];
        int t =(int) Math.ceil( (double) (totalTime-fees[0])/ fees[2]);
        total+= t*fees[3];
        return total;
    }
    int getTotalTime(List<InAndOut> lists){
        int total = 0;
        int cnt = 0;
        for (int i = 1; i < lists.size(); i+=2) {
            cnt +=2;
            total +=  calTime(lists.get(i).time,lists.get(i-1).time);
        }
        if(cnt != lists.size()){
            total +=  calTime("23:59",lists.get(lists.size()-1).time);
        }
        return total;
    }
    int calTime(String out,String in){
        int total = 0;
        String[] oTime = out.split(":");
        String[] iTime = in.split(":");
        int h = Integer.parseInt(oTime[0]) - Integer.parseInt(iTime[0]);
        int m = Integer.parseInt(oTime[1]) - Integer.parseInt(iTime[1]);
        return h*60+m;
    }
    //fees = [기본시간, 기본요금, 단위 시간, 단위요금]

}

• String [] input  =  x.split(" ") 를 이용하면 구분자 공백을 이용해서 찢은 배열을 반환 가능하다.
• 시간을 분 단위로 바꾸는 메서드를 따로 빼서 푸니까 깔끔하게 풀 수 있다.

 

 

 

3. 행렬 테두리 회전하기 - lv 2

09-07 수

출처 - https://school.programmers.co.kr/learn/courses/30/lessons/77485

프로그래머스

 

  Sol) 배열 이용

<hide/>
import java.util.List;
import java.util.*;
public class Test4 {

    static  class Point{
        int x;
        int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static int idx = 0;
    static int[] answer;
    static ArrayList<Integer> answerList = new ArrayList<>();
    static int len = 0;

    public static int[] solution(int rows, int columns, int[][] queries) {

        len = queries.length;
        answer = new int[queries.length];
        answerList = new ArrayList<>();
        int[][] matrix = new int[rows + 1][columns + 1];
        int idx = 1;
        for(int i = 1; i <= rows; ++i){
            for(int j = 1; j <= columns; ++j){
                matrix[i][j] = idx++;
            }
        }
        idx = 0;
        for(int [] p : queries){
            Point startPoint = new Point(p[0], p[1]);   // (2, 2)
            Point endPoint = new Point(p[2], p[3]); //  (5 4)
            matrix = rotate(matrix , answer, startPoint, endPoint, idx++);
        }
        return answer;
    }
    
    public static int[][] rotate(int[][] original, int[] answer, Point p1, Point p2, int idx){

        if(idx == len){
            return original;
        }

        int[][] cloneArr = original.clone();
        int startRow = p1.x;    // 2
        int startCol = p1.y;    // 2
        int endRow = p2.x;  // 5
        int endCol = p2.y;  // 4

        int min = Integer.MAX_VALUE;
        int x =  cloneArr[startRow][endCol];
        min = x < min? x : min;
		
        // 위쪽
        // 행은 그대로 열만 움직임 - 3, 3, => 3, 5
        // (2, 3) => (2, 4) 두 칸 채울 수 있다.
        for(int i = endCol; i > startCol; --i){
            original[startRow][i] = cloneArr[startRow][i - 1];
            min = original[startRow][i] < min ? original[startRow][i] : min;
        }

        // 왼쪽
        for(int i = startRow; i < endRow; ++i){
            original[i][startCol] = cloneArr[i + 1][startCol];
            min =  original[i][startCol] < min ? original[i][startCol] : min;
        }

        // 아래쪽
        for(int i = startCol; i < endCol; ++i) {
            original[endRow][i] = cloneArr[endRow][i + 1];
            min =  original[endRow][i] < min ? original[endRow][i]: min;
        }

        // 오른쪽
        for(int i = endRow; i > startRow; --i){     // 5부터  ~2 전까지
            original[i][endCol] = cloneArr[i - 1][endCol];
            min = original[i][endCol] < min ?  original[i][endCol] : min;
        }

        original[startRow + 1][endCol] = x;
        answer[idx] = min;
        ++idx;
        answerList.add(min);
        return original;
    }

    public static void main(String[] args) {

        int[][] queries = {{2, 2, 5, 4},
                            {3, 3, 6, 6},
                            {5, 1, 6, 3}};
        System.out.println(Arrays.toString(solution(6, 6, queries)));

        queries = new int[][]{{1, 1, 2, 2},
                                {1, 2, 2, 3},
                                {2, 1, 3, 2},
                                {2, 2, 3, 3}};
        System.out.println(Arrays.toString(solution(3, 3, queries)));

        queries = new int[][]{{1, 1, 100, 97}};
        System.out.println(Arrays.toString(solution(100, 97, queries)));
    }
}

• rotate라는 메서드를 이용해서 정해진 범위의 테두리에 값을 바꿔준다. 
  • rotate가 끝나면 answer에 최솟값을 업데이트해준다.
• 여기에서 값이 바뀌기 시작하는 부분 [startRow][endCol]를 저장해서 [startRow + 1][endCol]에 값을 별도로 넣어줘야한다.
• 문제에서 시계 방향으로 회전하는데 이대로 값을 넣지 말고 시계 반대 방향으로 값을 넣어줘야 정확하게 들어간다.
• 배열을 복사한 cloneArr()을 새로 만들어서 활용한다.
• 테두리 내에서 최솟값을 얻기 위해 min을 업데이트하면서 구하도록 한다.
  • 상 하 좌 우를 돌면서 모두 최솟값 체크를 한다.
• 풀이에서 idx와 answer를 static으로 쓰고 있기 때문에 이에 대한 초기화가 꼭 필요하다.

 

  cf) 리스트

<hide/>

// 회전

import java.util.List;
import java.util.*;

public class Test4 {

static  class Point{
    int x;
    int y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

    static int[] answer;
    static ArrayList<Integer> answerList = new ArrayList<>();
    static int len = 0;

    public static int[] solution(int rows, int columns, int[][] queries) {

        len = queries.length;
        answer = new int[queries.length];
        answerList = new ArrayList<>();

        int[][] matrix = new int[rows + 1][columns + 1];

        int idx = 1;
        for(int i = 1; i <= rows; ++i){
            for(int j = 1; j <= columns; ++j){
                matrix[i][j] = idx++;
            }
        }

//        for(int i = 1; i < matrix.length; ++i){
//            for(int j = 1; j < matrix[i].length; ++j){
//                System.out.printf("%3d", matrix[i][j]);
//            }
//            System.out.println();
//        }

        for(int [] p : queries){
            Point startPoint = new Point(p[0], p[1]);   // (2, 2)
            Point endPoint = new Point(p[2], p[3]); //  (5 4)
            matrix = rotate(matrix , answer, startPoint, endPoint);

             // idx를 rotate 아래가 아닌 이부분에 추가해야 오류가 안난다. static 관련 예외
//            for(int i = 1; i < matrix.length; ++i){
//                for(int j = 1; j < matrix[i].length; ++j){
//                    System.out.printf("%3d", matrix[i][j]);
//                }
//                System.out.println();
//            }
        }
//        System.out.println(answerList);

//        System.out.println(Arrays.toString(answer));
        int i = 0;
        for(int r: answerList){
            answer[i++] = r;
        }
        return answer;
    }
    public static int[][] rotate(int[][] original, int[] answer, Point p1, Point p2){


        int[][] cloneArr = original.clone();
        int startRow = p1.x;    // 2
        int startCol = p1.y;    // 2
        int endRow = p2.x;  // 5
        int endCol = p2.y;  // 4

        int min = Integer.MAX_VALUE;
        int x =  cloneArr[startRow][endCol];
        min = x < min? x : min;

        // 행은 그대로 열만 움직임 - 3, 3, => 3, 5
        // (2, 3) => (2, 4) 두 칸 채울 수 있다.
        for(int i = endCol; i > startCol; --i){
            original[startRow][i] = cloneArr[startRow][i - 1];
            min = original[startRow][i] < min ? original[startRow][i] : min;
        }

        // 왼쪽
        for(int i = startRow; i < endRow; ++i){
            original[i][startCol] = cloneArr[i + 1][startCol];
            min =  original[i][startCol] < min ? original[i][startCol] : min;
        }

        // 아래쪽
        for(int i = startCol; i < endCol; ++i) {
            original[endRow][i] = cloneArr[endRow][i + 1];
            min =  original[endRow][i] < min ? original[endRow][i]: min;
        }

        // 오른쪽
        for(int i = endRow; i > startRow; --i){     // 5부터  ~2 전까지
            original[i][endCol] = cloneArr[i - 1][endCol];
            min = original[i][endCol] < min ?  original[i][endCol] : min;
        }

        original[startRow + 1][endCol] = x;
        answerList.add(min);
        return original;
    }

    public static void main(String[] args) {

        int[][] queries = {{2, 2, 5, 4},
                            {3, 3, 6, 6},
                            {5, 1, 6, 3}};
        System.out.println(Arrays.toString(solution(6, 6, queries)));

        queries = new int[][]{{1, 1, 2, 2},
                                {1, 2, 2, 3},
                                {2, 1, 3, 2},
                                {2, 2, 3, 3}};
        System.out.println(Arrays.toString(solution(3, 3, queries)));

        queries = new int[][]{{1, 1, 100, 97}};
        System.out.println(Arrays.toString(solution(100, 97, queries)));

    }
}

 

  Sol) Gyu -PQ 이용

<hide/>
static int[][] matrix;
public static int[] solution(int rows, int columns, int[][] queries) {
    int[] answer = new int[queries.length];
    matrix = new int[rows][columns];
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
            matrix[i][j] = i * columns + j + 1;
        }
    }


    for (int i = 0; i < queries.length; i++) {
        answer[i] = change(queries[i]);
    }

    return answer;
}

public static int change(int[] query) {
    int x1 = query[0] - 1;
    int y1 = query[1] - 1;
    int x2 = query[2] - 1;
    int y2 = query[3] - 1;

    PriorityQueue<Integer> pq = new PriorityQueue<>();
    int next = matrix[x1][y1];
    int temp = 0;
    pq.offer(matrix[x1][y1]);

    for (int i = y1 + 1; i <= y2; i++) {
        pq.offer(matrix[x1][i]);
        temp = matrix[x1][i];
        matrix[x1][i] = next;
        next = temp;
    }

    for (int i = x1 + 1; i <= x2; i++) {
        pq.offer(matrix[i][y2]);
        temp =  matrix[i][y2];
        matrix[i][y2] = next;
        next = temp;
    }

    for (int i = y2 - 1; i >= y1; i--) {
        pq.offer(matrix[x2][i]);
        temp =  matrix[x2][i];
        matrix[x2][i] = next;
        next = temp;
    }

    for (int i = x2 - 1; i >= x1; i--) {
        pq.offer(matrix[i][y1]);
        temp =  matrix[i][y1];
        matrix[i][y1] = next;
        next = temp;
    }

    return pq.poll();
}

• PQ를 이용했는데 속도는 좀 걸리는 편이다.
• PQ대신에 Math.min()을 이용하면 더 빨라진다.