Skip to content

2023.11.16 ‐ 2023.11.22

Jump to bottom
yumyeonghan edited this page Dec 29, 2023 · 6 revisions

유명한

수들의 합

🦊 문제 해결 과정

  1. 그리디 문제
  2. 반복문을 통해 1 부터 순차적으로 더해가면서, 만약 주어진 S(자연수의 합)을 넘을 경우 break
    1. 이때 더해진 숫자가 몇개인지 카운트(n++)
    2. 위의 조건일 때 break 하는 이유
      1. 1부터 순차적으로 더해나갔기 때문에 합이 S를 넘어가면 언제든지 n개의 숫자로 S를 만들 수 있음

🐥 코드 풀이 과정

   // 2번 과정
   while (true) {
      index++;
      sum += index;
      // 순차적으로 더해나갔는데 만약 S를 넘어가면 해당 n 반환 => 언제든지 n개의 숫자로 원하는 숫자를 만들 수 있으므로
      if (sum > S) {
        break;
      }
      n++;
   }

신입 사원

🦊 문제 해결 과정

  1. 정렬과 그리디 문제
  2. 인덱스를 서류 순위, 값을 면접 순위로 배열 초기화 (정렬)
  3. 서류 1등 지원자를 처음 기준으로 두고, 다른 지원자들과 면접 순위를 비교해 가며 순회
    1. 면접 순위가 더 높은 사람이 있으면 카운팅 + 1
    2. 이때 해당 사람의 면접 순위를 기준으로 둠

🐥 코드 풀이 과정

      // 3번 과정
      /**
       * 2번째 예시
       * 1, 4 선발
       * 2, 5
       * 3, 6
       * 4, 2 선발
       * 5, 7
       * 6, 1 선발
       * 7, 3
       */
      int base = tmp[1]; // 2번 과정의 배열
      for (int j = 2; j <= m; j++) {
        if (tmp[j] < base) {
          base = tmp[j];
          count++;
        }
      }

가장 가까운 같은 글자

🦊 문제 해결 과정

  1. 현재 위치보다 앞을 순회
  2. 가장 처음 같은 글자를 찾은것이 가장 가까운 수이기 때문에 해당 값을 정답처리

🐥 코드 풀이 과정

    // 1-2번 과정
    for (int i = 0; i < answer.length; i++) {
      // 현재 위치보다 앞을 순회하며,
      for (int j = i; j >= 0; j--) {
        // 가장 처음 같은 글자를 찾으면 그것이 가장 가까운 수이기 때문에
        // answer[i] == 0 조건 추가
        if (s.charAt(i) == s.charAt(j) && answer[i] == 0) {
          answer[i] = i - j;
        }
      }
      if (answer[i] == 0) {
        answer[i] = -1;
      }
    }

정경원

로프

🦊 문제 해결 과정

  1. 주어진 로프의 개수에 의한 로프를 담을 배열을 생성
  2. 배열 입력 받음
  3. 최대 중량을 구하기 위해 배열 정렬
  4. 최소 중량 로프부터 w/k 값을 계산 하여 반복문을 통해 최대 증량을 구함

🐥 코드 풀이 과정

  1. 코드 단락, 이유 1
// 1~2번 해결 과정
int N = sc.nextInt(); //주어진 로프의 개수

int[] arr = new int[N]; //로프를 담을 배열
for (int i = 0; i < N; i++) {
    arr[i] = sc.nextInt();
}
  1. 코드 단락, 이유 2
// 3~4번 해결 과정

//"각" 로프가 버틸 수 있는 최대 중량을 구하기 위해 배열 정렬
Arrays.sort(arr);

//최소 중량 로프부터 (w/k)를 계산
int maximum = 0;
for (int i = 0; i < arr.length; i++) {
    maximum = Math.max(maximum, arr[i] * (N - i));
}

30

🦊 문제 해결 과정

  1. 수의 범위가 Long 범위도 넘어가므로 String 형태로 수를 입력 받음
  2. 30의 배수가 되려면 10의 배수도 되야 하므로 입력 받은 수에
    1. 0이 포함 된다면 숫자를 섞는 과정을 진행
    2. 0이 없다면 숫자를 섞어도 30의 배수를 만들 수 없으므로 “-1” 출력
  3. 출력할 배열의 크기를 주어진 수의 자릿수만큼 초기화
  4. 각 자릿수의 합을 sum 변수에 더해나감
  5. 가장 큰 수를 만들기 위해 배열 정렬 → 역순 출
  6. 각 자릿수의 합을 더한 sum 변수가
    1. 3으로 나누어 떨어지면 30의 배수가 되는 가장 큰 수를 출력
    2. 아니라면 만들 수 있는 30의 배수가 존재하지 않으므로 -1을 출력

🐥 코드 풀이 과정

String s = sc.next(); //미르코가 본 양수 (최대 10만개의 숫자로 구성)

