[테코테코1.5 1-05] 버스

💡테코테코 시즌 1.5 1회 모임 off-site 문제 풀이입니다. (2025.01.12)

 

문제

 

출처: 프로그래머스 - PCCE 기출문제 07. 버스

 

내용

 

영진이는 약속장소에 가기 위해 버스를 타려고 합니다. 버스에는 좌석이 총 seat개만큼 있습니다. 영진이는 버스 좌석에 앉아서 갈 수 있을지 궁금해합니다. 기점에서 출발한 버스가 영진이가 기다리는 정거장에 도착하기 전에 방문하는 각 정거장에서 승/하차한 승객 정보가 주어질 때, 영진이가 버스에 탄 순간 빈 좌석은 몇 개인지 구해주세요. 영진이가 기다리는 정거장에서는 영진이가 제일 먼저 버스에 탑승하며, 이전 정거장에서 버스에 탑승한 승객들은 남는 좌석이 있다면 항상 앉는다고 가정합니다. 또, 기점에서 출발하는 버스에는 승객이 0명 타고 있습니다.

예를 들어 다음은 좌석이 5개인 버스에 각 정거장에서 승/하차한 승객 정보를 나타냅니다. 영진이는 4번 정거장에서 기다리고 있으며, "On"은 승차한 승객, "Off"는 하차한 승객을 의미합니다.

 

- 1번 정거장 : ["On", "On", "On"] (3명 승차, 0명 하차)
- 2번 정거장 : ["Off", "On", "-"] (1명 승차, 1명 하차)
- 3번 정거장 : ["Off", "-", "-"]  (0명 승차, 1명 하차)

 

위와 같은 경우, 1번 정거장에서 3명이 승차하고, 2번 정거장에서 1명 승차 1명 하차, 3번 정거장에서 1명이 하차했으므로 4번 정거장에 도착한 버스에는 2명이 타고 있습니다. 4번 정거장에서는 영진이가 가장 먼저 탑승하므로, 남아있는 좌석 수는 3개입니다.

주어진 solution함수는 버스의 좌석 개수 seat, 기점에서 출발한 버스가 순서대로 방문한 정거장에서 승객이 승/하차한 정보를 담은 2차원 문자열 리스트 passengers가 주어질 때, 버스에 남아있는 좌석의 개수를 return 하는 함수입니다. solution 함수가 올바르게 작동하도록 빈칸을 채워 solution함수를 완성해 주세요.

• java를 응시하는 경우 리스트는 배열, 함수는 메소드와 동일한 의미이니 풀이에 참고해주세요.
  • ex) solution 함수가 올바르게 작동하도록 한 줄을 수정해 주세요. => solution 메소드가 올바르게 작동하도록 한 줄을 수정해 주세요.

 

 

제약 조건

• 1 ≤ seat ≤ 30
• 1 ≤ passengers의 길이 ≤ 10
• 1 ≤ passengers[i]의 길이 ≤ 20
  • passengers[0]은 1번 정거장, passengers[1]은 2번 정거장, … passengers[i]는 i + 1번 정거장의 정보입니다.
  • passengers의 길이가 n이라면, 영진이는 n + 1번 정거장에서 기다리고 있습니다.
• passengers[i]의 길이는 모두 동일합니다.
• passengers[i]의 원소는 "On", "Off" 또는 "-"입니다.
  • "-"는 배열의 가로(열) 길이를 맞추기 위한 요소로, 아무런 의미도 없습니다.
  • "-"가 "On", "Off" 사이에 있는 경우는 없습니다.

 

기록하기

💡 어디까지 생각해봤는지 단계적으로 기록해봅니다.

 

어떤 알고리즘을 적용하려 했나요?

 

스택을 사용하고 싶다. (만물스택설 ㅋㅋ) 그러나 문제는 숫자 연산으로 먼저 풀이되어 있다.

 

적용 근거는 무엇인가요?

 

순서 상관없이 버스 승하차 인원에 따라 남은 버스 좌석을 구하면 되므로 스택 사용해도 될 것 같았다.
하지만 숫자 연산으로 먼저 풀이되어 있으니 문제에 맞춰 풀이해보고 스택으로도 가능하면 스택으로 변형도 해보겠다.

 

 

풀이

풀이 시간

 

