뚝딱뚝딱

https://softeer.ai/practice/6292

💡 슈퍼바이러스

• lv1의 "바이러스" 업그레이드 버전
• 입력받는 크기가 더 커지기 때문에, 단순히 for문으로 해결하려고 하면, 시간초과가 발생한다.
• 따라서 분할과 정복을 통해 해결해야 한다.
• 즉 입력받은 n을 절반씩 쪼개가면서 분할 하고, 다시 합해가면서 전체 문제를 해결하는 방식이다.
• 이를 위해 solve라는 함수를 생성할 것이고, solve안에서는 solve함수를 재귀적으로 호출하면서 절반씩 나누어 해결한다.
• 코드를 통해 살펴보자.
  
  

public static long solve(long P, long N){
      if(N==1) return P;

      long res = solve(P, N/2);
      if(N%2==0){
        return (res*res)%D;
      }
      else{
        res*=res;
        res%=D;
        return (res*P)%D;
      }
    }

• solve함수는 배수인 P와 거듭 수인 N을 입력으로 받는다.
• N이 1이면 P를 반환한다
• 그렇지 않다면, res를 선언하여 N의 절반만큼 P를 거듭 제곱한 값을 solve를 통해 구하고 저장한다.
• 만약 N이 짝수였다면, res를 두번 곱한 것에 1000000007을 나눈 나머지 값을 반환하면 된다.
• 만약 N이 홀수라면, res를 두번 곱한 것에 1000000007을 나눈 나머지에 P를 한번더 곱해주고 또 1000000007을 나눈 나머지를 반환하면 된다. 왜냐하면 홀수의 경우 나누었을 때 나머지 1이 있기 때문에, P를 한번더 곱해주어야 한다는 의미이다.

• 위의 solve함수를 통해 P의 n거듭제곱 하여 1000000007로 나눈 나머지를 구할 수 있으며, 최종적으로는 k에 곱했어야 했기 때문에, K에 곱한 값에 다시한번 1000000007로 나눈 나머지를 구하면, 답이 된다.
• 전체 코드는 아래와 같다.
   

import java.io.*;
import java.util.*;

public class Main {

    static long D = 1000000007; 
    public static void main(String[] args) {
      Scanner scanner = new Scanner(System.in);
      long K = scanner.nextLong();
      long P = scanner.nextLong();
      long N = scanner.nextLong();
      N*=10;
      long res = solve(P,N)*K;

      res%=D;
      
      System.out.println(res);
    }

    public static long solve(long P, long N){
      if(N==1) return P;

      long res = solve(P, N/2);
      if(N%2==0){
        return (res*res)%D;
      }
      else{
        res*=res;
        res%=D;
        return (res*P)%D;
      }
    }
}

이 문제를 풀면서 한가지 알게 된 사실은, long 타입을 입력받을 땐 nextLong으로 받아야 한다는 점이다.

주 언어였던 c++에서 코테를 위한 java를 병행하여 배우면서 입력을 사용한지 얼마 안되었는데, next~가 세부적으로 존재한다는 것을 알게되었다. nextInt로 받으니 long으로의 변환에서 데이터 손실이 있어 결과가 잘 나오지 않았었다.

https://school.programmers.co.kr/learn/courses/30/lessons/42862

💡 체육복

• 단순 구현 문제
• lost_num이라는 int형 변수에 lost배열의 크기를 저장해두고, 최대로 빌려준 후 남은 학생 수를 저장하도록 하여, n에서 lost_num을 빼 답을 구할 것이다.
• n+1 크기의 배열 arr을 생성해서, reserve를 참고해 여벌을 가진 번호에 1을, 아니면 0으로 초기화한다.
• 근데, 여벌을 가져온 학생 중 도난을 당할 경우 자신의 옷을 입어야 한다. 따라서 lost배열과 arr배열을 비교해서, lost에 있는 번호가 arr배열에서 값이 1이면 0으로 만들고, lost_num을 1 빼준다.
  만약 해당하지 않으면 stack에 lost값을 넣는다.
