[JAVA] 백준 12789. 도키도키 간식드리미

이 글은 읽는데 약 7분이 걸립니다.

※개인 공부 목적의 정리글입니다.
이 글의 내용이 최선의 해답은 아닐 수 있습니다.

문제

인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두근 설레서 시험 공부에 집중을 못 한다. 이번 중간고사에서도 역시 승환이는 설레는 가슴을 안고 간식을 받기 위해 미리 공지된 장소에 시간 맞춰 도착했다. 그런데 이게 무슨 날벼락인가! 그 곳에는 이미 모든 학생들이 모여있었고, 승환이는 마지막 번호표를 받게 되었다. 설상가상으로 몇몇 양심에 털이 난 학생들이 새치기를 거듭한 끝에 대기열의 순서마저 엉망이 되고 말았다. 간식을 나눠주고 있던 인규는 학우들의 터져 나오는 불만에 번호표 순서로만 간식을 줄 수 있다고 말했다. 

그제야 학생들이 순서대로 줄을 서려고 했지만 공간이 너무 협소해서 마음대로 이동할 수 없었다. 다행히도 대기열의 왼쪽에는 1열로 설 수 있는 공간이 존재하여 이 공간을 잘 이용하면 모두가 순서대로 간식을 받을 수 있을지도 모른다. 자칫 간식을 못 받게 될지도 모른다는 위기감을 느낀 승환이는 자신의 컴퓨터 알고리즘적 지식을 활용해 과연 모든 사람들이 순서대로 간식을 받을 수 있는지 확인하는 프로그램을 만들기로 했다. 만약 불가능 하다면 승환이는 이번 중간고사를 망치게 될 것 이고 가능하다면 힘을 얻어 중간고사를 잘 볼 수 있을지도 모른다.

사람들은 현재 1열로 줄을 서있고, 맨 앞의 사람만 이동이 가능하다. 인규는 번호표 순서대로만 통과할 수 있는 라인을 만들어 두었다. 이 라인과 대기열의 맨 앞 사람 사이에는 한 사람씩 1열이 들어갈 수 있는 공간이 있다. 현재 대기열의 사람들은 이 공간으로 올 수 있지만 반대는 불가능하다. 승환이를 도와 프로그램을 완성하라.

현재 간식 배부 공간을 그림으로 나타내면 다음과 같다.

위 예제는 다음 그림과 같이 움직였을 때 모두가 순서대로 간식을 받을 수 있다..

입력

입력의 첫째 줄에는 현재 승환이의 앞에 서 있는 학생들의 수 N(1 ≤ N ≤ 1,000,자연수)이 주어진다.

다음 줄에는 승환이 앞에 서있는 모든 학생들의 번호표(1,2,…,N) 순서가 앞에서부터 뒤 순서로 주어진다.

출력

승환이가 무사히 간식을 받을 수 있으면 “Nice”(따옴표는 제외)를 출력하고 그렇지 않다면 “Sad”(따옴표는 제외)를 출력한다.

풀이

한 줄의 공간에 사람들이 섞인 상태로 줄을 서있으며 여기서는 선입선출이 되고, 여분의 공간에 사람을 잠시 옮겨둘 수 있으며 여기서는 후입선출이된다.

이 두 공간을 이용하여 1번부터 순서대로 사람을 통과시켜야하며, 이것이 가능한지 여부를 판별하는 알고리즘을 짜는 문제이다.

편의상 우측 공간을 메인, 아래측 공간을 서브라고 표현하겠다.

메인 공간의 순서는 위 그림에서 보이는 순서대로 입력이 주어진다. 선입선출이므로 이부분은 큐로 만들어야하지만… 나는 아직 큐를 안써봐서 입력의 순서를 반전시켜 그냥 스택에 넣었다…

서브 공간은 먼저 들어온 번호가 가장 안쪽으로 들어가서 나중에 들어간 사람이 가장 먼저 나오게 된다. 후입선출이므로 이건 그냥 스택으로 구현가능하다.

나는 이런식으로 풀었다.

일단 순서를 기억하는 변수가 order가 있다. 시작값은 1이다. 이후 1번이 통과되면 2로 올리고…
하여튼 메인 라인의 첫번째 번호가 order와 같은지 체크한다. 같으면 메인에서 pop하면 되고, 아니라면 pop한 후 서브 라인으로 push한다.

두번째에서도 메인 라인의 다음 값을 꺼내와 order와 비교한다. order와 다르면 서브 라인의 값을 꺼내와 또 비교한다. 이 값과도 다르면 메인 라인의 값을 pop해서 마찬가지로 서브 라인에 push한다.

말로 설명하니 좀 헷갈리는데 코드로 보자.

public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();

int N = Integer.parseInt(br.readLine());
String[] inputs = br.readLine().split(" ");
Stack<Integer> stack = new Stack<>();  // 메인 라인(원래는 큐로 하는게 자연스러움)
Stack<Integer> temp = new Stack<>();  // 서브 라인(원래 스택이 기본)
for(int i=N-1; i>=0; i--){
    stack.push(Integer.parseInt(inputs[i]));  // 큐를 써야하는데 스택을 써서 순서 반전후 push했음
}

int order = 1;  // 현재 나가야 하는 번호를 저장. 1번 부터 시작이므로 기본값은 1
while(!stack.isEmpty()){  // 메인 통로가 빌 때까지 반복
    int target = stack.peek();  // 먼저 메인라인의 다음 사람의 번호를 가져옴
    
    if(target == order){  // 나가야 하는 번호와 일치하면
        stack.pop();  // 바로 메인라인에서 빼고
        order++;  // 나가야 하는 번호는 1더해 다음 번호로 저장
    }else{  // 나가야 하는 번호가 아니면
        if(!temp.isEmpty()){  // 서브 라인이 비어있지 않으면
            if(temp.peek() == order){  // 서브라인에서 나갈 수 있는 번호가 order와 같으면
                temp.pop();  // 서브 라인에서 빼고
                order++;  // order+1한다
            }else{  // 서브라인에서 가져온 번호도 나가야 하는 번호가 아니면
                temp.push(stack.pop());  // 메인라인의 번호를 서브 라인으로 일단 옮겨둠
            }
        }else{  // 서브 라인이 비었으면
            temp.push(stack.pop());  // 바로 서브 라인으로 옮김
        }
    }
}

// 이제 메인라인은 내보낼 대로 내보냈으므로 서브 라인에서도 내보낸다.
while(!temp.isEmpty()){  // 서브라인이 빌 때까지 반복
    if(temp.pop() == order){  // 서브라인에서 꺼낸 번호가 나가야 하는 번호이면 
        order++;  // 다음 번호로 (pop을 조건부에서 이미 했음)
    }else{  // 만약 꺼낸 번호가 나가야하는 번호가 아니라면 그냥 끝이다. 다시 메인으로도 못넣으니까
        break;
    }
}

if(stack.isEmpty() && temp.isEmpty()){
  // 두 라인이 모두 비었다면 정상적으로 모두 빠졌다는 뜻
    sb.append("Nice");
}else{
    sb.append("Sad");
}

System.out.println(sb.toString());
br.close();
}

여담

도키도키(ドキドキ)는 일본어로 두근두근이라는 뜻이다.

댓글