Sunrise

이진탐색 문제입니다. - 숫자 업다운 게임이랑 비슷 초기 low = 0, high = nCard.length-1 while(low high = mid - 1 num이 중간위치값 위 -> low = mid + 1 num이 중간위치값과 같음 -> 찾음 찾지 못하고 while문을 나오게 되면 -1 반환 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int N, M; static int[] nCard, mCard; public static v..

String 관련 메서드 String str = "abcde"; Integer.parseInt("300") // 문자열을 숫자로 변환 Integer.toString(300) // 숫자를 문자열로 변환 if(str.length() > 4) // str의 길이 5 반환 if(str.equals("abcde")) // str과 abcde를 비교해서 같으면 true, 다르면 false, ==은 주소값 비교 (String - reference type) if(str.compareTo("abcdd") > 0) // str이 abcdd보다 사전순으로 뒤면 true /* str과 abcdd가 같으면 0 str이 abcdd보다 사전순으로 앞이면 -1 str이 abcdd보다 사전순으로 뒤면 1 str과 abcdd가 마지막..

보호되어 있는 글입니다.

큐 문제 입니다. 테스트 케이스 10개가 주어지고 각 케이스마다 큐를 초기화하며 큐 메서드를 잘 사용해야 합니다. 조건 별로 큐 메서드를 사용하는데 익숙하지 않아 큐가 예상과 다르게 바뀌어버려서 디버깅할 때 큐의 상태가 어떤지 주로 확인했습니다. queue.peek() : 큐의 가장 앞의 원소를 가져옴 queue.poll() : 큐의 가장 앞의 원소를 가져오고 제거 queue.add() : 큐의 가장 뒤에 원소 추가 queue.remove() : 큐의 가장 앞의 원소 제거 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.u..

누적 합 문제입니다. 11659번은 1차원 누적 합 배열이지만 11660은 2차원 누적 합 배열입니다. 2차원 배열의 각 원소, 1차원 배열에 대해 누적 합을 만들고, 주어지는 x1, y1, x2, y2로 인덱스를 구분짓고 차이를 구합니다. sum에다가 각 행에 대해 구한 누적합을 더해서 답을 구합니다. 주어지는 배열 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 누적 합 배열 1 3 6 10 2 |5 9 14| 12 3 |7 12 18| 15 4 9 15 22 좌표 2, 2! 3, 4! 3,4 3,4 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.Inp..

누적 합 문제입니다. 구간 별로 모두 더하려 하면 시간초과입니다. 이럴 때는 값을 차례대로 더해놓은 배열을 먼저 구해놓고, 구간이 주어지면 그 구간에 해당하는 인덱스들의 차이만 구하면 됩니다. (그 인덱스까지의 합이 들어있기 때문에 가능) import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws Numbe..

시뮬레이션 문제입니다. 풀이) 필요 변수 초기화, 맵, 명령어 입력받기 1. 탱크 위치 찾기 2. 명령어 실행 3. 명령어 별로 grid 상태 변경 4. 출력 import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; public class Solution { static char[][] grid = new char[20][20]; // 게임 맵 static int r=0, c=0, dir=0; // 탱크 현재 위치 static char[] tankDir = {''}; // dir 0 1 2 3 순 static int h, w; public static void main(String[] args) throws F..

2차원 배열 탐색 문제입니다. 풀이) 1. N*N 2차원 배열 준비 2. 현 위치 초기화 3-1) 방향 전환 조건에 해당 안되면 → 현 위치 값 세팅 3-2) 방향 전환 조건에 해당하면 → 이전 한번 돌아가고 방향 변경 4. 출력 import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; public class Solution { public static void main(String[] args) throws FileNotFoundException { // TODO Auto-generated method stub String path = System.getProperty("user.dir") + "\\src\\..

이분탐색 문제입니다. N과 M의 범위가 10만, 10만이므로 탐색을 위해 이중 for문을 돌리면 시간초과가 납니다. 따라서 시간복잡도가 logN인 이분 탐색을 합니다. 이분탐색은 숫자게임 Up&Down 과 비슷한 원리로, 정렬된 배열에서 시작점과 끝점을 잡고 들어온 값을 배열의 중간값과 비교합니다. 값이 중간값보다 작은 경우, 끝점은 mid-1 값이 중간값보다 큰 경우, 시작점은 mid+1 이렇게 해서 시작점이 끝점과 같거나 커질 때까지 while문을 돌리면 이분탐색을 할 수 있습니다. import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc ..

누적 합 문제입니다. N 개의 숫자들을 받고, K 개만큼의 합들의 수열을 구해서 그 중 가장 큰 숫자를 구해야합니다. 이를 그냥 구현하게 되면, N개 반복, K개 반복하여 이중반복문으로 최악의 경우 5만*5만으로 시간초과가 납니다. 누적 합 문제들의 경우, 한 반복문 안에서 값을 갱신해나가는 prefix_sum 알고리즘을 이용하면 시간복잡도를 줄일 수 있습니다. O(N*K) → O(N) 이중 반복문으로 구현하여 시간초과 나는 코드 N, K = map(int, input().split()) num = list(map(int, input().split())) arr = [] for i in range(N-K+1): temp_sum = 0 for j in range(i, i+K): temp_sum += num..