• stack이 비워질 때까지, 하나씩 빼가면서 arr배열에서, 현재 peek값+1 또는 peek값-1 번호가 1의 값을 가질 때 둘 중 하나 먼저 해당되는 것을 빌리도록 하고, 그 arr값을 0으로, lost_num을 1 빼준다. 그리고 pop한다.
• 최종 answer는 n에서 lost_num을 뺀 값이다.
• 여기서 주의할 점은, lost 배열을 사용하기 전에, 오름차순 정렬해야 한다는 점이다.
  로직은 동일했는데, 두 테케에서 자꾸 실패가 떠서 왜 그런가 하고, 정렬을 해봤더니 해결됐다.
  항상 입력 배열이 정렬되어 주어질 것이라 장담하지 말고, 정렬하고 시작하는 습관을 기르자.
• 그리고 나의 풀이 방식의 경우, lost를 오름차순 정렬한 후에, lost 크기만큼 순회하면서 stack에 넣었다.
  stack에 넣으면 작은 값부터 들어가고, 나올때는 큰 값부터 나오기 때문에, lost+1번호가 여벌이 있는지를 먼저 확인하도록 하였다.
  만약 작은 값부터 나오게 짰다면, lost-1번호가 여벌이 있는지를 먼저 확인하도록 해야, 최대의 값을 가질 수 있을 것이다.
• 전체 코드는 아래와 같다.
  
  

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        
        int[] arr = new int[n+1];
    
        Arrays.fill(arr,0);
        
        for(int i=0; i<reserve.length; i++){
            arr[reserve[i]]++;
        }
        
        int lost_num=lost.length;
        
        Stack<Integer> st = new Stack<>();
        
        Arrays.sort(lost);
        
        for(int i=0; i<lost.length; i++){
            if(arr[lost[i]]==1){
                arr[lost[i]]--;
                lost_num--;
            }else{
                st.push(lost[i]);
            }
        }
        
        while(!st.isEmpty()){
            if(st.peek()<n&&arr[st.peek()+1]==1){
                arr[st.peek()+1]--;
                lost_num--;
            }
            else if(st.peek()>1&&arr[st.peek()-1]==1){
                arr[st.peek()-1]--;
                lost_num--;
            }
            st.pop();
        }
        
        answer=n-lost_num;
        return answer;
    }
}

https://softeer.ai/practice/6284

💡 바이러스

• 단순한 수학문제였다.
• K에 P를 N번 곱한 후 그값을 1000000007로 나눈 값을 출력하는 문제인데, 그냥 곱할 경우에는 int나 long에 완전히 담을 수 없을 정도로 숫자가 커지기 때문에, 일정한 값으로 나누어 져야 한다.
• K에 P를 곱한 후 1000000007로 나눈 나머지를 K에 다시 저장한 후, 그 나머지에 P를 곱하고 또 1000000007로 나눈 나머지를 K에 저장하는 식으로 해결할 수 있다. 이를 N번 반복한다.
• 어떻게 그게 가능할까?
• 만약 K=3, P=5, N=3,D(나누는 값)=13이라고 해보자.
  1R : 3*5=15, 15%13=2
  2R : 2*5=10, 10%13=10
  3R : 10*5=50, 50%13=11
  답:11
  한번에 했을 때 : 3*5*5*5%13 = 375%13=11
  답 11
  
  결과는 동일하다.
  
  15*5%13==(13*5%13)+(2*5%13)
  위와 같이 15 는 13,2로 분배될 수 있기 때문이다. 어차피 13만큼의 몇배던 13의 배수이므로 그 나머지는 0이되기때문에, 2만큼에 몇 배수를 한 것의 13으로 나눈 나머지만 구하면 된다.
• 전체 코드는 아래와 같다.
  

  import java.io.*;
  import java.util.*;
  
  public class Main {
  
      public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long K = scanner.nextInt();
        int P = scanner.nextInt();
        int N = scanner.nextInt();
        int d = 1000000007;
  
        for(int i=0; i<N; i++){
          K=(K*P)%d;
        }
        
        System.out.println(K);
        
      }
  }​

• 참고로 입력 값인 K와 P를 곱했을 때의 최대값의 범위가 10^18~10^19까지 나올 수 있기 때문에 계속해서 갱신되어야 할 K는 long으로 선언해주었다.

I-2 데이터 모델링

Q 데이터 베이스를 구축하기 위한 용도를 위해 데이터 모델링을 수행하고 업무에 대한 설명은 별도의 표기법을 이용한다.(x)

