코딩테스트: "기능개발" 문제 풀이 및 설명

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

프로그래머스

문제를 풀어봅시다~

이번 문제 또한 프로그래머스 기준 레벨 2 인지라, 어느 정도 코테에 익숙하신 분이라면,

그렇게 어렵지 않게 접근할 수 있는 문제이다.

 

 

문제를 이해해 봅시다

문제에 대한 설명은 위의 링크에 들어가면 이해가 가능한 만큼, 설명은 요약을 하고자 하니 양해를 부탁드린다.

문제들은 배열 형태로 0번 부터 해서 n 번 까지 나오며, 현재 문제의 진행 정도 또한 progress 배열에 나타나 있다.

이와 별개로 speeds 라는 배열이 따로 존재하는데, 이는 각 문제의 진행 속도이다.

 

핵심은, 한꺼번에 얼마나 배포할 수 있냐는 것인데, 배포의 조건이 문제 진행 정도가 100이 되는 것이다.

만약, 특정 시간이 지나서 문제들의 진행 정도가 [100, 100, 100, 95, 90, 100] 이 되었다고 가정할 경우,

배포는 한꺼번에 3번 문제까지만 가능하다. 왜냐하면, 그 뒤에 해결되지 않은 문제가 있으므로, 

아무리 뒤에 100이 있어도 배포가 불가능하다.

 

 

머릿속에 표를 그려보자

그럼, 이제 머릿속에 한번 배열을 표 혹은 그림을 그려넣고, 어떻게 해결해야 하는 지 생각해보자.

문제의 케이스 2번을 가지고 풀이를 해 보겠다. 먼저, 케이스 2번의 progress, 즉, 현재 진행 정도는

95

90

99

99

80

99

이렇게 되어있다. 여기서 checkPos 라는 지점을 선언을 할 것이다.

checkPos는 현재 어느 지점까지 배포가 되었는지 알려준다.

현재로써는 1번째가 95이니, 배포는 아직 하나도 되지 않았으며, checkPos 또한 0이다.

 

그 다음은, speeds 배열에서 적시한 속도만큼 progress에 진행도를 더하자.

progress의 배열은 [ 1, 1, 1, 1, 1 ]로, 모든 문제의 작업 속도가 동일하다.

그래도, 작업 속도가 개별로 다르다고 가정해서, 코드를 작성하면, 다음과 같이 적을 수 있다.

for(int i=0; i<progresses.length; i++){
    addedProgresses[i] += speeds[i];
}

이 for 반복문을 1회 진행할 경우, speeds가 각 문제에 모두 한 번씩 더해진다.

따라서 addedProgress 배열은 다음 아래와 같아질 것이다.

96

91

100

100

81

100

 

이미 100이 되어 완성된 문제는 3, 4, 그리고 6번째 문제이다.

하지만, 맨 첫 번째 문제는 진행도가 96이라 배포가 진행될 수 없으며, checkPos는 여전히 0이다.

 

따라서, 위의 for 반복문을 계속 돌려보자. 

언제까지? 바로 checkPos가 탐색해야 할 우측 칸이 100이 될 때 까지다.

(100이 넘을 경우, 여기서 더 더해도 상관이 없다. 코드를 어떻게 작성하냐에 따라서..)

 

 

100

95

104

104

85

104

총 5번을 for 문을 반복할 경우, 다음 과 같은 addedProgress 배열이 생성된다.

탐색해야 할 우측 칸이 100 이상일 경우, checkPos가 우측으로 움직이기 시작한다.

하지만 바로 다음 칸이 100미만이라 1칸만 움직인다.

여기서 한꺼번에 배포할 수 있는 문제는 총 1개이다.

 

이렇게 checkPos가 멈추게 되었을 경우, 다시 for 문을 돌린다.

언제까지? 바로 checkPos가 탐색해야 할 우측 칸이 100이 될 때 까지다.

105

100

109

109

90

109

총 5번 진행하니, 우측 칸이 100이 넘었다. 이번에는 checkPos가 우측으로 3번 움직인다.

따라서, 이번에는 한꺼번에 배포할 수 있는 문제는 총 3개이다.

 

checkPos의 이동 양  =  한꺼번에 배포할 수 있는 문제 수

라는 것이 성립이 되는 만큼 이 과정을 반복하면 된다. 

해당 과정을 한번 더 반복할 경우,

115

110

119

119

100

119

이렇게 checkPos의 이동량은 1번, 3번, 2번이 성립된다.

 

 

코드를 작성해보자

사실 이 부분은 저 또한 꽤나 고민한 부분이다. 

문제를 좀 더 간결하고 쉽게, 혹은 논리적으로 작성한 사람도 있겠으나,

저의 경우 while과 for문을 겹쳐서 적용하는 방식으로 풀었다.

class Solution {
    public ArrayList<Integer> solution(int[] progresses, int[] speeds) {
        int[] addedProgresses = Arrays.copyOf(progresses, progresses.length);
        ArrayList<Integer> answer = new ArrayList<>();
        int prevPos = -1;
        int checkPos = 0;
        
        while(checkPos < progresses.length-1){
            for(int i=0; i<progresses.length; i++){
                addedProgresses[i] += speeds[i];
            }
            
            if(addedProgresses[checkPos] >= 100){
                while(addedProgresses[checkPos] >= 100 ){
                    if(checkPos >= progresses.length-1|| addedProgresses[checkPos + 1] < 100){
                        break;
                    }
                    checkPos++;                    
                }
                int range = checkPos - prevPos;
                if(range != 0){
                    answer.add(range);
                }

                prevPos = checkPos;               
            }
        }       
        return answer;
    }
}

코드 전체는 다음과 같다.

1. 맨 위의 while 문은 checkPos가 progress의 말단 끝 까지 탐색이 완료되었을 경우, 이를 중지한다는 반복문이다.

2. 그 안의 for 문은 addedProgress에 speeds 만큼 더하는 계산식이다.

3-1. 아래의 if 문은 checkPos가 위치한, 탐색해야 할 우측 칸이 100을 넘을 경우 작동하는 조건문이며,

3-2. 안의 while 문은  checkPos가 탐색해야 할 우측 칸이 100이 될 때 까지 움직이도록 작성한 반복문이다.

 

 

문제 해결에 도움이 되길 바라며 글을 마친다.

뿅~