2022-06-29 [4회차] 알고리즘 스터디

1. substring의 index 찾기

  - String haystack에 대해서 String needle이 haystack의 한 부분을 차지하는 경우 그 index를 반환하라.

  - 부분 문자열이 아닌 경우는 -1을 반환하라

  - 포인터를 써서 풀도록 문제를 가져오셨는데 내가 단순하게 substr으로 풀었다. 포인터로 푸는 부분도 복습!

 

출처: https://leetcode.com/problems/implement-strstr/

Implement strStr() - LeetCode

 

  MySol)

<hide/>
public class T4 {

    public static  int strStr(String haystack, String needle) {

        for(int i = 0; i <= haystack.length() - needle.length(); ++i){
            if(haystack.substring(i, i + needle.length()).equals(needle) ){
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String haystack = "hello";
        String needle = "ll";
        System.out.println(strStr(haystack, needle));	// 2

        haystack = "aaaaa";
        needle = "bba";
        System.out.println(strStr(haystack, needle));	// -1

        haystack = "a";
        needle = "a";
        System.out.println(strStr(haystack, needle));	// 0

        haystack = "abc";
        needle = "c";
        System.out.println(strStr(haystack, needle));	// 2

        haystack = "mississippi";
        needle = "pi";
        System.out.println(strStr(haystack, needle));	// 9
    }
}

    - for문에 등호를 꼭 넣어야한다.(맨 뒤에 있는 substr도 확인해야하니까)

 

 

  Sol) 스터디원 코드

출처: https://gist.github.com/Guiwoo/c3c5e6746ef44e4322ba86bad91e0803

<hide/>
// 1번 솔루션 1ms
class Solution {
    public int strStr(String hay, String needle) {
        if(needle.length() > hay.length())return -1; // 니들이 길다면 굳이 탐색해줄 필요없이 -1 뱉어줍니다.
        if(needle.length() == hay.length()){ // 만약 서로의 길이가 같다면 ? 서로 문자열 비교해서 맞으면 0 리턴해줍니다.
            if(cal(needle,hay)){
                return 0;
            }else{
                return -1; // 아닌경우
            }
        }
        for (int i = 0; i < hay.length()-needle.length()+1; i++) { //for 를 끝까지 이동할 필요 없이 needle 을 셀수있을만큼만 이동 
            String sub = hay.substring(i,i+needle.length()); //문자 잘라주기
            if(cal(sub,needle)){ //넘겨줘서 트루면 현재 인덱스 반환 
                return i;
            }
        }
        return -1; // for 를 다돌아도 함수가 종료 안된다면 -1
    }
    public boolean cal(String s1,String s2){ //스트링 2개를 가져와 비교해서 같으면 트루,폴스 리턴 해줌 생각해보니, eqaul 쓰면됨 ㅋㅋㅋ
        for (int i = 0; i < s2.length(); i++) {
            if(s1.charAt(i) != s2.charAt(i)){
                return false;
            }
        }
        return true;
    }
}

//2번째 2ms 2포인터 섹션이길래 어거지로 넣어 봤습니다.

class Solution {
    public int strStr(String hay, String needle) {
       if(needle.length() > hay.length())return -1;
        int start = 0; //시작 점
        int end = needle.length(); // 찾을 문자열 끝점
        int answer = -1; 
        while(end <= hay.length()){
            String sub = hay.substring(start,end); // 위와 유사하게 문자열 잘라줍니다, 
            if(checker(sub,needle)){ // 체커 말고 equal 쓰세요 ㅠㅠㅠㅠ
                answer = start; // 인덱스 업데이트
                break;
            }
            start++; // 아니면 ++해줍니다
            end = start + needle.length(); //문자열 끝점도 업데이트
        }
        return answer;
    }
    public boolean checker(String s1 ,String s2){
        for (int i = 0; i < s1.length(); i++) {
            if(s1.charAt(i) != s2.charAt(i)) return false;
        }
        return true;
    }
}

//3번 위에처럼 생각하다 보니 슬라이딩 윈도우 가 왔습니다. 사실 슬라이딩 윈도우나 , 쟤나 별반다를것 없습니다.
// 저는 스트링에 냅다 추가했는데 다른분들 풀이보니 빌더쓰더라고요.. 그분들 풀이가 직관적이여서 벤치마킹 해왔습니다.
class Solution {
    public int strStr(String haystack, String needle) {
        if(needle.length() > haystack.length())return -1;
        if(needle.length() == 0 )return 0;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < needle.length(); i++) {
            sb.append(haystack.charAt(i)); //0번부터 추가해줍니다.
        }

        if(sb.toString().equals(needle)){
            return  0 ; //같으면 0번 시작이니 고대로 리턴해줍니다.
        }
        int leftWindow = 0, rightWindow = needle.length()-1; // 윈도우 세팅 해줍니다.

