백준 2493 C언어

 

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

2493번: 탑

---

문제

KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 

예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한다.

탑들의 개수 N과 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 작성하라. 

---

입력

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.

---

출력

첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.

---

 

정말 많이 풀었다..

 

문제를 간단히 해보자면 다섯 개의 탑이 있고 탑의 높이가 [6,9,5,7,4]일때 탑의 왼쪽 방향으로 레이저를 쏘는데 

6은 왼쪽에 탑이 없어서 수신하지 못하고 9는 왼쪽에 탑이 있지만(6) , 탑이 9보다 작으므로 수신하지 못한다.

 

5는 9인 탑이 수신하고, 7은 9인탑이 수신하고, 4는 7인 탑이 수신한다.

 

간단히 그림으로 그리자면

 

0은 수신하지 못함을 나타낸다.

 

이런식으로 된다.

 

---

해결방안: 스택의 구조체를 topindex값, 배열인 arr, 그리고 배열의 인덱스값을 저장하는 Index배열 이렇게 정의한다.

--1부터 N까지 for문을 돌리면서

 

1) 스택이 비어있으면 0을 출력하고 Push연산을 한다. (이 때 Index배열에 배열의 인덱스 값이 들어간다)

 

2) 스택이 비어있지 않고 스택의 top값이 배열의 값보다 크다면 top값의 Index값을 출력하고 Push연산을 한다.

 

4)스택이 비어있지 않고 스택의 top값이 배열의 값보다 작다면

 

Pop연산을 한다.

 

while문을 돌리면서

Pop연산 이후 스택이 비어있다 ->0을 출력하고 Push연산을 한다. ->break문을 통해 탈출

Pop연산 이후 스택의 top값이 배열의 값보다 크다면 ->스택의top값의 인덱스를 출력하고 ->break문을 통해 탈출

 

---

N = 5

탑이 [6,9,5,7,4]일떄

 

1) 6->스택이 비어있으므로 0출력후 Push(6,1) 1은 6의 인덱스 값.

 

2) 9->스택의 top값보다 배열의 값인 9가 더 크므로 

 

Pop연산을 수행 ->Pop연산 후 스택이 비어있으므로 0출력후 9 Push(9,2) 2는 9의 인덱스 값.

 

3) 5->스택의 top값이 배열의 값인 5보다 크므로

 

top의 인덱스 값 출력(9,2에서 2출력) -> Push연산 (9,2),(5,3) 3은 5의 인덱스 값

 

4) 7->스택의 top값(5)보다 배열의 값(7)이 더 크므로

 

Pop연산을 수행 ->Pop연산 후 top값은 5->9로 바뀜.

 

이 때 9가 7보다 크므로 top의 인덱스 값인 2를 출력 후 Push(7,4)

 

스택의 상태 ->(9,2)(7,4)

 

5) 4->스택의 top값(7)이 배열의 값인 4보다 크므로 

 

top의 인덱스 출력 후 Push.

 

---

전체 소스 코드 ->

#include <stdio.h>

#define True 1

#define False 0

 

 

typedef struct _CSTACK{

    int arr[500000]; //탑의 높이를 저장할 용도

    int idx[500000]; //탑의 인덱스를 저장할 용도

    int topindex;

}cstack;

 

typedef cstack Stack;

 

void Stackinit(Stack *pstack){

    pstack->topindex = -1;

}

 

int Empty(Stack *pstack){

    if(pstack->topindex == -1){

        return True;

    }

    else{

        return False;

    }

}

 

void Push(Stack *pstack,int data,int i){

    pstack->topindex = pstack->topindex + 1;

    pstack->arr[pstack->topindex] = data;

    pstack->idx[pstack->topindex] = i;

}

 

void Pop(Stack *pstack){

    pstack->topindex = pstack->topindex - 1;

}

 

int Top(Stack *pstack){

    return pstack->arr[pstack->topindex];

}

 

int Topindex(Stack *pstack){

    return pstack->idx[pstack->topindex];

}

 

int main(void){

    Stack stack;

    Stackinit(&stack);

 

    int n;

    scanf("%d",&n);

 

    int arr[500010];

    for(int i = 1;i<=n;i++){

        scanf("%d",&arr[i]);

    }

 

    for(int i = 1;i<=n;i++){

        if(Empty(&stack)){ //스택이 비어있을 때

            printf("0 ");

            Push(&stack,arr[i],i);

        }

        else if(Top(&stack) > arr[i]){ //스택의 Top값이 배열의 값보다 클 때

            printf("%d ",Topindex(&stack));

            Push(&stack,arr[i],i);

        }

        else if(Top(&stack) < arr[i]){ //스택의 Top값이 배열의 값보다 작을 때

            while(!Empty(&stack)){ //스택이 비어있지 않다면

                Pop(&stack); //Pop연산

 

                if(Empty(&stack)){ //Pop연산 후 스택이 비었다 -> 0찍고 배열의 값 Push

                    printf("0 ");

                    Push(&stack,arr[i],i);

                    break;

                }

             else if(Top(&stack) > arr[i]){//Pop연산 후 Top값이 배열의 값보다 크다->Top인덱스값 찍고 Push

                    printf("%d ",Topindex(&stack));

                    Push(&stack,arr[i],i);

                    break;

                }

            }

        }

    }

}