Coding Test/백준

문제설명입력 & 출력나의 풀이이번 문제는 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하는 문제입니다.for (int i = 0; i  만약 위와 같이 코드를 작성했다면 각 구간 합을 구하는 데 O(N)의 시간이 걸리기 때문에, 이를 O(1)로 줄이기 위해 누적 합 배열을 사용하는 것이 좋습니다.  먼저 빠른 입력을 위해서 Buffer로 입력을 받아주고, StringTokenizer를 사용하여 숫자를 공백을 기준으로 분리하여 저장합니다. 그리고 각 수를 저장할 배열 arr을 만들고, 누적 합을 구하기 위하여 prefixSum배열을 N보다 1 크게 초기화를 합니다. 각 수를 반복문을 통해서 N개만큼 저장하고, 누적 합 배열에도 각 구간별 누적 합을 저장해 줍니다. 그리고..

문제설명입력 & 출력나의 풀이 이번 문제는 문자열에서 괄호의 균형을 확인하는 것입니다. 주어진 문자열에 대하여 소괄호 ()와 대괄호 []가 올바르게 짝을 이루는지를 판단하고, 올바르면 "yes", 그렇지 않으면 "no"를 출력해야 합니다. 보통 짝을 이루는지 확인하는 문제는 스택을 활용하면 간단히 풀 수 있습니다. 왜냐하면 스택의 특성상 LIFO구조이기 때문에 괄호의 열림과 닫힘을 간편하게 관리할 수 있기 때문입니다. 마지막으로 열린 괄호와 첫 번째로 닫힌 괄호의 대응가장 마지막에 열린 괄호가 가장 먼저 닫혀야 합니다. 스택은 이러한 구조를 자연스럽게 지원합니다. 즉, 가장 마지막에 추가된 요소가 가장 먼저 제거되는 스택의 특성이 괄호 문제에 적합합니다.중첩 구조의 처리괄호는 중첩될 수 있으며, 스택은 ..

문제설명입력 & 출력나의 풀이 이번 문제는 2xn 타일링 문제에 이어지는 문제입니다. 위 그림과 같은 타일이 존재할 때 입력으로 n을 받아 2xn의 크기의 직사각형을 채우는 문제입니다. 타일을 채우다 보면 n = 5일 때 0~5까지의 타일링의 수는 다음과 같습니다. n= 0 ➡️ 1 (채우는 방법이 없으므로 1부터 시작)n= 1 ➡️ 1n= 2 ➡️ 3n= 3 ➡️ 5n= 4 ➡️ 11n= 5 ➡️ 21위 타일링의 수를 생각해서 DP의 가장 핵심요소인 점화식을 도출해야 합니다. 좀 더 이해를 하기 쉽게 그림으로 표현하면 다음과 같습니다.  만약에 n = 3일 때를 보면 n-1의 타일에서 2x1의 타일이 추가된 것을 볼 수있습니다. n-2의 타일에서 2x2를 채우는 경우는 1x2 ➡️ 2개 2x2 ➡️ 1..

문제설명입력 & 출력나의 풀이 이번 문제는 듣도 못한 사람 N과 보도 못한 사람 M이 주어질 때 듣도 못한 사람 + 보도 못한 사람 = "듣도보도 못한 사람"을 구하는 문제입니다. 먼저 빠른 입력을 위해서 Buffer로 입력을 받아주고, StringTokenizer를 사용하여 N과M을 공백을 기준으로 분리하여 각각 저장해줍니다. 저는 N과 M의 입력을 한 번에 받아서 듣지도 보지도 못한 사람은 vlaue가 2가 형성되도록 구성했습니다. HashMap을 선언해 주고, N과 M을 입력을 받고, getOrDefault() 메서드를 사용하여 해당하는 이름을 1씩 증가했습니다.  이러면 듣도 보도 못한 사람은 위 실행결과와 같이 value가 2가 형성됩니다. 그리고 keySet() 메서드와 get() 메서드를 사..