[2493] 탑 - μ‹œκ°„μ΄ˆκ³Ό

2020. 4. 20. 16:04Β· Algorithm/πŸ‘ 문제
λͺ©μ°¨
  1. 문제
  2. μž…λ ₯
  3. 좜λ ₯
λ°˜μ‘ν˜•

문제

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을 좜λ ₯ν•œλ‹€.


문제 풀이

μ²˜μŒμ—λŠ” λ‹¨μˆœνžˆ ν•œλ²ˆμ— νƒ‘λ“€μ˜ 높이λ₯Ό λ°›κ³ , μ œκ±°ν•΄λ‚˜κ°€λŠ” 방식을 μ‚¬μš©ν–ˆλ‹€.

#include <iostream>
#include <stack>

using namespace std;
stack<pair<int, int>> s;

int arr[500000];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		s.push({ i,tmp }); // index와 νƒ‘μ˜ 높이
	}

	for (int i = 0; i < n; i++) {
		stack<pair<int, int>> cur_s = s;
		while (cur_s.size() != (n - i)) {
			cur_s.pop();
		}
		int prev_idx = cur_s.top().first;
		int prev_value = cur_s.top().second;
		cur_s.pop();

		int result = 0;
		while (!cur_s.empty()) {
			if (cur_s.top().second > prev_value) {
				result = cur_s.top().first; // ν•΄λ‹Ή νƒ‘μ˜ 인덱슀
				break;
			}
			cur_s.pop();
		}
		result == 0 ? arr[prev_idx] = 0 : arr[prev_idx] = result + 1;
	}

	for (int i = 0; i < n; i++) {
		cout << arr[i] << " ";
	}
}

pairλ₯Ό μ‚¬μš©ν•΄ νƒ‘μ˜ μΈλ±μŠ€μ™€ 높이λ₯Ό μ €μž₯ν•˜κ³  (pair.first == 인덱슀, pair.second == 높이)

κ°€μž₯ 였λ₯Έμͺ½(4)의 탑뢀터 어디에 μ‹ ν˜Έκ°€ λ„λ‹¬ν•˜λŠ”μ§€ κ³„μ‚°ν–ˆλ‹€.

ν•˜μ§€λ§Œ, μ΄λ ‡κ²Œ ν‘ΈλŠ” λ°©μ‹μ˜ λ¬Έμ œλŠ” 1. 계속 stack을 λ³΅μ‚¬ν•˜κ³  2. μ‹œκ°„μ΄ μ˜€λž˜κ±Έλ¦°λ‹€λŠ” 점이닀.

즉 탑이 6 9 5 7 4 이라면, 높이 4의 탑이 어디에 λ„λ‹¬ν•˜λŠ”μ§€ μ²΄ν¬ν•œλ‹€. 

λͺ¨λ“  탑을 ν™•μΈν• λ•ŒκΉŒμ§€(s.empty()) λΉ„κ΅ν•˜λŠ” 탑(4)κ³Ό stack의 top을 λΉ„κ΅ν•œλ‹€.

λΉ„κ΅ν•˜λŠ” 탑 - 4 / stack의 top - 7 --> μ‹ ν˜Έκ°€ λ„λ‹¬ν•œλ‹€.

(계속 stack을 λ³΅μ‚¬ν•œλ‹€) κ·Έ λ‹€μŒμœΌλ‘  stack에 6 9 5 7 4 λ₯Ό λ³΅μ‚¬ν•˜κ³  6 9 5 7 4λ₯Ό μ œκ±°ν•΄  

높이 7의 탑이 어디에 λ„λ‹¬ν•˜λŠ”μ§€ μ²΄ν¬ν•œλ‹€. 

λΉ„κ΅ν•˜λŠ” 탑 - 7 / stack의 top - 5 --> μ‹ ν˜Έκ°€ λ„λ‹¬ν•˜μ§€ μ•ŠλŠ”λ‹€ --> 더 높은 탑이 μžˆλŠ”μ§€ ν™•μΈν•œλ‹€.(s.pop())

λΉ„κ΅ν•˜λŠ” 탑 - 7 / stack의 top - 9 --> μ‹ ν˜Έκ°€ λ„λ‹¬ν•œλ‹€.


μ΄λŸ°μ‹μœΌλ‘œ 맨 처음 탑인 6κΉŒμ§€ 원본 stack 볡사 -> 이미 λΉ„κ΅ν•œ 탑듀 제거 -> 비ꡐ할 탑 선택 -> stack의 topκ³Ό 비ꡐ

