๐ŸŒžAlgorithm/๐Ÿ”ฅBaekjoon

[Baekjoon] 2493_ํƒ‘

๋ฟŒ์•ผ._. 2022. 3. 28. 15:33

Gold V

๋ฌธ์ œ(์ถœ์ฒ˜: https://www.acmicpc.net/problem/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์„ ์ถœ๋ ฅํ•œ๋‹ค.

 

 

๋ฌธ์ œ ํ’€์ด

   - my solution (Python)

import sys

if __name__=='__main__':
    n=int(input()) # ํƒ‘์˜ ์ˆ˜

    arr=list(map(int, sys.stdin.readline().split())) # ํƒ‘์˜ ๋†’์ด

    stack=[]
    answer=[]

    for i in range(len(arr)):
        while True:
            if len(stack)==0: # ๋ ˆ์ด์ € ์‹ ํ˜ธ ์ˆ˜์‹ ํ•˜๋Š” ํƒ‘ ์กด์žฌ x
                answer.append(str(0))
                stack.append([str(i+1), arr[i]])
                break
            elif stack[-1][1]<arr[i]: # ์™ผ์ชฝ ํƒ‘์˜ ๋†’์ด๊ฐ€ ๋” ๋‚ฎ์œผ๋ฉด
                stack.pop()
            else: # ์™ผ์ชฝ ํƒ‘์˜ ๋†’์ด๊ฐ€ ๋†’๊ฑฐ๋‚˜ ๊ฐ™์œผ๋ฉด
                answer.append(stack[-1][0])
                stack.append([str(i+1), arr[i]])
                break

    print(' '.join(answer))

 

- my solution (JAVA)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class _2493_ํƒ‘ {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n=Integer.parseInt(br.readLine()); // ํƒ‘์˜ ์ˆ˜
	
		String arr[]=br.readLine().split(" "); // ํƒ‘์˜ ๋†’์ด
	
		
		Stack<int[]> stack=new Stack<>();
		int[] answer=new int[n];
		
		for(int i=0; i<n; i++) {
			while(true) {
				if(stack.size()==0) { // ๋ ˆ์ด์ € ์‹ ํ˜ธ ์ˆ˜์‹ ํ•˜๋Š” ํƒ‘ ์กด์žฌ x
					answer[i]=0;
					stack.push(new int[] {i+1, Integer.parseInt(arr[i])});
					break;
				}else if(stack.peek()[1]< Integer.parseInt(arr[i])) { // ์™ผ์ชฝ ํƒ‘์˜ ๋†’์ด๊ฐ€ ๋” ๋‚ฎ์œผ๋ฉด
					stack.pop();
				}else { // ์™ผ์ชฝ ํƒ‘์˜ ๋†’์ด๊ฐ€ ๋†’๊ฑฐ๋‚˜ ๊ฐ™์œผ๋ฉด
					answer[i]=stack.peek()[0];
					stack.push(new int[] {i+1, Integer.parseInt(arr[i])});
					break;
				}
			}			
		}
		for(int i=0; i<n; i++) { // ์ถœ๋ ฅ
			bw.write(answer[i]+" ");
		}
		bw.flush();
		bw.close();
	}
}

 

๋ฌธ์ œ์— ์žˆ๋Š” ์˜ˆ๋ฅผ ๊ทธ๋ฆผ์œผ๋กœ ๋‚˜ํƒ€๋‚ด๋ฉด ์•„๋ž˜์™€ ๊ฐ™๋‹ค.

๋ ˆ์ด์ €๊ฐ€ ์™ผ์ชฝ ๋ฐฉํ–ฅ์œผ๋กœ ๋ฐœ์‚ฌํ•˜๋ฏ€๋กœ ์™ผ์ชฝ์˜ ํƒ‘ ๊ธธ์ด์™€ ๋น„๊ตํ•˜๋ฉด ๋  ๊ฒƒ ๊ฐ™์•„ stack์„ ํ™œ์šฉํ•˜์˜€๋‹ค.

๋˜ํ•œ, ์ˆ˜์‹ ํ•œ ํƒ‘์„ ์•Œ๊ธฐ ์œ„ํ•ด ์กฐ๊ฑด์„ 3๊ฐ€์ง€๋กœ ์„ค์ •ํ•˜์˜€๋‹ค. stack์ด ๋น„์—ˆ์„ ๋•Œ, ์™ผ์ชฝ ํƒ‘์˜ ๊ธธ์ด๊ฐ€ ๋” ์งง์„ ๋•Œ, ๊ธธ๊ฑฐ๋‚˜ ๊ฐ™์„ ๋•Œ๋กœ ๋‚˜๋ˆ„์–ด ๊ตฌํ˜„ํ•˜์˜€๋‹ค. stack์ด ๋น„์—ˆ์œผ๋ฉด ์ˆ˜์‹ ํ•˜๋Š” ํƒ‘์ด ์กด์žฌํ•˜์ง€ ์•Š์œผ๋ฏ€๋กœ answer์— 0์„ ๋„ฃ๊ณ  ๋‹ค์Œ ํƒ‘์„ ์œ„ํ•ด stack์— ๋„ฃ์–ด์ค€๋‹ค. ์™ผ์ชฝ ํƒ‘์˜ ๊ธธ์ด๊ฐ€ ์งง์„ ๋•Œ๋Š” ๊ทธ ํƒ‘์€ ๋ ˆ์ด์ €๋ฅผ ์ˆ˜์‹ ํ•  ์ˆ˜ ์—†์œผ๋ฏ€๋กœ pop์„ ํ•ด์ค€๋‹ค. ํ•˜์ง€๋งŒ stack์— ๋‚จ์•„์žˆ๋Š” ํƒ‘ ์ค‘์—์„œ ์ˆ˜์‹ ํ•  ์ˆ˜ ์žˆ๋Š” ํƒ‘์ด ์žˆ์„ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ while์„ ํ†ตํ•ด ๋๊นŒ์ง€ ํ™•์ธํ•ด์ค€๋‹ค. ๋งˆ์ง€๋ง‰์œผ๋กœ ์™ผ์ชฝ ํƒ‘์˜ ๊ธธ์ด๊ฐ€ ๊ธธ๊ฑฐ๋‚˜ ๊ฐ™๋‹ค๋ฉด ๋ ˆ์ด์ €๋ฅผ ์ˆ˜์‹ ํ•  ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ answer์— ๊ทธ ํƒ‘์˜ ๋ฒˆํ˜ธ๋ฅผ ๋„ฃ๊ณ  ๋‹ค์Œ ํƒ‘์„ ์œ„ํ•ด stack์— ๋„ฃ์–ด์ค€๋‹ค.

 