        while(rightWindow < haystack.length()){
            sb.delete(0,1); //빌더에 요렇게 앞에서 지울수 있는 편의기능 !
            
            rightWindow++; // 윈도우 오른쪽으로 이동 시켜줍니다.
            leftWindow++;
            
            if(rightWindow > haystack.length()-1) break; //while 에서 범위에 맞게 들어오더라도 안에서 추가를 했기때문에 다시 확인해야합니다.
            //안하면 인덱스 나가요

            sb.append(haystack.charAt(rightWindow)); // 늘린만큼 추가해주어 현재 스트링 갯수를 유지해 줍니다.
            if(sb.toString().equals(needle)) return leftWindow;
        }
        return -1;
    }
}

 

 

2. 수열 - 실버 3

https://www.acmicpc.net/problem/2559

2559번: 수열

 

  MySol 1) - 1700ms

<hide/>

import java.util.Scanner;
public class T5 {
    public static void main(String[] args) {

        Scanner scan  = new Scanner(System.in);
        int N = scan.nextInt();
        int K = scan.nextInt();
        int[] arr = new int[N];
        int max = Integer.MIN_VALUE;

        for(int i = 0; i < N; ++i){
            arr[i] = scan.nextInt();
        }

        for(int i = 0; i <= N - K; ++i){    

            int p1 = i;
            int p2 = i + K;
            int sum = 0;

            for(int j = p1; j < p2; ++j){
                sum += arr[j];
            }
            max = Math.max(sum, max);
        }
        System.out.println(max);
    }
}

    - 이것도 1번과 마찬가지로 for문 안에 조건부에 등호를 넣지 않아서 처음에 오류가 났다. (배열의 마지막 K개 원소의 합은 카운트 되지 않았기 때문)

    - 등호를 추가하니까 (i <= N - K) 통과할 수 있다.

    - 백준 회전초밥 참고!? 알고리즘 1-1 연습문제 2번? 강의에 있음!

    - totalSum 은 구할 때 매번 더하지 말고 앞에는 빼고 뒤에꺼는 더하는 방식으로 해야 시간이 훨씬 줄어든다! 아주 중요

 

  MySol 2) 슬라이딩 윈도우 - 812ms (nextInt()를 nextLine()으로 바꾸면 속도가 528ms로 줄어든다.) 

<hide/>
// 수열
import java.util.Scanner;
public class T5 {

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt(); // 10
        int K = scan.nextInt(); // 5
        int[] arr = new int[N];
        int max = 0;
        int sum = 0;

        for (int i = 0; i < N; ++i) {
            arr[i] = scan.nextInt();    // 3 -2 -4 -9 0 3 7 13 8 -3

            if(i < K){
                sum += arr[i];      // sum 초깃값
            }
        }
        max = sum;

        for (int i = 1; i < N - K + 1; ++i) {    // i : 1 ~ 5

            int p1 = i - 1;         // 0
            int p2 = i + K - 1;     // 5
            sum += (arr[p2] - arr[p1]);   // 6 + 3 - 4 = 5
            max = Math.max(sum, max);
        }
        System.out.println(max);
    }
}

    - 첫 번째 풀이는 시간이 오래 걸려서 스터디원의 조언에 따라서 sum구하는 방법을 수정했다.

    - 윈도우가 이동할 때 마다,  sum에다가 이전 데이터는 마이너스 다음 데이터는  더하는 방식으로 구현한다.

    - 정수 하나씩 scan하는 것보다 줄 단위로 scan.nextInt()를 두 번(그리고 String[] 두 개 만든다.) 하는 것이 시간적인 면에서 효율성이 높다. (528ms로 줄어든다.)

      -> 그런데 여기서 Scanner가 아닌 BufferedReader를 이용하면 시간이 더 줄어든다!

 

  Sol) 스터디원 코드 -  296ms

<hide/>
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    static int N, K;
    static int[] temperatures;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] s = br.readLine().split(" ");
        N = Integer.parseInt(s[0]); // 온도를 측정한 전체 날짜 수
        K = Integer.parseInt(s[1]); // 합을 구하기 위한 연속적인 날짜의 수
        temperatures = new int[N]; // 측정한 온도를 저장하기 위한 배열

        String[] s_temperature = br.readLine().split(" ");
        int max_temp = 0;
        for (int i = 0; i < N; i++) {
            temperatures[i] = Integer.parseInt(s_temperature[i]);

            if (i < K) {
                max_temp += Integer.parseInt(s_temperature[i]);
            }
        }

        // N = 10, K = 5 일 때
        // 위에서 temperatures[0] ~ temperatures[4] 까지 더한 값을 max_temp에 저장하고 temp_sum에 넣어 줌
        // 1. 그리고 둘째 날부터 시작해서 temperatures[1] ~ temperatures[5] 까지의 합을 temp_sum에 넣어주고 첫째 날짜는 temp_sum에서 빼준 후
        // 2. max_temp와 비교해서 더 큰 값을 업데이트
        // 1번, 2번을 for문이 끝날 때 까지 반복
        int temp_sum = max_temp;
        for (int i = 1; i < N - K + 1; i++) {

            int p1 = i - 1;
            int p2 = K + i - 1;

            temp_sum += -temperatures[p1] + temperatures[p2];
            max_temp = Math.max(max_temp, temp_sum);
        }

        System.out.println(max_temp);

    }
}

 

 

