백준 (30) 썸네일형 리스트형 2230번: 수 고르기(Java) 투 포인터를 사용해 해결할 수 있다. 우선, 필요한 변수들을 선언한다. int N, M; Scanner scanner = new Scanner(System.in); N = scanner.nextInt(); M = scanner.nextInt(); int[] arr = new int[N]; int p1 = 0; int p2 = 0; int result = 2000000000; |A[i]|의 범위가 0~1000000000 이므로, 두 수의 차이는 최대 2000000000까지 될 수 있다. 따라서 result를 우선 2000000000로 설정했다. arr에 데이터를 넣어 주고, 투 포인터를 사용해야 하기 때문에 arr를 정렬해준다. Arrays.setAll(arr, i -> scanner.nextInt());.. 2559번: 수열(Java) 구간 합을 이용하는 문제이다. 구간 합을 공부한 지 얼마 되지 않아 처음에 고민을 많이 했다. 우선, 필요한 변수를 선언하고, 수를 입력받으며 구간합을 구한다. Scanner scanner = new Scanner(System.in); int size = scanner.nextInt(); int day = scanner.nextInt(); int[] arr = new int[size]; arr[0] = scanner.nextInt(); for(int i = 1; i 11659번: 구간 합 구하기 4(Java) 구간 합을 이용해 간단하게 풀 수 있는 문제이다. 배열을 사용해 수를 입력받으면서 구간 합을 저장하면 된다. 우선, 필요한 변수들을 선언한다. Scanner scanner = new Scanner(System.in); int size = scanner.nextInt(); int n = scanner.nextInt(); int[] partialSum = new int[size]; StringBuilder result = new StringBuilder(); 이제 구간 합을 저장하면서 수를 입력받으면 된다. partialSum[0] = scanner.nextInt(); for(int i = 1; i 16139번: 인간-컴퓨터 상호작용(Java) 누적 합을 이용해서 풀 수 있는 문제이다. 문자열을 입력받은 후, 문자열의 길이만큼 이차원 배열을 선언한다. 이차원 배열의 크기는 [문자열의 길이][26] 이다(알파벳은 26개). 문자열의 각 인덱스 별로 알파벳이 몇 번 나왔는지 저장하면 된다. 0 번째 인덱스부터 length - 1 번째 인덱스까지 반복하며 해당 알파벳을++ 해 주면 된다. 말로 하면 복잡하기도 하고 필자가 설명을 잘 못 하기도 하니 코드로 확인해 보자. Scanner scanner = new Scanner(System.in); StringBuilder sb = new StringBuilder(); String str = scanner.next();//입력받을 문자열 int n = scanner.nextInt();//테스트 갯수 cha.. 11279번: 최대 힙(Java) 가장 큰 값을 출력해야 하므로 우선순위 큐(Priority Queue)를 사용하면 된다. 우선순위 큐는 큐의 일종으로, add()를 할 때 우선순위를 정할 수 있다. 예를 들어 1,4,6,2를 차례대로 오름차순 우선순위 큐에 넣으면 1,2,4,6 순서로 들어가게 된다. 문제에서는 큰 숫자를 먼저 출력하라고 했으므로, 내림차순으로 큐에 들어가게 하면 된다. 우선순위 큐는 기본적(초기화할 때 매개변수가 없다면)으로 낮은 숫자를 우선순위로 하므로, 내림차순으로 큐에 들어가게 하려면 Priority Queue를 초기화할 때 매개변수로 Collections.reverseOrder() 를 넣어주면 된다. Collections에서 제공하는 reverseOrder()로 내림차순으로 저장되게 할 수 있다. Scanner.. 1043번: 거짓말(Java) 한 파티에 진실을 아는 사람이 있다면 나머지 사람들에게도 진실을 알리면 된다고 생각했다. 그러면 진실을 절대 알 수 없는 사람들만 참가했던 파티 수를 얻을 수 있기 때문이다. 가장 먼저 person class를 만들었다. 각 person은 아이디(사람 번호), 진실을 아는지 여부, 친구들을 가지고 있다. 친구들을 만든 이유는 거짓말이라는 것을 알았을 때 같이 파티에 참가했던 친구들에게 소문은 퍼뜨려야 하기 때문이다. public static class person { int id;//아이디 boolean know;//진실을 아는지 여부 Stack friends;//친구들 person(int id, boolean know) { this.id = id; this.know = know; friends = ne.. 2493번: 탑(Java) 이런 유형은 처음 봐서 푸는 데 조금 걸렸다. 처음엔 Stack의 get()을 써서 모든 값을 비교해 봤지만, 예상대로 시간초과가 났다. Stack의 get()을 쓰는 목적이 index를 얻는 것이라는 것을 생각해 보다가 int[2] 배열을 쓰면 index와 값을 동시에 저장할 수 있다는 생각을 했다. //변수 선언 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; StringBuilder sb = new StringBuilder(); Stack stack = new Stack(); int num[]; int n = Integer.parseInt(br.readLine()); st = ne.. 24797번:알파벳 블록(Java) 양방향 queue(Deque)와 Stack을 이용해 풀었다. 명령어에 따라 맨 앞, 맨뒤에 문자를 추가해야 했으므로, 문자열은 Deque로 만들었다. 가장 나중에 추가된 문자를 제거해야 했으므로, Stack을 사용해 First In Last Out 방식을 사용했다. 마지막으로 추가된 문자가 맨 앞에 추가되었는지 맨뒤에 추가되었는지 두 가지의 값만 필요했기 때문에 Stack에 넣을 수 있는 자료형으로 Boolean을 택했다. Scanner scanner = new Scanner(System.in); Deque list = new LinkedList();//문자열 Stack history = new Stack();//마지막으로 넣은 문자가 앞에 넣은 문자인지 뒤에 넣은 문자인지 판별 int n = scann.. 13414번: 수강신청(Java) 학번을 저장하면서 만약 이미 저장하고 있는 학번이라면(한번 더 클릭했다면) 삭제하고 다시 저장하면 순서의 맨 뒤로 저장된다. LinkedList를 써서 풀었더니 시간초과가 생겼다. 구글링을 해 보니 LinkedList의 add, remove 연산의 시간복잡도가 O(n)이라는 것이 원인이라는 결론이 나왔다. for문을 사용하며 입력을 받음과 동시에 add, remove를 하니 시간복잡도가 O(n^2) 이 되는 것이었다. 그래서 LinkedHashSet을 사용했다. 기존의 Set은 순서를 보장하지 않지만, LinkedHashSet은 순서를 보장하므로 클릭 순서에 따라 저장할 수 있다. 입력이 많으므로 BufferedReader를 사용했다. BufferedReader br = new BufferedReader.. 1417번: 국회의원 선거(Java) 처음엔 int 배열을 사용해 푸려고 했었다. 하지만 Array.sort로 내림차순 정렬을 하기 위해선 Comparator.reverseOrder()을 사용해야 했기 때문에 int 배열 대신 Integer 배열을 사용해 풀기로 했다. 우선 다솜이는 기호 1번이기 떄문에 후보 수롤 입력받은 후 후보 수 - 1 만큼의 Integer 배열을 생성하고 다솜이의 득표수를 저장할 int 변수를 따로 만든다. 다음으로 후보들의 득표수를 입력받을 차례다. 우선 다솜이의 득표수를 따로 입력받은 후에 나머지 후보들의 득표 수를 입력받는다. Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); Integer[] list = new Integer[n-1]; .. 이전 1 2 3 다음
