이 영역을 누르면 첫 페이지로 이동
시간의화살 블로그의 첫 페이지로 이동

시간의화살

페이지 맨 위로 올라가기

시간의화살

행복하세요

[백준] 2529 부등호 - Java

  • 2022.08.19 01:27
  • Algorithm/Baekjoon

 

 

 

부등호 조건에 맞게 숫자를 넣어가며 백트래킹 돌리면 된다.

이 때 int 범위로는 값을 제대로 표현할 수 없으니 long 타입을 사용하자 (최대, 최소 설정에도 Long.MAX_VALUE)

 

 

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

public class Main {
    static int[] select;
    static char[] operators;
    static int N;
    static boolean[] visit;

    static long max = Long.MIN_VALUE;
    static long min = Long.MAX_VALUE;
    

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));     

        N = Integer.parseInt(br.readLine());
        select = new int[N + 1];
        operators = new char[N];
        visit = new boolean[10];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            operators[i] = st.nextToken().charAt(0);
        }

        bt(0);

        

        System.out.println(String.valueOf(max).length() == N+1 ? max : "0" + String.valueOf(max));
        System.out.println(String.valueOf(min).length() == N+1 ? min : "0" + String.valueOf(min));
        
        
    }

    static void bt(int depth){
        
        if(depth == N + 1){
            // calculate
            String tmp = "";

            for(int i =0; i< select.length; i++){
                tmp += String.valueOf(select[i]);
            }

            long num = Long.parseLong(tmp);

            max = Math.max(max, num);
            min = Math.min(min, num);
            return;
        }


        for(int i=0; i<10; i++){
            if(!visit[i]){
                if(depth == 0){
                    visit[i] = true;
                    select[depth] = i;
                    bt(depth + 1);   
                    visit[i] = false;
                    select[depth] = 0;
                }else{
                    if(operators[depth - 1] == '<'){
                        if(select[depth - 1] > i){
                            continue;
                        }
                        visit[i] = true;
                        select[depth] = i;
                        bt(depth + 1);
                        visit[i] = false;
                        select[depth] = 0;
                    }

                    if(operators[depth - 1] == '>'){
                        if(select[depth - 1] < i){
                            continue;
                        }
                        visit[i] = true;
                        select[depth] = i;
                        bt(depth + 1);
                        visit[i] = false;
                        select[depth] = 0;
                    }
                    
                }
            }
        }

    }

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

'Algorithm > Baekjoon' 카테고리의 다른 글

[백준] 1106 호텔 - Java  (0) 2022.08.25
[백준] 9489 사촌 - Java  (0) 2022.08.24
[백준] 1553 도미노 찾기 - Java  (0) 2022.08.18
[백준] 15658 연산자 끼워넣기 (2) - Java  (0) 2022.08.18
[백준] 17136 색종이 붙이기 - Java  (0) 2022.08.17

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • [백준] 1106 호텔 - Java

    [백준] 1106 호텔 - Java

    2022.08.25
  • [백준] 9489 사촌 - Java

    [백준] 9489 사촌 - Java

    2022.08.24
  • [백준] 1553 도미노 찾기 - Java

    [백준] 1553 도미노 찾기 - Java

    2022.08.18
  • [백준] 15658 연산자 끼워넣기 (2) - Java

    [백준] 15658 연산자 끼워넣기 (2) - Java

    2022.08.18
다른 글 더 둘러보기

정보

시간의화살 블로그의 첫 페이지로 이동

시간의화살

  • 시간의화살의 첫 페이지로 이동

검색

방문자

  • 전체 방문자
  • 오늘
  • 어제

카테고리

  • 분류 전체보기 (610)
    • Algorithm (205)
      • Data Structure (5)
      • Theory && Tip (33)
      • Baekjoon (166)
      • ALGOSPOT (1)
    • Spring (123)
      • Spring (28)
      • Spring Web MVC (20)
      • Spring Database (14)
      • Spring Boot (6)
      • Spring 3.1 (11)
      • Spring Batch (6)
      • Spring Security (16)
      • JPA (12)
      • Spring Data JPA (5)
      • QueryDSL (4)
      • eGovFramework (1)
    • Programming Language (74)
      • Java (19)
      • JavaScript (15)
      • C (25)
      • C++ (12)
      • Python (1)
      • PHP (2)
    • Computer Science (69)
      • Operating System (18)
      • Computer Network (17)
      • System Programming (22)
      • Universial Programming Lang.. (8)
      • Computer Architecture (4)
    • Database (21)
      • Database (7)
      • MySQL (3)
      • Oracle (3)
      • Redis (5)
      • Elasticsearch (3)
    • DevOps (20)
      • Docker && Kubernetes (8)
      • Jenkins (4)
      • Github Actions (0)
      • Amazon Web Service (8)
    • Machine Learning (28)
      • AI Introduction (28)
    • Mobile (28)
      • Android (21)
      • Flutter (7)
    • Solutions (14)
    • Life Logs (3)
    • 낙서장 (25)

최근 글

나의 외부 링크

메뉴

  • 홈

정보

13months의 시간의화살

시간의화살

13months

블로그 구독하기

  • 구독하기
  • RSS 피드

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
Powered by Tistory / Kakao. Copyright © 13months.

티스토리툴바