์œ„์˜ ์„ค๋ช…์„ ๊ฐ„๋‹จํžˆ ๋‚˜ํƒ€๋‚ด๋ฉด ์•„๋ž˜์™€ ๊ฐ™๋‹ค.

 

  • ํƒ‘์˜ ์ˆ˜, ํƒ‘์˜ ๋†’์ด ์ž…๋ ฅ
  • ํƒ‘์˜ ๋†’์ด ๋ฐ˜๋ณต๋ฌธ ์ˆ˜ํ–‰ (for๋ฌธ)
    : while 
    1) len(stack) == 0 
    - ๋ ˆ์ด์ € ์‹ ํ˜ธ ์ˆ˜์‹ ํ•˜๋Š” ํƒ‘์ด ์กด์žฌํ•˜์ง€ ์•Š๋Š”๋‹ค๋Š” ์˜๋ฏธ
    - ์‹ ํ˜ธ๋ฅผ ์ˆ˜์‹ ํ•˜๋Š” ํƒ‘์ด ์กด์žฌํ•˜์ง€ ์•Š์œผ๋ฏ€๋กœ answer์— 0 ์ถ”๊ฐ€
    - ๋‹ค์Œ ํƒ‘์„ ์œ„ํ•ด stack์— [index, height] ์ถ”๊ฐ€
    - break
    2) stack [-1][1] < arr [i]
    - ์™ผ์ชฝ ํƒ‘์˜ ๋†’์ด๊ฐ€ ๋” ๋‚ฎ์œผ๋ฉด
    - ์‹ ํ˜ธ๋ฅผ ์ˆ˜์‹ ํ•˜์ง€ ๋ชปํ•˜๋ฏ€๋กœ stack์—์„œ pop
    3) stack [-1][1] >= arr [i]
    - ์™ผ์ชฝ ํƒ‘์˜ ๋†’์ด๊ฐ€ ๋” ๋†’๊ฑฐ๋‚˜ ๊ฐ™์•„ ์‹ ํ˜ธ ์ˆ˜์‹  ๊ฐ€๋Šฅํ•˜๋ฉด
    - answer์— stack [-1]์˜ index ์ถ”๊ฐ€
    - ๋‹ค์Œ ํƒ‘์„ ์œ„ํ•ด stack์— [index, height] ์ถ”๊ฐ€
    - break
  • ๊ฒฐ๊ณผ answer ์ถœ๋ ฅ

 

 

โ“ JAVA์—์„œ ์™œ ๋ฉ”๋ชจ๋ฆฌ ์ดˆ๊ณผ๊ฐ€ ๋ฐœ์ƒํ–ˆ๋Š”๊ฐ€?

Scanner๋ฅผ ์‚ฌ์šฉํ•ด์„œ ๋ฐœ์ƒํ–ˆ๋‹ค. ์˜ˆ์ „์— Scanner ์“ฐ๋˜ ์Šต๊ด€์ด ๊ทธ๋Œ€๋กœ...

BufferedReader, BufferedWriter๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ์ฝ”๋“œ๋ฅผ ๊ณ ์ณค๋”๋‹ˆ ํ†ต๊ณผํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค.

 


์ƒ๊ฐ๐Ÿค”

 

๋ฌธ์ œ ๋ณด๊ณ  ์ƒ๊ฐ๋‚˜๋Š” ๋ฐ๋กœ ๋š๋”ฑ๋š๋”ฑํ–ˆ๋”๋‹ˆ ํ•œ ๋ฒˆ๋งŒ์— ์„ฑ๊ณต -!

JAVA BufferedReader, BufferedWriter ์‚ฌ์šฉํ•˜๋Š” ๋ฒ• ์ฐพ์•„๋ณธ๋‹ค๊ณ  ์กฐ๊ธˆ ์‹œ๊ฐ„์ด ๊ฑธ๋ ธ์ง€๋งŒ ๋งŒ์กฑํ•œ๋‹ค.

 


 

 

 

'๐ŸŒžAlgorithm > ๐Ÿ”ฅBaekjoon' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[Baekjoon] 2178_๋ฏธ๋กœ ํƒ์ƒ‰  (0) 2022.03.31
[Baekjoon] 6198_์˜ฅ์ƒ ์ •์› ๊พธ๋ฏธ๊ธฐ  (0) 2022.03.29
[Baekjoon] 1068_ํŠธ๋ฆฌ  (0) 2022.03.25
[Baekjoon] 3190_๋ฑ€  (0) 2022.03.23
[Baekjoon] 7569_ํ† ๋งˆํ†   (0) 2022.03.22