시작 시각	종료 시각	총 소요 시간
12:53	13:06	13분

 

문제 분석

 

입력값 분석

💡 입력값을 분석하면 문제에서 요구하는 알고리즘의 시간 복잡도를 간접적으로 파악할 수 있습니다.

 

seat	passengers	result
5	[["On", "On", "On"], ["Off", "On", "-"], ["Off", "-", "-"]]	3
10	[["On", "On", "On", "On", "On", "On", "On", "On", "-", "-"], ["On", "On", "Off", "Off", "Off", "On", "On", "-", "-", "-"], ["On", "On", "On", "Off", "On", "On", "On", "Off", "Off", "Off"], ["On", "On", "Off", "-", "-", "-", "-", "-", "-", "-"]]	0

 

 

입출력 예 #1

• 지문과 동일합니다

 

입출력 예 #2

 

아래와 같이 승객이 타고 내렸고 마지막으로 12명이 버스에 타고 있으므로 남은 좌석은 0개입니다.

- 1번 정거장 : ["On", "On", "On", "On", "On", "On", "On", "On", "-", "-"] (8명 승차, 0명 하차)
- 2번 정거장 : ["On", "On", "Off", "Off", "Off", "On", "On", "-", "-", "-"] (4명 승차, 3명 하차)
- 3번 정거장 : ["On", "On", "On", "Off", "On", "On", "On", "Off", "Off", "Off"] (6명 승차, 4명 하차)
- 4번 정거장 : ["On", "On", "Off", "-", "-", "-", "-", "-", "-", "-"] (2명 승차, 1명 하차)

 

 

의사 코드 작성

💡 의사 코드는 동작 중심으로 작성하는 것이 중요합니다.

💡 의사 코드는 문제 해결 순서로 작성합니다.

💡 의사 코드를 충분히 테스트해봅니다.

 

(기존 코드는 이렇게 구현되어 있었다.)

class Solution {
    public int solution(int seat, String[][] passengers) {
        int num_passenger = 0;
        for(int i=0; i<passengers.length; i++){
            num_passenger += func;
            num_passenger -= func;
        }
        int answer = func;
        return answer;
    }

    public int func1(int num){
        if(0 > num){
            return 0;
        }
        else{
            return num;
        }
    }
    public int func2(int num){
        if(num > 0){
            return 0;
        }
        else{
            return num;
        }
    }

    public int func3(String[] station){
        int num = 0;
        for(int i=0; i<station.length; i++){
            if(station[i].equals("Off")){
                num += 1;
            }
        }
        return num;
    }

    public int func4(String[] station){
        int num = 0;
        for(int i=0; i<station.length; i++){
            if(station[i].equals("On")){
                num += 1;
            }
        }
        return num;
    }
}

 

 

구현

class Solution {
    public int solution(int seat, String[][] passengers) {
        int num_passenger = 0;
        for(int i=0; i<passengers.length; i++){
            num_passenger += func4(passengers[i]);
            num_passenger -= func3(passengers[i]);
        }
        int answer = func1(seat - num_passenger);
        return answer;
    }

    public int func1(int num){
        if(0 > num){
            return 0;
        }
        else{
            return num;
        }
    }
    public int func2(int num){
        if(num > 0){
            return 0;
        }
        else{
            return num;
        }
    }

    public int func3(String[] station){
        int num = 0;
        for(int i=0; i<station.length; i++){
            if(station[i].equals("Off")){
                num += 1;
            }
        }
        return num;
    }

    public int func4(String[] station){
        int num = 0;
        for(int i=0; i<station.length; i++){
            if(station[i].equals("On")){
                num += 1;
            }
        }
        return num;
    }
}

public static int solution(int seat, String[][] passengers) {  
    Stack<String> stack = new Stack<>();  

    for (String[] passenger : passengers) {  
        for (String p : passenger) {  
            if (p.equals("On")) {  
                stack.push(p);  
            } else if (p.equals("Off") && !stack.isEmpty()) {  
                stack.pop();  
            }  
        }  
    }  

    return Math.max(0, seat - stack.size());  
}

 

복기하기

답안과 나의 풀이를 비교해보세요

• 근데 뭘해도 시간복잡도는 O(N^2)라 메모리 효율 생각하면 숫자 연산 방식으로 하는 게 나을지도..