Junior-Developer
Home
  • Category (316)
    • 문제풀이 (270)
      • 백준oj (201)
      • 프로그래머스 (53)
      • 명품 자바 프로그래밍(개정4판) (11)
      • 구름 (5)
    • 알고리즘 (6)
    • Node.js (2)
    • 체크리스트 (37)
블로그 내 검색
Home

Junior-Developer

1일 1커밋! 1일 1 백준!

  • 문제풀이/백준oj

    [백준OJ] 1365번 꼬인 전깃줄

    2021. 11. 7.

    by. Hyeon-Uk

    반응형

    https://www.acmicpc.net/problem/1365

     

    1365번: 꼬인 전깃줄

    첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가

    www.acmicpc.net


     

     

    풀이

    말을 살짝 바꿔서 잘라야되는 전깃줄을 구하는것이아닌, 자르지 않아도되는 전깃줄의 최대값을 구해준다고 생각을 하면 쉽게된다. 

    그럼 여기서 자르지않아도 되는 전깃줄의 최대값은 어떻게 구해줄까? 방법은 바로 증가하는 수열의 최대길이를 구해주면된다.

    이를 위해 Lower_bound함수를 구현해준 뒤, 자르지않아도 되는 전깃줄의 최대값을 구해주어 N에서 빼주면 답이 나온다.

    시간복잡도

    Lower_bound의 시간은 O(logN)이 되는데, 이를 N번 반복하기때문에 O(NlogN)이 된다.

     

    코드

    import java.util.ArrayList;
    import java.util.Scanner;
    
    public class Main {
        static ArrayList<Integer> v=new ArrayList<>();
        static int n;
    
        static int lower_bound(int num){
            int l=0;
            int r=v.size();
    
            while(l<r){
                int middle=(l+r)>>1;
    
                if(v.get(middle)>=num){
                    r=middle;
                }
                else{
                    l=middle+1;
                }
            }
    
            return l;
        }
    
        public static void main(String[] args){
            Scanner scanner=new Scanner(System.in);
            n=scanner.nextInt();
            for(int i=0;i<n;i++){
                int line=scanner.nextInt();
                int ind=lower_bound(line);
                if(ind>=v.size()){
                    v.add(line);
                }
                else{
                    v.set(ind,line);
                }
            }
            System.out.println(n-v.size());
            scanner.close();
        }
    }

     

    반응형
    저작자표시 (새창열림)

    '문제풀이 > 백준oj' 카테고리의 다른 글

    [백준OJ] 2631번 줄세우기  (0) 2021.12.24
    [백준OJ] 7347번 플립과 시프트  (0) 2021.12.24
    [백준OJ] 1309번 동물원  (0) 2021.11.07
    [백준OJ] 7568번 덩치  (0) 2021.11.05
    [백준OJ] 1181번 단어 정렬  (0) 2021.11.04

    댓글

    관련글

    • [백준OJ] 2631번 줄세우기 2021.12.24
    • [백준OJ] 7347번 플립과 시프트 2021.12.24
    • [백준OJ] 1309번 동물원 2021.11.07
    • [백준OJ] 7568번 덩치 2021.11.05
    맨 위로
전체 글 보기
Tistory 로그인
Tistory 로그아웃
로그아웃 글쓰기 관리

Today

Total

Powered by ⓒ Kakao Corp.

Designed by Nana
블로그 이미지
Hyeon-Uk

티스토리툴바