99클럽 코테 스터디 16일차 TIL: 리스트

Marin·2024년 8월 6일
99클럽TIL개발자취업코딩테스트준비항해99
0

TIL

목록 보기
13/17
post-thumbnail

1 | 오늘의 문제(16일차)

1. 최소직사각형_프로그래머스

문제 설명
명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다.

아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다.

명함 번호가로 길이세로 길이
16050
23070
36030
48040

가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다. 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다. 이때의 지갑 크기는 4000(=80 x 50)입니다.

모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다. 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return 하도록 solution 함수를 완성해주세요.

2. 사고

이 문제에서 명함을 돌려 지갑 크기의 최솟값을 줄일 수 있다는 표현때문에 헷갈릴 수 있다. 그러나 row에서 큰 값을 하나의 colunm으로 밀어버린다면 지갑의 최솟값을 구할 수 있다.
문제를 풀면 풀수록 왜 알고리즘이 중요한지, 수학적 사고가 중요한지 체감한다.

3. 풀이

class Solution {
    public int solution(int[][] sizes) {
        
        int maxWidth = 0;
        int maxHeigth = 0;
        
        for(int[] size : sizes) {
            int w = Math.max(size[0], size[1]); //(1)
            int h = Math.min(size[0], size[1]);
            
            //(2)
            if(w > maxWidth) { 
                maxWidth = w;
            }
            
            if(h > maxHeigth) {
                maxHeigth = h;
            }            
        }
        
        int answer = maxWidth * maxHeigth;
        return answer;
    }
}
  1. 큰 값을 index 1의 colunm으로 밀어버렸다.
  • Math.max(값1, 값2)
  1. 각 colunm 별 최댓값을 구한다.

2 | 15일차 문제

휴가 일정으로 14, 15일차를 건너 뛰어 따로 푸는 시간을 가졌다

1. 모의고사_프로그래머스

문제 설명
수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 조건
시험은 최대 10,000 문제로 구성되어있습니다.
문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

2. 풀이

import java.util.*;

class Solution {
    public int[] solution(int[] answers) {
        
        int[] person1 = {1, 2, 3, 4, 5}; 
        int[] person2 = {2, 1, 2, 3, 2, 4, 2, 5}; 
        int[] person3 = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}; 
        
        //1. 점수 배열 -> 최대 점수 찾기(메서드 생성)
        int[] scores = new int[3];
        scores[0] = correct(person1, answers);
        scores[1] = correct(person2, answers);
        scores[2] = correct(person3, answers);
        
        int maxScore = Math.max(scores[0], Math.max(scores[1], scores[2]));

        //2. 배열의 크기에서 자유로워야 한다 -> 리스트 사용
        List<Integer> result = new ArrayList<>();
        
        //3. 최대 점수를 찾아서 그 점수를 가진 사람을 리스트에 저장한다.
        for(int i = 0; i < scores.length; i++) {
            if(scores[i] == maxScore) {
                result.add(i + 1);
            }
        }
        
        //스트림을 안쓰고 배열로 바꾸기 위해서는 반복문으로 붙여넣기 해야 함
        return result.stream().mapToInt(i -> i).toArray();
    }
    
    public static int correct(int[] person, int[] answers) {
        int count = 0;
        
        for(int i = 0; i < answers.length; i++) {
            if(person[i % person.length] == answers[i]) {
                count++;
            }
        }    
        
        return count;
    }
}

이 문제를 풀면서 가장 중요한 사고라고 생각한 것은 중복이 허용되는 최댓값을 가진 인덱스(사람의 번호)를 찾기 위해서는 두 가지 과정을 거쳐야 한다는 것이다.

1. 중복이 허용되는 최댓값 자체를 찾아 변수로 선언하여 사용한다.
2. 그 최댓값을 점수로 가진 인덱스를 찾아 저장한다. 형태: 리스트

그러나 시간이 아슬아슬했던 것 같아 성능을 좀 더 개선할 수 있을 것 같아 다른 풀이를 찾아 보았다.

3. 개선

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public int[] solution(int[] answers) {

        int[] first = {1, 2, 3, 4, 5};
        int[] second = {2, 1, 2, 3, 2, 4, 2, 5};
        int[] third = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
        
        // (1)
        int[] score = new int[3];
        
        // (2)
        for (int i = 0; i < answers.length; i++) {
            if (answers[i] == first[i % first.length]) {
                score[0]++;
            }
            if (answers[i] == second[i % second.length]) {
                score[1]++;
            }
            if (answers[i] == third[i % third.length]) {
                score[2]++;
            }
        }
        
        int maxScore = Math.max(score[0], Math.max(score[1], score[2]));
        
        List<Integer> bestStudents = new ArrayList<>();
        for (int i = 0; i < score.length; i++) {
            if (score[i] == maxScore) {
                bestStudents.add(i + 1);
            }
        }
       
        return bestStudents.stream().mapToInt(i -> i).toArray();
    }
}

확실히 개선된 것을 확인했다.
가장 다른 부분은 (2)이다.
3명의 점수(=맞은 개수)를 계산하는 부분을

나: int형 메서드로 정의 -> scores 배열에 대입

3번 풀이: 메서드 없이 바로 scores 배열에 대입

main 메서드 외부를 활용하는가에 차이가 있다. 아마도 int형 배열 2개나 읽는 과정이 오래 걸리지 않았을까 하는 생각이다.

3 | 회고

오늘 문제들을 풀면서 확실히 수학적 사고를 키우는게 중요하다는 생각이 들었다. 내가 이미 배운 도구들이 무엇인지 확인하고 사용할 줄 아는 것은 필요한 것들을 배워나가는 것만큼 혹은 그 이상 중요하다.

오늘의 키워드

  • 최댓값 자체를 찾는 방법
  • Math.max(값1, 값2)
  • Math.max(값1, Math.max(값2, 값3))

  • 수학적 사고하기
    1. 직사각형의 최소 넓이
    2. 리스트로 최댓값(혹은 1등)을 가진 사람(변수/인덱스) 찾기

  • List
  • import java.util.ArrayList;
  • import java.util.List;
  • List<타입> 이름 = new ArrayList<>();
  • 중복 허용, 순서 있음, 배열의 크기 변동 있을 시 사용
profile
Marin
대학생 | BE | 취준 | Fight or Flight
이전 포스트

99클럽 코테 스터디 13일차 TIL: 이진탐색트리(BST)

다음 포스트

99클럽 코테 스터디 17일차 TIL: 이진트리 중위순회(Inorder)

0개의 댓글