//30의 배수 = 10의 배수 -> 10의 배수이면? "0"을 포함
if (s.contains("0")) {

		//만들고 싶어하는 수를 출력할 배열
    int[] num = new int[s.length()]; 
    int sum = 0;
    for (int i = 0; i < num.length; i++) {
        num[i] = Integer.parseInt(String.valueOf(s.charAt(i)));
        sum += num[i];
    }

    Arrays.sort(num);//가장 큰 수를 만들어야 하므로 배열을 정렬

    //30의 배수: 각 자릿수의 합이 3의 배수
    if (sum % 3 == 0) {
        for (int i = num.length - 1; i >= 0; i--) {
            System.out.print(num[i]);
        }
    }

    //아닐 시 만들 수 있는 30의 배수가 존재하지 않음
    else{
        System.out.println(-1);
    }
}

//"0"이 없으면 30의 배수를 만들 수 없음
else{
    System.out.println(-1);
}

문자열 나누기

🦊 문제 해결 과정

  1. 나눈 문자열을 담을 리스트를 초기화
  2. 첫 글자 나온 횟수와 다른 글자 나온 횟수 변수 선언
  3. 나눌 문자를 담을 문자열 변수 선언 및 첫 글자로 초기화
  4. 반복문 돌면서 첫 글자 나온 횟수와 다른 글자 나온 횟수 비교
    1. 문자열을 초기화한 상태 → 첫 글자 횟수와 다른 글자 횟수가 같아서 리스트에 누적 문자열을 담은 상태이므로 첫 글자 초기화
    2. 아니라면 count 변수 더해 나감
    3. 처음 글자 횟수와 다른 글자 횟수가 같다면 리스트에 여태까지 누적한 문자열을 더한 후 문자열 초기화 & count 변수 초기화
    4. 문자열 끝까지 count 과정을 진행했을 때, tmp 변수가 공백, 즉, 문자열 일부가 남아 있다면 리스트에 더함
  5. 리스트의 사이즈를 출력: 리스트 사이즈의 개수: 분해한 문자열의 개수

🐥 코드 풀이 과정

//1~3번 풀이 과정

var a = new ArrayList<String>();

int count_first = 1; //첫 글자 나온 횟수
int count_other = 0; //다른 글자 나온 횟수

char first = s.charAt(0); //첫 글자

String tmp = String.valueOf(s.charAt(0)); //나눌 문자


//4~5번 풀이 과정

for (int i = 1; i < s.length(); i++) {
    char c = s.charAt(i);

    //문자열을 초기화한 상태에서는 첫 글자만 초기화함
    if (tmp.equals("")) {
        first = c;
    }
    else {
        if (c == first) {
            count_first += 1;
        }
        else{
            count_other += 1;
        }
    }

    tmp += c; //문자열 누적

    //처음 글자 횟수와 다른 글자 횟수가 같다면
    //리스트에 여태까지 누적한 문자열을 더한 후 문자열 초기화 & count 초기화
    if (count_first == count_other) {
        a.add(tmp);
        tmp = "";
        count_first = 1;
        count_other = 0;
    }
}

//문자열 끝까지 진행했을 때 리스트에 들어가지 않은 경우
if (!tmp.equals("")) {
    a.add(tmp);
}
return a.size();

디펜스 게임

🦊 문제 해결 과정

  • 무적권을 활용하여 최대한 많은 라운드를 진행함 → greedy
  1. 무적권의 개수와 적의 수를 담은 배열의 크기가 같다면 해당 길이를 리턴
  2. 무적권 사용 여부를 판단하기 위한 우선순위 큐 선언: 내림차순 정렬
  3. 적 배열의 길이 만큼 반복문을 진행
    1. 이때, 적의 수보다 막을 병사가 부족하고 무적권이 없다면 반복문 종료
    2. 큐에 적의 병사 수를 더해나감
    3. 현재 적보다 병사수가 부족하다면 최소로 병사 수를 소비한 라운드를 다시 병사 수에 더한 후 현재 라운드는 무적권을 사용함

🐥 코드 풀이 과정

  1. 코드 단락, 이유 1
// 1~2번 해결 과정
//모든 라운드를 막을 수 있는 경우(무적권 개수 == 적 배열의 길이)
if (k == enemy.length) {
    return enemy.length;
}

//무적권 사용 여부를 판단하기 위함 & 우선순위 큐 오름차순 정렬
PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
  1. 코드 단락, 이유 2
// 3~4번 해결 과정

for (int i = 0; i < enemy.length; i++) {

    //병사가 부족하고 무적권이 없다면 공격을 막을 수 없으므로 반복문 종료
    if (n < enemy[i] && k == 0) {
        break;
    }

    queue.offer(enemy[i]);

    //현재 적보다 병사 수가 부족하면
    //최소로 병사 수를 소비한 라운드를 다시 병사 수에 더한 후 무적권 사용
    if (!queue.isEmpty() && enemy[i] > n) {
        n += queue.poll();
        k -= 1;
    }

    n -= enemy[i];
    answer += 1; //막을 수 있는 라운드는 계속 증가
}
Clone this wiki locally