stack의 top 보닀 λΉ„κ΅ν•˜λŠ” 탑이 λ†’λ‹€λ©΄ -> μ‹ ν˜Έ 도달 x -> 더 높은 탑 μžˆλŠ”μ§€ 확인

stack의 top 이 λΉ„κ΅ν•˜λŠ” 탑보닀 λ†’λ‹€λ©΄ -> μ‹ ν˜Έ 도달 -> break 

λ₯Ό λ°˜λ³΅ν•œλ‹€.

ν•˜μ§€λ§Œ, μ΄λ ‡κ²Œ ν•˜λ©΄ μž…λ ₯의 μˆ˜κ°€ 크기 λ•Œλ¬Έμ— μ‹œκ°„μ΄ˆκ³Όλ₯Ό ν”Όν•  수 μ—†λ‹€. κ·Έλž˜μ„œ ꡬ글링을 톡해 λ‹€λ₯Έ 방법을 κ³ μ•ˆν•΄λƒˆλ‹€. κ·Έ 방법은 λ‹€μŒ κ²Œμ‹œλ¬Όμ—μ„œ μ†Œκ°œν•˜λ„λ‘ ν•˜κ² λ‹€.

(μ°Έκ³  : [2493] 탑)

λ°˜μ‘ν˜•
  1. 문제
  2. μž…λ ₯
  3. 좜λ ₯
'Algorithm/πŸ‘ 문제' μΉ΄ν…Œκ³ λ¦¬μ˜ λ‹€λ₯Έ κΈ€
  • [5430] AC
  • [2493] 탑
  • [2108] 톡계학
  • [2609] μ΅œλŒ€κ³΅μ•½μˆ˜μ™€ μ΅œλŒ€κ³΅λ°°μˆ˜
YURIπŸ•πŸ“πŸΆ
YURIπŸ•πŸ“πŸΆ
λ°˜μ‘ν˜•
YURIπŸ•πŸ“πŸΆ
πŸ•
YURIπŸ•πŸ“πŸΆ
전체
였늘
μ–΄μ œ
  • λΆ„λ₯˜ 전체보기 (96)
    • Today I Learned (0)
      • 2022 (16)
      • 2023 (6)
      • 2024 (0)
    • Project (0)
    • Study (41)
      • OOP (1)
      • Java (2)
      • Spring (22)
      • Kafka (3)
      • Web (1)
      • Network (4)
      • MSA (2)
      • ETC (6)
    • Algorithm (30)
      • πŸ‘ 문제 (30)
    • Book (1)
    • Daily Life (0)

인기 κΈ€

졜근 λŒ“κΈ€

졜근 κΈ€

hELLO Β· Designed By μ •μƒμš°.v4.2.0
YURIπŸ•πŸ“πŸΆ
[2493] 탑 - μ‹œκ°„μ΄ˆκ³Ό
μƒλ‹¨μœΌλ‘œ

ν‹°μŠ€ν† λ¦¬νˆ΄λ°”

κ°œμΈμ •λ³΄

  • ν‹°μŠ€ν† λ¦¬ ν™ˆ
  • 포럼
  • 둜그인

단좕킀

λ‚΄ λΈ”λ‘œκ·Έ

λ‚΄ λΈ”λ‘œκ·Έ - κ΄€λ¦¬μž ν™ˆ μ „ν™˜
Q
Q
μƒˆ κΈ€ μ“°κΈ°
W
W

λΈ”λ‘œκ·Έ κ²Œμ‹œκΈ€

κΈ€ μˆ˜μ • (κΆŒν•œ μžˆλŠ” 경우)
E
E
λŒ“κΈ€ μ˜μ—­μœΌλ‘œ 이동
C
C

λͺ¨λ“  μ˜μ—­

이 νŽ˜μ΄μ§€μ˜ URL 볡사
S
S
맨 μœ„λ‘œ 이동
T
T
ν‹°μŠ€ν† λ¦¬ ν™ˆ 이동
H
H
단좕킀 μ•ˆλ‚΄
Shift + /
⇧ + /

* λ‹¨μΆ•ν‚€λŠ” ν•œκΈ€/영문 λŒ€μ†Œλ¬Έμžλ‘œ 이용 κ°€λŠ₯ν•˜λ©°, ν‹°μŠ€ν† λ¦¬ κΈ°λ³Έ λ„λ©”μΈμ—μ„œλ§Œ λ™μž‘ν•©λ‹ˆλ‹€.