-
백준 3015번 오아시스 재결합: C 언어 풀이Programming/PS 2023. 9. 30. 22:49
백준 3015 오아시스 재결합 문제의 C언어 해설입니다.
내림차순 스택을 이용한 구현에서, 시간 초과를 해결하기 위해 키가 같은 사람들을 하나의 구조체로 묶어서 처리하는 방법을 설명합니다.
최종 코드는 C언어와 파이썬, 두 언어로 작성하였습니다.전략
역시나 내림차순 스택
오큰수 문제 와 유사한 문제다.
스택에 사람들의 키를 하나씩 저장한다.
스택은 항상 내림차순으로 정렬되어 있다고 가정한다.내림차순이 깨지는 순간을 살펴보자. 9, 8, 3, 2 다음 7이 나온 상황이다.
키가 7인 사람과 스택안에 있는 사람들, 8, 3, 2는 서로 마주 볼 수 있다.
7이 가로막기 때문에, 이후 어떤 숫자가 나오든 3, 2의 키를 가진 사람은 이후 사람을 볼 수 없다.이게 뭔가 직관적으로 생각해보면 조금 이상한 면이 있다.
이를테면 키가 10인 사람이 나왔다고 하자. 9, 8, 3, 2, 7, 10 이렇게 한 줄로 서게 될것이다.
키가 2인 사람이 올려다보면 10과 마주 볼 수 있을 것 같다. 높은 아파트 뒤로 남산타워를 볼 수 있으니까.하지만 직관 대신 문제의 정의에 집중해야한다.
두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.
2보다 큰 7이 중간에 있으므로 2는 10을 볼 수 없다.
따라서 7을 넣기 전에 3, 2를 스택에서 pop 해준다. pop 할 때마다 서로 볼 수 있는 쌍의 수를 하나씩 더해준다.
스택은 9, 8, 7 이 된다. 내림차순이 깨지지 않는다.
7은 9와는 마주볼 수 없지만 바로 옆에 있는 8과는 마주볼 수 있다. 볼 수 있는 쌍 카운트를 하나 더해준다.문제는 키가 같은 경우
문제의 문제의 정의를 다시 한번 살펴보자.
두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.
또 다시, 비직관적이지만, 키가 같은 사람이 5명이 일렬로 서있다면 5명이 전부 서로를 쳐다볼 수 있다.
5명이 서로 쳐다보면서 4+3+2+1, 10개의 마주보는 쌍을 만들어낸다.
101명이 전부 키가 같아도 서로를 쳐다볼 수 있다. 5050개의 쌍이 만들어진다.그러면 내림차순 스택에서 키가 같은 친구들을 어떻게 저장해야 할까?
5, 3, 2, 2 다음 2가 오는 상황을 생각해보자.
스택을 훑으면서 같은 키를 가진 사람이 나오면 pop 하지 않고 다음 원소를 확인하는 방법을 고려해볼 수 있겠다.다음 코드처럼 말이다.
for (int i = 0; i < num_people; i++) { // Pop shorter people while (top != EMPTY && heights[i] > stack[top]) { top--; pairs_count++; } // People with same height is not popped but counted for (int j = top; top != EMPTY && stack[j] == heights[i]; j--) { pairs_count++; } // If there remains a taller person in the stack, count + 1 if (top != EMPTY && stack[0] != heights[i]) { pairs_count++; } // Push stack[++top] = heights[i]; }그러나 이 방식으로 코드를 짜서 제출하면 시간 초과가 뜬다.
학창시절 배운 등차수열의 합공식을 생각해보자.
같은 키를 가진 사람이 N이라고 하면 서로 마주 보는 걸 확인하기 위한 조작이 그 제곱만큼 필요하다.
아마 오아시스 공연에 키가 똑같은 사람이 정말 많아서 시간초과가 나는 모양이다.이를 해결하기 위해 스택에 각 사람의 키가 아닌 키가 같은 사람끼리 묶은 집합을 넣어준다.
즉 키와 키가 같은 사람의 수를 담는 구조체를 하나 정의해서 스택에 넣어주는 방법이다.
키가 107인 사람이 107명 연속으로 서있다고 해보자. 여기서 108번째 키 107인간이 추가된다.
이때 스택 맨 위에 있는
{키: 107, 인원: 107명}을{키:107, 인원: 108명}으로 수정해주기만 하면 된다.
마주 보는 인원도 +107 만큼 더해주면 끝이다.만일 이 다음에 키가 108인 사람이 와도, 107번 pop할 필요가 없다.
{키:107, 인원: 108명}원소를 pop 하고 인원을 +108 만큼 더해주면 된다.최종 코드
C언어 코드
추가적으로 키가 같은 사람일 때의 조작을 내림차순 스택 부분에 통합 시켰다.
이러면 같은 키 일 때 구조체를 굳이 Pop 하고 나중에 도로 Push 하게 된다.
이는 스택이 비어있지 않을 때 카운터를 +1 한다던가 new를 push하는 등의 로직을 별다른 조건문 없이 깔끔하게 수행할 수 있게 도와준다.#include <stdio.h> #define MAX_PEOPLE_SIZE 500000 #define EMPTY -1 // People grouped by same height struct height_group { int height; int size; }; int main(void) { int num_people; scanf("%d", &num_people); struct height_group stack[MAX_PEOPLE_SIZE]; int top = EMPTY; long pairs_count = -1; struct height_group new; for (int i = 0; i < num_people; i++) { scanf("%d", &new.height); new.size = 1; // Pop shorter people, count pairs while (top != EMPTY && stack[top].height <= new.height) { pairs_count += stack[top].size; // If same height, merge into new if (new.height == stack[top].height) { new.size += stack[top].size; } // Push top--; } // Taller person exists, count +1 if (top != EMPTY) { pairs_count++; } // Push stack[++top] = new; } printf("%ld", pairs_count); }Python 코드
어쩌다 파이썬으로도 짜게 되어 추가함.
import sys from collections import namedtuple MAX_HEIGHT = 2 ** 31 HeightGroup = namedtuple('HeightGroup', ['height', 'cnt']) n_people, *heights = map(int, sys.stdin.buffer.read().splitlines()) stack = [HeightGroup(MAX_HEIGHT, 0)] observable_pair_cnt = 0 for height in heights: curr = HeightGroup(height, 1) while stack[-1].height <= height: if stack[-1].height == height: curr = HeightGroup(height, stack[-1].cnt + 1) observable_pair_cnt += stack[-1].cnt stack.pop() observable_pair_cnt += 1 if len(stack) > 1 else 0 stack.append(curr) print(observable_pair_cnt)