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

자료구조와 알고리듬 With Java/[Study] BAEKJOON 프로그래머스 CodeUp LeetCode

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

계란💕 2022. 9. 5. 01:25

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

09-04 일

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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

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

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

java

열기

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점

java

열기

// 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/

java

열기

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 이용

java

열기

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

프로그래머스

programmers.co.kr

MySol) 0.xx ~ 9.6x ms

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

java

열기

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;   
                        
    }
}

출력부 포함

java

열기

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

java

열기

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/

java

열기

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

프로그래머스

programmers.co.kr

Sol) 배열 이용

java

열기

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) 리스트

java

열기


// 회전

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 이용

java

열기

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()을 이용하면 더 빨라진다.

저작자표시

'자료구조와 알고리듬 With Java > [Study] BAEKJOON 프로그래머스 CodeUp LeetCode' 카테고리의 다른 글

[12월 1주차] 알고리즘 스터디 (0)	2022.12.05
[11월 3주차] 알고리즘 스터디 (0)	2022.11.21
2022-08-28 [11회차] 알고리즘 스터디 (0)	2022.08.28
2022-08-03 [9회차] 알고리즘 스터디 (0)	2022.08.03
2022-07-27 [8회차] 알고리즘 스터디 (0)	2022.07.26

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

Backend Developer lan4250@naver.com https://github.com/goraneee

GIT, Queue, 백준, 자바, DB, 제로베이스 백엔드, 스프링, Java, SQL, 데이터베이스, BFS, 프로그래머스, Stack, dfs, 알고리즘, dp, 코드업, mysql, JPA, 제로베이스 스쿨,

Today :
Yesterday :

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

계란 블로그