백준 22866 JAVA

문제 유형

• 자료 구조(스택)

문제 접근

• 답
  • 현재 빌딩에서 보이는 빌딩 개수와 가장 가까운 빌딩 위치
• 주어지는 정보
  • 건물 개수 : 최대 100,000 (N)
  • 건물 높이 : 최대 100,000 (L)
• 정보 정리
  • 최대 연산은 N^2 미만이어야한다
    • N^2 = 10,000,000,000
    • ⇒ 완전 탐색 X(시뮬레이션, BFS, DFS 등은 사용못할 가능성이 큼)
  • 남는 예상 후보
    • DP
      • 가능할 거라 여겼으나, 실패
      • 내가 실패한 이유
        • 코드로 짜기 복잡함
          • DP[current]의 값을 구하기 위해, DP[current-1]의 값 등을 이용해야 함
          • 하지만 DP[current-1]이 가지는 자신과 제일 가까운 빌딩 위치 a가 존재할 때,
          • DP[currnet] → DP[current-1] → a 순의 단계를 거쳐서 DP[current]와 가장 가까운 빌딩을 유추해야함(복잡함)
          • 예시

if(height[current] == height[i])
{
		//i번째 빌딩과 가장 가까운 빌딩이 왼쪽, 오른쪽에 있는지 구분하려면 더 많은 if문을 써야함
		dp[current].nearBuilding = dp[i].nearBuilding + (current-i);
}

• ⇒ 스택을 써서 DP의 구현 난이도를 극복함
• 이분 탐색 , 그리디
  • 적합X
  • 빌딩의 높이는 무작위이므로, 둘 다 불가능

 

 

• 풀이
  • Stack
    • L→R 방향으로 for문 돌림
      • 방향대로 빌딩 높이를 스택에 추가
      • 현재 빌딩보다 스택의 빌딩 높이가 낮으면 스택 값 제거
      • 스택에 있는 빌딩 개수 = 현재 빌딩의 왼쪽에서 볼 수 있는 빌딩 개수
    • R→L 방향으로 해당 방법을 다시 돌림

import java.util.*;
import java.io.*;

class Building
{
    public int L = 0;
    public int R = 0;
    public int targetIdx=0;
    public int dis=100001;
}

class BuildingState
{
    public int h,idx;

    public BuildingState(int h, int idx)
    {
        this.h = h;
        this.idx = idx;
    }
}

public class Main {
    static int N;
    static int[] map;
    static Building[] arr;
    public static void Resolve()
    {
        Stack<BuildingState> stack = new Stack<>();
        stack.push(new BuildingState(map[0], 0));
        for(int i = 1; i<N; i++)
        {
            while(!stack.isEmpty() && stack.peek().h <= map[i])
            {
                stack.pop();
            }

            if(stack.size() != 0)
            {
                arr[i].L = stack.size();
                int targetIdx = stack.peek().idx;
                arr[i].targetIdx = targetIdx;
                arr[i].dis = i - targetIdx;
            }

            stack.push(new BuildingState(map[i],i));
        }
        stack.clear();

        stack.add(new BuildingState(map[N-1],N-1));
        for(int i = N-1; i>=0; i--)
        {
            while(!stack.isEmpty() && stack.peek().h <= map[i])
            {
                stack.pop();
            }

            if(stack.size() != 0)
            {
                arr[i].R = stack.size();

                int targetIdx = stack.peek().idx;
                if(targetIdx-i < arr[i].dis)
                {
                    arr[i].targetIdx = targetIdx;
                    arr[i].dis = targetIdx-i;
                }
            }

            stack.push(new BuildingState(map[i],i));
        }
    }


    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        map = new int[N];
        arr = new Building[N];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N; i++)
        {
            map[i] = Integer.parseInt(st.nextToken());
            arr[i] = new Building();
        }
        
        Resolve();
        
        for(int i = 0; i<N; i++)
        {
            int result = arr[i].L + arr[i].R;
            if(result == 0)
            {
                System.out.println(0);
            }
            else
            {
                int idx = arr[i].targetIdx + 1;
                System.out.println(result + " " + idx);
            }
        }
        
    }
}

 

 

틀린 풀이(DP로 접근)

import java.util.*;
import java.io.*;

class LR
{
    public int L,R;
    public LR(int L, int R)
    {
        this.L = L;
        this.R = R;
    }

    public int dis=100001;
    public int idx=100001;
}

public class Main {
    static int N;
    static int[] map;
    static LR[] dp;
    
    public static void Resolve()
    {
        //Left
        for(int i = 1; i<N; i++)
        {
            if(map[i] < map[i-1])
            {
                dp[i].L = dp[i-1].L+1;
                dp[i].idx = i-1;
                dp[i].dis = 1;
            }
            else if(map[i] == map[i-1] && dp[i-1].idx != 100001)
            {
                dp[i].L = dp[i-1].L;
                dp[i].idx = dp[i-1].idx;
                dp[i].dis = dp[i-1].dis + 1;
            }
            else if(map[i] > map[i-1])
            {
                for(int j = i-1; j>=0; j--)
                {
                    if(map[i] < map[j])
                    {
                        dp[i].L = dp[j].L+1;
                        dp[i].idx = j;
                        dp[i].dis = i-j;
                        break;
                    }
                    else if(map[i] == map[j] && dp[j].idx != 100001)
                    {
                        dp[i].L = dp[j].L;
                        dp[i].idx = dp[j].idx;
                        dp[i].dis = dp[j].dis+(i-j);
                        break;
                    }
                }
            }
        }
        
        //Right
        for(int i = N-2; i>=0; i--)
        {
            if(map[i] < map[i+1])
            {
                dp[i].R = dp[i+1].R + 1;
                if(dp[i].dis > 1)
                {
                    dp[i].idx = i+1;
                }
            }
            else if(map[i] == map[i+1])
            {
                dp[i].R = dp[i+1].R;
                if(dp[i+1].idx != 100001 && dp[i].dis > dp[i+1].dis+1)
                {
                    dp[i].idx = dp[i+1].idx;
                }
            }
            else if(map[i] > map[i+1])
            {
                for(int j = i+1; j<N; j++)
                {
                    if(map[i] < map[j])
                    {
                        dp[i].R = dp[j].R + 1;

                        if(dp[i].dis > j-i)
                        {
                            dp[i].idx = j;
                        }
                        break;
                    }
                    else if(map[i] == map[j])
                    {
                        dp[i].R = dp[j].R;

                        if(dp[i].dis > dp[j].dis + (j-i) && dp[j].idx != 100001)
                        {
                            dp[i].idx = dp[j].idx;
                        }
                        break;
                    }
                }
            }
        }
    }

    public static void PrintDp()
    {
        for(int i = 0; i<N; i++)
        {
            System.out.println(dp[i].L + " " + dp[i].R);
        }
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        map = new int[N];
        dp = new LR[N];
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N; i++)
        {
            map[i] = Integer.parseInt(st.nextToken());
            dp[i] = new LR(0,0);
        }
        
        Resolve();
        
        for(int i = 0; i<N; i++)
        {
            int result = dp[i].L + dp[i].R;
            if(result== 0)
            {
                System.out.println(0);
            }
            else
            {
                int idx = dp[i].idx + 1;
                System.out.println(result + " " + idx);
            }
        }

        //PrintDp();
        
    }
}