백준 1092번: 배 (Python/Java)

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

1092번: 배

 

 

 

접근

---

굉장히 단순한 문제다. 어렵게 생각할 것 없이, 우선 입력받은 정보를 목록을 만들고 내림차순으로 정렬해준다. 그 뒤, 가장 무거운 무게를 들 수 있는 크레인과 가장 무거운 무게의 박스를 하나씩 확인해보며 걸리는 시간을 구하면 된다. 여기까지는 누구나 쉽게 생각할 수 있는 부분이다.

 

내가 생각하는 이 문제의 진짜 핵심은 구현 방식이라고 생각한다. while문 속에 for문이, 그 for문 속에 다시 또 for문이 들어가기 때문에 연산이 많아질 수밖에 없다. 평범하게 while, for만 사용한다면 무조건 시간 초과가 난다.

 

이를 위해 세 가지 처리를 해줘야 한다. 첫 번째로 박스 배열이 비어있는 상황이다. 박스 배열이 비었으면 이미 모든 결과가 나온 상태이기 때문에 반복문을 돌릴 필요가 없다. 반복문에서 나와주자. 두 번째로 더 이상 박스를 뺄 수 없는 상황이다. 현재 순서인 크레인이 들 수 없는 무게의 박스만 남았을 때 어차피 반복문을 돌려봤자 결과에 영향을 줄 수 없기 때문에 바로 빠져나와주자. 마지막으로 이미 옮긴 박스 처리다. 배열을 몇 번씩이나 반복문으로 돌리기 때문에 배열의 크기가 작으면 작을수록 유리하다. 이미 옮긴 박스는 박스 배열에서 빼줘서 박스 배열을 최대한 작게 만들어주자. 이 세 가지 처리를 미리 해둔다면 시간 초과 없이 문제를 해결할 수 있을 것이다.

 

 

 

풀이

---

Python

import sys

crainNum = int(sys.stdin.readline())
crainList = sorted(list(map(int, (sys.stdin.readline()).split())), reverse=True)

boxNum = int(sys.stdin.readline())
boxList = sorted(list(map(int, (sys.stdin.readline()).split())), reverse=True)

if crainList[0] < boxList[0]:
    print(-1)
else:
    result = 0
    while boxList:
        for i in range(len(crainList)):
            if not boxList:
                break
            elif crainList[i] < boxList[-1]:
                break
            else:
                for j in range(len(boxList)):
                    if crainList[i] >= boxList[j]:
                        boxList.pop(j)
                        break
        result += 1
    print(result)

 

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);

        int crainNum = Integer.parseInt(scan.nextLine());
        String[] firstLine = (scan.nextLine()).split(" ");
        Integer[] crainList = new Integer[crainNum];
        for(int i = 0 ; i < crainNum ; i++){
            crainList[i] = Integer.parseInt(firstLine[i]);
        }
        Arrays.sort(crainList, Collections.reverseOrder());

        int boxNum = Integer.parseInt(scan.nextLine());
        String[] secondLine = (scan.nextLine()).split(" ");
        ArrayList<Integer> boxList = new ArrayList<Integer>();
        for(int i = 0 ; i < boxNum ; i++){
            boxList.add(Integer.parseInt(secondLine[i]));
        }
        Collections.sort(boxList, Collections.reverseOrder());

        if(crainList[0] < boxList.get(0)){
            System.out.println(-1);

        }else{
            int result = 0;
            while(boxList.size() != 0){
                for(int i = 0 ; i < crainNum ; i++){
                    if(boxList.size() == 0){
                        break;
                    }else if(crainList[i] < boxList.get(boxList.size()-1)){
                        break;
                    }else{
                        for(int j = 0 ; j < boxList.size() ; j++){
                            if(crainList[i] >= boxList.get(j)){
                                boxList.remove(j);
                                break;
                            }
                        }
                    }
                }
                
                result++;
            }
            
            System.out.println(result);
        }

    }

}

 

 

 

후기

---

개인적으로 알고리즘을 풀 때, 시간 초과가 나면 해결하기가 정말 힘들다. 물론 금방 다른 방법을 찾아 해결하는 경우도 있지만, 오늘같이 해결방법을 찾지 못하는 경우엔 몇십 분, 길면 몇 시간까지도 해결하지 못하게 된다. 차라리 아예 틀려버리면 꼼꼼히 살펴봐 오류를 찾아내고 그것도 안된다면 반례를 찾아보면 되기 때문에 오히려 더 해결하기 쉽다. 하지만 시간 초과는 어쨌든 답 자체는 나오기 때문에 어렵다는 생각이 드는 것 같다.

 

특히 평일에는 퇴근 후 몇시간 정도밖에 공부할 시간이 없기 때문에 이런 부분에서 시간을 많이 빼앗기면 다른 공부를 할 수 없다. 당장 오늘도 시간초과를 해결하느라 계획한 공부를 전혀 하지 못했다;;; 

 

예전부터 느꼈지만 시간 초과에 있어 어려움을 많이 느끼고 있다. 효율적인 코드 작성을 지속적으로 공부해야겠다고 다시금 생각하게 되는 문제였다.