YURI๐Ÿ•๐Ÿ“๐Ÿถ 2020. 4. 20. 16:23
๋ฐ˜์‘ํ˜•
๋”๋ณด๊ธฐ

๋ฌธ์ œ

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์„ ์ถœ๋ ฅํ•œ๋‹ค.


๋ฌธ์ œ ํ’€์ด

์ด์ „ ๊ฒŒ์‹œ๋ฌผ์˜ ๋ฐฉ์‹์œผ๋ก  ์‹œ๊ฐ„์ดˆ๊ณผ๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์—†์–ด์„œ ์•„์˜ˆ ๋‹ค๋ฅธ ๋ฐฉ๋ฒ•์œผ๋กœ ๋„์ „ํ–ˆ๋‹ค(๊ตฌ๊ธ€๋ง.. ์ข‹๋‹ค)

ํ•˜๋‚˜์”ฉ ํƒ‘์˜ ๋†’์ด๋ฅผ ์ž…๋ ฅ๋ฐ›์„ ๋•Œ๋งˆ๋‹ค ๋น„๊ตํ•˜๋Š” ๋ฐฉ์‹์ด๋‹ค.

1. stack์ด ๋น„์–ด์žˆ๋‹ค๋ฉด ์‹ ํ˜ธ๋ฅผ ๋ฐ›์„ ํƒ‘์ด ์กด์žฌํ•˜์ง€ ์•Š๋Š”๋‹ค. -> ๊ฒฐ๊ณผ : 0

2. stack์˜ top๋ณด๋‹ค ๋น„๊ตํ•˜๋Š” ํƒ‘์˜ ๋†’์ด๊ฐ€ ๋‚ฎ๋‹ค๋ฉด ์‹ ํ˜ธ๋ฅผ ๋ฐ›๋Š” ํƒ‘์€ ํ˜„์žฌ stack์˜ top์ด๊ณ , ๋น„๊ตํ•˜๋Š” ํƒ‘๋„ stack์— pushํ•œ๋‹ค.

3. stack์˜ top๋ณด๋‹ค ๋น„๊ตํ•˜๋Š” ํƒ‘์˜ ๋†’์ด๊ฐ€ ๋†’๋‹ค๋ฉด stack์— ์žˆ๋Š” ๋ชจ๋“  ํƒ‘๋“ค๊ณผ ๋†’์ด๋ฅผ ๋น„๊ตํ•ด๋ณธ๋‹ค. stack์ด empty๊ฐ€ ๋˜๋ฉด ์‹ ํ˜ธ๋ฅผ ๋ฐ›์„ ํƒ‘์ด ์กด์žฌํ•˜์ง€ ์•Š์Œ์œผ๋กœ -> ๊ฒฐ๊ณผ : 0

ํ•ด๋‹น ์„ค๋ช…์„ ๊ฐ„๋‹จํžˆ ๊ทธ๋ฆผ์œผ๋กœ ํ‘œํ˜„ํ–ˆ๋‹ค.

๊ทธ๋ฆผ์œผ๋กœ ๋ณด๋Š”๊ฒŒ ์ดํ•ด๊ฐ€ ๋” ์ž˜ ๋  ๊ฒƒ ๊ฐ™๋‹ค.

#include <iostream>
#include <stack>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	stack<pair<int, int>> s;

	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;

		while (!s.empty()) {  // ๋น„๊ตํ•  ํƒ‘์ด ์žˆ๋‹ค๋ฉด
			if (tmp < s.top().second) { // ํ˜„์žฌ top๋ณด๋‹ค ์ž‘๋‹ค๋ฉด
				cout << s.top().first+1 << " "; 
				s.push({ i,tmp }); // ํ˜น์‹œ ์ด๋ฒˆ ํƒ‘๋ณด๋‹ค ์ž‘์€ ํƒ‘ ์žˆ์„์ˆ˜๋„ ์žˆ๊ธฐ ๋•Œ๋ฌธ์—
				break;
			}
			else {
				// top ๋ณด๋‹ค ํ˜„์žฌ ํƒ‘์ด ํฌ๋‹ค๋ฉด
				s.pop(); // ๋‹ค์Œ ํƒ‘ ๋น„๊ต
			}
		}

		if (s.empty()) { // ์ˆ˜์‹ ๋ฐ›์„ ํƒ‘์ด ์—†์œผ๋ฉด
			cout << "0 ";
			s.push({ i,tmp }); // ํ˜„์žฌ ํƒ‘ ๋„ฃ๊ธฐ
		}

	}
}

 

๋ฐ˜์‘ํ˜•