백준7 [java] 백준 4949 균형잡힌 세상 이번 문제는 stack를 활용하여 괄호 짝을 찾는 문제이다. 하지만 이번 문제와는 다르게 소괄호 () 와 대괄호 []가 모두 들어가 있다. 따라서 if문 처리가 조금 복잡하다. 특히 ')'가 나온 뒤 '('가 나오는 등 순서도 신경써야하는 것이 헷갈렸다. 하지만 boolean변수를 하나 추가하여 해결했다. 코드를 통해 설명하겠다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.security.Identity; import java.util.Stack; public class Main { public static void main(String[] args) throws Exception{ BufferedReader .. 2024. 2. 13. 백준 11478 서로 다른 부분 문자열의 개수 간단한듯 어려운 문제였다. 하지만 한 메소드를 안다면 간단하게 해결할 수 있다. 우선 부분 문자열을 구하는 방법을 알아보자. 만약 abcde가 입력된다면 a b c d e ab bc cd de abc bcd cde abcd bcde abcde 이런식으로 나온다. 저 순서대로 출력하는 것은 반복문으로 처리하기에는 복잡하다. 반복문을 통해 해결하기에는 출력을 시작하는 자리가 지속적으로 변해 출력하기가 매우 까다롭다. 그렇다면 다른 규칙을 가지고 출력해보는 것을 생각해본다. 출력을 시작하는 자리를 고정해 본다. a ab abc abcd abcde b bc bcd bcde c cd cde d de e 위와 같은 방식을 사용해도 모든 경우의 수가 나오는 것을 알 수 있다. 이제 조금 감이 잡히기 시작할 것이다. .. 2024. 1. 24. 백준 1764 듣보잡 자바 java 문제를 읽어본 처음 N. M을 입력받는데 반해 N번째 까지 듣도 못한사람, N + 2번째까지 보도 못한사람을 입력받으라고해 혼란이 있었다. 하지만 이 의미는 결국 첫 번째 줄은 N, M을 입력받으므로 N번만큼 듣도 못한사람을, 이후 M번 보도 못한사람을 입력받으라는 의미였다. 왜 이렇게 쓴건지는 잘 모르겠다. 듣도 못한사람, 보도못한사람 2가지 조건을 충족해야하기에, 입력받을 때 마다 value를 + 1 하는 방법을 선택했다. 즉 듣도 보도 못한사람은 value값이 2일 것이다. 듣도 보도 못한사람이 몇 명인지도 출력해야 하므로 보도 못한사람을 입력받을 때 count에 몇명인지 저장한다. TreeMap를 사용하여 사전순으로 정렬한다. for-each문과 keySet를 적절히 사용하여 듣도 보도 못한 사람.. 2024. 1. 24. 백준 10815 숫자 카드 자바 java 이번 문제는 또한 시간내에 해결하는 것이 중요하다. 입력 값의 범위를 고여하면 약 10,000,000 * 500,000이 되므로 일일히 값을 비교하는 방법은 사용할 수 없다. 그렇다면 다른 방법을 생각해보아야한다. 이 부분은 다른 사람의 포스트를 참고하여 만들었다. HashMap를 사용하여 만들어 보자. HashMap는 키를 통해 조회할 때 가지고 있다면 value를 가지고 있지 않다면 null을 반환한다. import java.util.StringTokenizer; import java.util.HashMap; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; public class Main .. 2024. 1. 22. 백준 2751 수 정렬2 자바 java 문제를 풀어보니 앞선 수 정렬 1에서 사용한 방식을 사용하면 시간초과가 뜬다. N의 범위가 1,000,000까지로 늘어났기 때문으로 생각된다. 조금이라도 시간을 아끼끼 위해 Scanner보다 BufferReader과 BuffferWriter을 사용하기로 한다. 기존에 사용한 정렬방식은 버블정렬이었는데, 이 방식은 선택정렬, 삽입정렬과 함께 큰 수를 정렬할 때는 비효율 적인 방식이다. (시간복잡도 O(n^2)) 따라서 Arrays.sort(); 를 사용해보기로 했다. 이 방식은 시간복잡도( O(n log n) 이다. 따라서 큰 수에 효율적인 Arrays.sort()를 사용하기로 한다. import java.io.BufferedReader; import java.io.BufferedWriter; import.. 2024. 1. 18. 백준 24313 자바 java 아이디어 : 식을 최대한 단순화 시켜보자 모두 된다고 가정하고, 안되는 부분만 제외하자 1. 우선 식을 알아보자 f(n) = a1n + a0 이다. O(g(n)) = {f(n) 에서 O(n) 으로 간소화 되었다. 따라서 g(n) = n이다. 2. 제약사항을 알아보자. (1). n ≥ n0 (2). f(n) ≤ c × g(n) 3. 식을 단순화 해보자. f(n) ≤ c × n 이다. 위에서 정의된 식을 대입하면, a1n + a0 ≤ c × n이 된다. n끼리 묶으면 n(a1-c) = a0가 된다. 이 식이 항상 참이되기 위해서는 c-a1이 항상 양수여야 한다. 따라서 c-a1 = a0 자체도 성립해야한다. n(c-a1) < a0 인 상황을 제거한다. impo.. 2024. 1. 15. 이전 1 2 다음