3. 카드 합체 놀이 - 실버 1

출처:https://www.acmicpc.net/problem/15903

15903번: 카드 합체 놀이

 

  MySol 1) 배열과 정렬 이용 - 830ms

<hide/>
import java.util.Arrays;
import java.util.Scanner;

public class T6 {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();     // 카드의 개수
        int m = scan.nextInt();     // 카드의 상태.   0가능
        long[] arr = new long[n];

        for(int i = 0;i < n; ++i){
            arr[i] = scan.nextLong();
        }
        Arrays.sort(arr);
//      System.out.println(Arrays.toString(arr));

        int idx = 0;
        while( idx < m){

            long sum = arr[0] + arr[1];  // 가장 작은 두 수를 더한다...
            arr[0] = sum;
            arr[1] = sum;
            ++idx;
            Arrays.sort(arr);
//            System.out.println(arr[0] +" " +  arr[1]);

        }
            System.out.println(Arrays.stream(arr).sum());
    }
}

    - 배열을 정렬해서 푼다.

    - 조건 때문에 int가 아닌 long으로 해야한다.

 

  MySol 2) PriorityQueue 이용 -324ms

<hide/>
// 실버1
// 카드 합체 놀이
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class T6 {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();     // 카드의 개수
        int m = scan.nextInt();     // 카드의 상태  0가능
        PriorityQueue<Long> pq = new PriorityQueue<>();

        for(int i = 0;i < n; ++i){
            pq.offer(scan.nextLong());
        }

        int idx = 0;
        while( idx < m){
            long sum = pq.poll() + pq.poll();  // 가장 작은 두 수를 더한다.
            ++idx;
            pq.offer(sum);
            pq.offer(sum);
        }

        long answer = 0;
        while(!pq.isEmpty()){
            answer += pq.poll();
        }
            System.out.println(answer);
    }
}

    - 우선순위 큐를 이용하니까 시간이 절반이나 줄어든다.

 

  Sol) 스터디원 코드 - 168ms

<hide/>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Practice082 {
    // 풀이 1 - 0, 1번 원소를 그때마다 삽입정렬
    // 메모리 14632 KB, 시간 168ms
    public static void solution(int n, int m, long[] arr) {
        long answer = 0;
        // n이 2면 걔들 둘만 계속 돌리면 됨
        if(n == 2) {
            for (int i = 0; i < m; i++) {
                long tmp = arr[0] + arr[1];
                arr[0] = tmp;
                arr[1] = tmp;
            }
            System.out.println(arr[0] + arr[1]);
            return;
        }

        // m이 0이면 배열 더하고 끝
        if(m == 0) {
            for (long item : arr) {
                answer += item;
            }
            System.out.println(answer);
            return;
        }
        // 배열 정렬
        Arrays.sort(arr);
        // m번 수행
        for (int i = 0; i < m; i++) {
            // 0, 1번 원소를 tmp로 업데이트한 후 매번 정렬을 하기 때문에
            // 계속 0번, 1번을 더하면 됨
            long tmp = arr[0] + arr[1];
            arr[0] = tmp;
            arr[1] = tmp;
            sort(arr, 1); // 1번 인덱스에 있는것 정렬
            sort(arr, 0); // 0번 인덱스에 있는것 정렬
        }
        // 배열 모두 더해서 출력
        for (long item : arr) {
            answer += item;
        }
        System.out.println(answer);
    }
    // 정렬 메서드
    public static void sort(long[] arr, int startIdx) {
        // 인덱스가 배열길이 - 1까지 (그 뒤에거랑 비교를 하니 -1까지)
        while(startIdx < arr.length - 1) {
            if(arr[startIdx] > arr[startIdx + 1]) {
                // 스왑
                long tmp = arr[startIdx];
                arr[startIdx] = arr[startIdx + 1];
                arr[startIdx + 1] = tmp;
            } else { // 뒤에 원소가 더 크면 정렬 종료. (오름차순 정렬되어있기 때문)
                break;
            }
            startIdx++;
        }
    }

    // 풀이 2 - 우선순위큐를 이용
    // 메모리 15596 KB, 시간 164ms
    // 예외처리 하니 메모리 15468 KB, 시간 176ms ...?
    public static void solution2(int n, int m, long[] arr) {
        long answer = 0;
        // n이 2면 걔들 둘만 계속 돌리면 됨
        if(n == 2) {
            for (int i = 0; i < m; i++) {
                long tmp = arr[0] + arr[1];
                arr[0] = tmp;
                arr[1] = tmp;
            }
            System.out.println(arr[0] + arr[1]);
            return;
        }

        // m이 0이면 배열 더하고 끝
        if(m == 0) {
            for (long item : arr) {
                answer += item;
            }
            System.out.println(answer);
            return;
        }

        PriorityQueue<Long> pq = new PriorityQueue<>();
        Arrays.sort(arr);
        // 큐에 넣기
        for (int i = 0; i < arr.length; i++) {
            pq.add(arr[i]);
        }
        // m번 수행
        for (int i = 0; i < m; i++) {
            // 큐에서 2개 빼서 더한 후 더한 값을 큐에 넣기
            long a = pq.poll();
            long b = pq.poll();
            long tmp = a + b;
            pq.add(tmp);
            pq.add(tmp);
        }
        // 큐에 있는것 더해서 출력
        for (long item : pq) {
            answer += item;
        }
        System.out.println(answer);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);

        String[] s2 = br.readLine().split(" ");
        long[] arr = new long[s2.length];
        for (int i = 0; i < s2.length; i++) {
            arr[i] = Long.parseLong(s2[i]);
        }
        solution2(n, m, arr);
    }
}

    - 삽입 정렬 sort() 구현해서 푼다.

    - 우선순위 큐 보다 직접 구현해서 푸는 게 시간이 훨씬 짧고 효율적이다.

 

 

