프로그래머스 체육복 푸드 파이트 대회 (99클럽 코딩테스트 28일차 TIL)

목표

문제를 풀었을때 거기에서 끝나는게 아니라 조금더 효율적으로 풀 수 있게 스스로 공부를 하는게 내목표이다.

문제

내가 생각했을때 문제에서 원하는부분

전체 학생의 수 n 체육복을 도난당한 학생들의 번호가 담긴 배열 lost 
여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질때 
체육수업을 들을 수 있는 학생의 최대값을 return 해준다.

내가 이 문제를 보고 생각해본 부분

전체 학생을 배열로 표현하여 번호와 인덱스를 매핑하기
lost와 reserve 학생 정보를 값 조정으로 표현하기
인덱스로 바로 앞뒤 학생 쉽게 체크하기

코드로 구현

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int[] people = new int[n];
        int answer = n;
        
        for(int l: lost) {
            people[l-1]--;
        }
        for(int r: reserve) {
            people[r-1]++;
        }
        for (int i = 0; i < people.length; i++) {
           if(people[i] == -1) {
               if(i-1>=0 && people[i-1] == 1) {
                   people[i]++;
                   people[i-1]--;
               }else if(i+1< people.length && people[i+1] == 1) {
                   people[i]++; 
                   people[i+1]--;
               }else 
                   answer--;
           }
       }
        return answer;
    }
}

people 배열 생성: 전체 학생 수 기준 배열
lost 학생 도난 표시: people 값에서 1 감소
reserve 학생 여벌 표시: people 값에서 1 증가
도난당한 학생(people 값이 -1)에 대해 앞뒤 학생에게 빌려받기
여벌 옷 없으면 answer 값 감소
이와 같이 전체 학생을 기준으로 한 배열을 만들고 처리하면 편리하다.
배열 인덱스 기반으로 앞뒤 학생 처리도 간단하다.

시간복잡도 O(n)

장점
전체 학생을 인덱스로 관리하여 구현 용이하다.
학생 번호와 인덱스가 매핑되어 구현 편리하다.
앞뒤 학생 체크 시 인덱스 사용으로 쉽다.

단점
입력값에 따라 배열 크기 고정된다.
불필요한 메모리 공간 소모된다.
실제 필요한 만큼 동적 할당하는 것이 효율적이다.

내가 생각했을때 문제에서 원하는부분

이 대회에서 선수들은 1대 1로 대결하며, 매 대결마다 음식의 종류와 양이 바뀐다.
대결은 준비된 음식들을 일렬로 배치한 뒤, 한 선수는 제일 왼쪽에 있는 음식부터 오른쪽으로, 
다른 선수는 제일 오른쪽에 있는 음식부터 왼쪽으로 순서대로 먹는 방식으로 진행된다.
중앙에는 물을 배치하고, 물을 먼저 먹는 선수가 승리하게 된다.
이때, 대회의 공정성을 위해 두 선수가 먹는 음식의 종류와 양이 같아야 하며, 음식을 먹는 순서도 같아야 한다.
또한, 이번 대회부터는 칼로리가 낮은 음식을 먼저 먹을 수 있게 배치하여 선수들이 음식을 더 잘 먹을 수 있게 하려고 한다.
이번 대회를 위해 수웅이는 음식을 주문했는데, 대회의 조건을 고려하지 않고 음식을 주문하여 몇 개의 음식은 대회에 사용하지 못하게 되었다.

내가 이 문제를 보고 생각해본 부분

문제에서 음식의 종류별 양과 섭취하는 순서가 동일해야 한다고 제시되어 있다.
StringBuilder만을 이용하여 문자열 조작으로 해결할 수 있다면 별도의 데이터 구조 없이 해결 가능하다.
문자열과 int형 배열만 사용하여 해결할 수 있다면 추가적인 메모리 사용을 줄일 수 있다.

코드로 구현

class Solution {
    public String solution(int[] food) {
        StringBuilder sb = new StringBuilder();
 
        for (int i = 0; i < food.length; i++) {
            for (int j = 0; j < food[i] / 2; j++) {
                sb.append(i);
            }
        }     
        return sb.toString() + "0" + sb.reverse().toString();
    }
}

가장 적은 양인 food0을 제외한 나머지 음식들에 대해 반복문을 돈다.
각 음식의 양을 2로 나눈 값만큼 음식 번호를 StringBuilder에 추가한다.
(음식 양을 균등하게 나눠 먹도록 함)
가운데 물(0)을 추가한다.
만들어진 문자열을 뒤집어 이어 붙인다.

시간복잡도 O(N^2)

장점
구현이 단순하다.
추가 메모리 사용이 적다.
음식 종류가 적다면(N이 작다면) 효율적이다.

단점
음식 양이 정확히 균등하지 않을 수 있다.
음식 종류가 많다면(N이 커지면) 시간 복잡도 측면에서 비효율이다.

마무리

오늘도 문제 설명이 긴 문제들만 풀었는데 채점완료후에 공부가 거기서 끝나는게 아니라 조금더 심도깊게 문제를 파악하기 위해서 오늘 작성했던 코드 말고 다른 로직을 사용해서 코드를 작성할 수 있는지 다시 생각해보고 시도해봐야겠다.