[백준 3015] 오아시스 재결합(C++)

오아시스 재결합

링크: http://www.acmicpc.net/problem/3015

 

문제

---

오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.

이 역사적인 순간을 맞이하기 위해 줄에서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해졌다.

두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.

줄에 서 있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.

문제 접근

• A와 B 사이에는 같거나 작은 값들만 존재해야 한다.
• 2 4 1 2 2 5 1의 경우 총 10개의 쌍이 존재한다.
  • (2,4), (4,1), (4,2), (4,2), (4,5), (1,2), (2,2), (2,5), (2,5), (5,1)

풀이 힌트

• stack의 top 값을 이용하여 볼 수 없는 값들을 제거하면서 진행한다.
• 연속된 값은 자신보다 같거나 큰 값들을 전부 볼 수 있다.

풀이 해설

• 스택의 형태
  삽입하려는 값과 top을 비교하여 해당 꼴을 유지하도록 한다.

• 스택의 활용
  stack은 pair<int, int>를 사용하여 value와 duplicated를 저장할 수 있도록 했다.
  마주볼 수 있는 쌍일 경우 cnt 변수에 duplicated 만큼 값을 추가하며 진행한다.

• 각 조건 별 해설

코드

• 주의사항
  • 쌍의 결과는 int 범위를 넘어갈 수 있다.
  • 비교하는 값이 top보다 작으면 top이 연속되고 있더라도 한 쌍만 볼 수 있다.
• 스택을 이용하여 쌍의 개수 구하기

// 첫 번째 값으로 스택 초기화
S.push({input[0], 1});
for (int i = 1; i < N; ++i) {
    // Top의 큰 값을 만날 때까지 증가
    while (!S.empty() && S.top().first < input[i]) {
        // 큰 값은 중복된 값을 모두 볼 수 있으므로 second 만큼 cnt 증가
        cnt += S.top().second;
        S.pop();
    }

    // top과 같은 값일 때 연속된 값을 모두 볼 수 있으므로 += top.second
    if (!S.empty() &&S.top().first == input[i]) {
        cnt += S.top().second;
        S.top().second += 1;
        // 해당 값보다 큰 값이 스택에 있다면 += 1
        if (S.size() > 1)
            cnt += 1;
        continue ;
    }
    // 현재 값이 제일 큰 값이 아니라면 cnt += 1
    else if (!S.empty()) {
        cnt += 1;
    }
    // 현재 값 push
    S.push({input[i], 1});
}
cout << cnt;

 

※ 오류나 개선점이 있다면 알려주세요 :) 신속히 수정하겠습니다.