=> 데이터 모델링이라는 것은 단지 데이터베이스만을 구축하기 위한 용도로 쓰이는 것이 아니라 데이터 모델링 자체로서 업무를 설명하고 분석하는 부분에서도 매우 중요한 의미를 가지고 있다.

I-13 엔터티의 이름을 부여하는 방법

Q 가능하면 약어를 사용하여 엔터티의 이름을 간결하고 명확하게 한다 (x)

=> 가능하면 약어를 사용하지 않는다.

=> 엔터티 생성의미대로 이름을 부여한다.

I-14 속성

Q 업무에서 필요로 하는 인스턴스에서 관리하고자 하는 의미상 더 이상 분리되지 않는 최소의 데이터 단위

=> 속성(ATTRIBUTE)

I-12 식별자

Q 다른 엔터티로부터 주식별자를 상속받지 않고, 자신의 고유한 주식별자를 가지며 사원, 부서, 고객, 상품, 자재 등이 예가 될 수 있는 엔터티

=>기본엔터티(키 엔터티)

I-20 관계

Q 데이터 모델링에는 존재적 관계와 행위에 의한 관계를 구분하는 표기법이 없지만, UML에서는 연관관계와 의존관계에 대해 다른 표기법을 가지고 표현하게 되어있다.

=> 실선과 점선의 표기법

I-23 관계

Q  업무기술서, 장표에 관계연결을 가능하게 하는 명사가 있는가? (X)

=> 동사가 있는가?

I-29 관계

Q 부모 엔터티의 주식별자를 자식엔터티에서 받아 손자엔터티까지 계속 흘려보내기 위해 비식별자관계를 고려한다 (X)

=> 식별자 관계를 고려

자바 문법 공부 겸 정리한 글

String

string이 아님. String임!!

String str = "apple";

str.length();//문자열 길이 반환

str.isEmpty(); //빈 문자열 체크

str.charAt(0); //0번째 문자 반환=>'a'
str.indexOf("a") // 가장 먼저 나오는 a의 인덱스 반환=>0
str.lastIndexOf("p") //마지막 p의 인덱스를 반환 =>2

str.substring(1,3) //1번 인덱스부터 3 미만의 인덱스까지 자르기=>pp
str.substring(3) // 인덱스 3 미만 문자열 반환 => app

str.replace('p','e') // 모든 기존문자 p를 e로 바꿈=> aeele
str.replaceFirst('p','e')//첫 p만 e로 바꿈=>aeple

str.equals("apple")//값 비교를 위해 equles사용

str.contains("app"); // 문자열이 app를 포함하는지

str.split(" ") // 공백으로 구분된 문자열을 분리하여 String[]배열로 반환
str.split()//한 문자씩 분리하여 String[]로 반환

Integer.parseInt("100"); // 문자열 100을 숫자 100으로 변환
Integer.toString(100) // 숫자 100을 문자열 100으로 변환

Integer.parseInt(문자열)
Integer.toString(숫자)

StringBuilder

문자열의 변경이 필요한 경우에는  StringBuilder사용하기

유용해 보이는 것
StringBuilder sb = new StringBuilder();

st.append("apple"); //st에 apple 추가하기
st.reverse(); //st문자열 뒤집기

List

List관련 메서드
리스트는 List로 만들어서 생성자는 ArrayList로 받기
List<String> list = new ArrayList<>();

list.add(값) //요소 추가
list.add(인덱스, 값) //특정 인덱스에 값을 추가
list.addAll(list2) //리스트 병합
list.indexOf(값)
list.remove(값)
list.clear()
list.isEmpty()
list.size()
list.contains(요소)->bool타입
list.removeIf(x->x%2==0)//짝수 제거: 람다식 이용

배열을 리스트로 변환
int[] temp = {1,2,3};
List<Integer> list = new ArrayList<>(Arrays.asList(temp));

리스트를 배열로 변환
List<Integer> list = new ArrayList<>();
int[] temp = list.stream().mapToInt(x->x).toArray();

배열의 정렬을 하려면 Arrays.sort를 쓰면 되고, 인자로는 배열 넘겨주면 됨.
  

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

💡 문자열 폭발

이 문제를 풀다가 내가 폭발하는 줄 알았다.

2시간동안 총 16번의 시도끝에 결국 해냈다.

세번의 서로 다른 시도가 있었다.