4. 큰 수 만들기 (Greedy) - level 2

출처: https://programmers.co.kr/learn/courses/30/lessons/42883

코딩테스트 연습 - 큰 수 만들기

  My)

    - 문제를 잘못 읽어서 오랫동안 이해를 못 했다.

    - 계수 정렬(counting sort)을 해서 문자열에 있는 가장 작은 숫자들만 k개 만큼 제거하면 되는 줄 알고 잘못 풀었다..

 

  Sol)

<hide/>
import java.util.Stack;
class Solution {
    public String solution(String number, int k) {
        char[] result = new char[number.length() - k];
        Stack<Character> stack = new Stack<>();
        int curK = k;
        for (int i = 0; i < number.length(); i++) {
            char c = number.charAt(i);
            while (!stack.isEmpty() && stack.peek() < c && curK-- > 0) {
                stack.pop();
            }
            stack.push(c);
        }
        for (int i = 0; i < number.length()-k; i++) {
            result[i] = stack.get(i);
        }
        return new String(result);
    }
}

    - stack을 이용한다.

    - stack의 get(int index) 메서드: stack의 index번째의 값을 읽어 온다.

    - while문과 currK를 이용해서 k개 만큼만 문자를 지운다. stack.pop()

 

 

5.  기지국 설치 (Greedy) - level 3 

https://programmers.co.kr/learn/courses/30/lessons/12979

코딩테스트 연습 - 기지국 설치

  Sol)

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

    public static int solution(int n, int[] stations, int w) {  // 16, [9], 2

       int cnt = 0;         // 기지국 개수
       int position = 1;   // 1동부터 시작
       int idx = 0;         // stations[] 내의 idx

        // 전파가 터지는 최대 위치 position
        while(position <= n){

            // 기지국 설치 하지 않아도 되는 상황
            // 현 위치 position은 station[idx]으로부터 전파가 터지는 상황이다.
            if(idx < stations.length && stations[idx] - w <= position ){

                // position에 2w + 1만큼 온전히 더할 수 없는 상황이니까 position을 변경한다.
                // stations[idx] - w 부터 stations[idx] + w 까지 전파 터지니까 그 다음으로 이동
                position = stations[idx] + w + 1;
                ++idx;
//                System.out.println("position: " + position + ", idx: "+ idx);
                continue;
            }
            // 기지국 설치해야하는 상황
            ++cnt;
            position += 2 * w + 1;
//            System.out.println("position: " + position + ", cnt: " + cnt);
        }
        return  cnt;
    }


    public static void main(String[] args){

        int[] stations = {4, 11};
        System.out.println(solution(11, stations, 1));  // 3

        stations = new int[]{9};
        System.out.println(solution(16, stations, 2));  // 3

        stations = new int[]{3, 7, 9};
        System.out.println(solution(16, stations, 1));  // 4

    }
}

    - 전에 포스팅했던 그리디 문제를 내가 가져갔다.

    - 오랜만에 다시 보니까 while문의 조건에 등호가 포함되지 않는 부분이 이해가 안 갔다.

    - position은 전파가 퍼지지 않는 첫 부분을 뜻하므로 position = n일 때 까지 while문이 꼭 돌아가야한다.

 

https://oranthy.tistory.com/168