[첫번째 시도]. 자바의 String에서 제공하는 contains함수를 이용하는 것이다.

입력받은 전체 문자열에서 target문자열이 있는지를 contains()함수를 이용하였고, String의 replace함수를 사용해 target을 ""빈 문자열로 변경하도록 하였다.

뭐야 너무 간단하잖아? 하고 자신있게 제출했는데... 예상과는 다르게, "메모리 초과"라는 결과가 나왔다.

String의 경우 문자열이 const이기 때문에, 내용이 바뀌면 계속해서 새로운 문자열을 만들어 저장한다.

이 부분을 완전히 간과하고 있었던 것이다..

그래서 최대 100만 길이 문자열이라면, 굉장히 많은 메모리를 낭비하게 될 것이다.

따라서 String의 replace함수로는 해결할 수 없다!

[두번째 시도]. StringBuilder 클래스를 사용하였다

앞 시도에서 문자열이 계속해서 새로 생성되니까, 메모리 초과가 되는 걸 보고, 덧셈연산을 하지 않고 메모리 효율적인 StringBuilder를 사용하면 되겠다!! 싶어서 StringBuilder객체 sb를 생성하고 문자열을 저장해 주었다.

그리고 sb에서 indexOf()함수를 사용해서 target이 존재하는 위치를 찾고, delete함수를 통해 target을 지우도록 하였다.

그리고 sb를 toString함수를 통해 string으로 출력하도록 하였다.

이젠 되겠지..?? 했는데... 이번에 "시간초과"라는 결과가 나왔다. 

따라서 StringBuilder는 단순히 문자열을 받는 입장으로는 사용할 수 있겠구나라고 판단하였다!

[세번째 시도].

결국은 한번씩 순회를 하는 수밖에 없겠다는 생각을 하였고... 

결론적으로 스택을 활용하면 되는 문제였다!

다음 과정을 거친다.

• 문자열 길이만큼 순회하면서, 스택의 길이가 target 문자열길이 이상이면 끝에서부터 target길이만큼 비교 후, 동일하면 target길이 만큼 pop한다.
• 문자열 덧셈 연산을 안하기 위해 StringBuilder를 사용하고, stack에 있는 값을 그대로 옮겨준다.
• stringBuilder의 크기가 0이 아니면, toStirng으로 출력하도록 하고, 0이면 요구사항에 있는 문자열을 출력한다.

이렇게 하면, 딱 n번 순회하니 시간 초과 문제도 없고, 스택을 통해 push pop으로 문자열을 조정함으로써 새로운 문자열이 생기는 등 메모리 낭비가 발생하지 않을 수 있다.

전체 코드는 아래와같다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
      Scanner scanner = new Scanner(System.in);
      String st=scanner.nextLine();
      String target=scanner.nextLine();
      scanner.close();
      
      Stack<Character> stack = new Stack<>();
     
      for(int i=0; i<st.length(); i++){
          stack.push(st.charAt(i));
          
          if(stack.size()>=target.length()){
              boolean flag = true;
              
              for(int j=0; j<target.length(); j++){
                  if(stack.get(stack.size()-target.length()+j)!=target.charAt(j)){
                      flag=false;
                      break;
                  }
              }
              if(flag){
                  for(int j=0; j<target.length(); j++){
                      stack.pop();
                  }
              }
          }
      }
      
      StringBuilder sb = new StringBuilder();
      
      for(Character c : stack){
          sb.append(c);
      }
      
      if(sb.length()!=0){
        System.out.print(sb.toString());
      }
      else System.out.print("FRULA");
    }
}

헷갈렷던 자바 개념은, stack에 있는 값을 sb에 옮기는 과정이었는데

stack을 뒤에서 부터 뺄 수 있다는 것과, 새로운 값을 sb에 넣을 때는 오른쪽 방향으로 넣는다는 생각때문에,

문자열이 뒤집어져서 sb에 들어가지 않을까? 했는데..

결론적으로 sb에 들어갈 때는 스택의 맨 뒤의 값을 넣고, 다음 값을 넣을 때 앞 방향으로 누적되도록 들어갈 수 있기 때문에, 결국 stack에 들어간 순으로 sb에도 누적할 수 있다고 한다.

알고나면 쉬운데, 생각해내기가 어려웠던 문제였다!