선우 Design LAB

개요 1978번은 주어진 숫자 N개 중 소수를 찾는 문제이고, 2581번은 주어진 범위 M부터 N까지의 숫자 중 소수(+ 최소값)를 찾는 문제입니다. 두 문제 모두 소수를 찾는 문제로, 저는 두 가지 방법으로 문제를 해결했습니다.O(N^2)의 시간 복잡도를 갖는 단순 구현O(N)의 시간 복잡도를 갖는 에라토스테네스의 체 사실 단계 별로 풀어보기의 문제 설명에는 첫 번째 방법이 작성되어 있습니다.그러나 에라토스테네스의 체 방법으로도 풀이가 가능합니다.  시간과 메모리 상 큰 차이는 보이지 않는 것 같은데, 입력 값의 범위가 작아서 그렇습니다.제출한 코드로 숫자 범위를 넓혀 테스트한 결과 큰 차이가 있었습니다.  단순 구현은 M=1, N=10만에서 약 2초가 걸렸고 M=1, N=100만에서 약 23초가 걸렸..

접근법트리는 그래프의 일종입니다. 문제에서 입력으로 주어지는 노드의 연결 정보는 그래프의 간선 정보나 다름 없습니다.간선 정보로 그래프를 구성한 뒤 트리의 루트인 1번 정점에서 부터 그래프 탐색을 하면 됩니다. 그래프 초기화입력으로 주어진 간선 정보를 토대로 그래프를 초기화 하는 코드입니다.각 정점에 연결된 인접 정점들을 표기하기 위해 Map> 자료구조를 사용했습니다.static Map> tree = new HashMap();public static void initTree(int v, int w) { if(!tree.containsKey(v)) { // 정점 v를 최초로 입력 받았을 경우 LinkedList list = new LinkedList(); list.add(w)..

접근법트리 자료구조를 표현하기 위해 배열을 선언합니다. 배열의 타입은 Node[] 입니다.트리의 각 노드를 표현하기 위해 왼쪽, 오른쪽 자식을 가리킬 수 있는 Node 클래스를 선언합니다.'A' 'B' 'C' 등 각 Node의 값은 배열의 인덱스로 표현할 수 있습니다. Node 클래스class Node { int left; // 왼쪽 자식의 인덱스 int right; // 오른쪽 자식의 인덱스 public Node(int left, int right) { this.left = left; this.right = right; }} 왼쪽 자식의 인덱스와 오른쪽 자식의 인덱스를 포함하는 Node 클래스를 생성했습니다.Node 배열을 생성하고, 알파벳 A를 기준으로 ..

접근법여는 괄호 '(' 일 때는 막대나 레이저 상관 없이 스택에 push 합니다.닫는 괄호 ')' 일 때 두 가지 경우의 수가 있습니다. 레이저 또는 막대의 끝을 나타낼 수 있습니다.레이저라면 현재 스택 사이즈 (아직 끝나지 않은 막대의 수)를 더합니다.막대의 끝이라면 잘린 막대가 하나 늘어난 것이므로 1을 더합니다. (아래 그림에서 빨간색으로 표시) Java 코드import java.io.*;import java.util.*;class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..

문제 해설 맨 위의 카드를 제거하고, 새로운 맨 위의 카드를 맨 아래로 삽입하면 됩니다. 카드의 제거가 위쪽, 카드의 삽입이 아래쪽에서 이뤄지므로 큐 자료구조를 활용할 수 있습니다. 문제 풀이 계획 필요 변수 변수명 타입 초기값 설명 q Queue 큐 N int 카드 갯수 해결 로직 N을 입력 받는다. queue에 차례대로 1부터 N까지 삽입한다. queue 사이즈가 1이 될 때 까지 다음을 반복한다. 맨 위의 카드를 제거한다. 맨 위의 카드를 제거하고 다시 맨 아래에 삽입한다. 마지막으로 남은 숫자를 출력한다. 풀이 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import ja..

문제 해설 큐 자료구조를 직접 구현하면 되는 문제입니다. 자바 기본 제공 큐를 사용해도 됩니다. 이 글에서는 배열로 직접 큐를 구현하였습니다. 문제 풀이 계획 필요 변수 변수명 타입 초기값 설명 N int 명령어 수 command String 명령어 queue int[] 큐 배열 front int 0 큐의 머리를 가리키는 포인터 back int 0 큐의 끝을 가리키는 포인터 해결 로직 N을 입력받는다. N번 동안 명령어를 입력받는다. 명령어에 따라 기능을 분기처리 한다. 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; im..

문제 해설 n개의 탑이 일직선으로 세워져 있습니다. 이 탑들의 꼭대기에서는 무조건 왼쪽 방향으로 레이저 빔이 나가는데, 그 신호를 수신하는 건 가장 먼저 레이저를 맞는 단 하나의 탑입니다. 각 탑에서 쏘는 레이저를 몇 번째 탑이 맞는지 구하는 문제입니다. 문제 풀이 계획 필요 변수 변수명 타입 초기값 설명 N int 탑의 개수 stack Stack Tower 객체를 저장하는 스택 X Tower { int height; int index; } Tower 클래스, 각 탑의 높이와 인덱스(순서)를 갖는다. 해결 로직 주어진 탑의 개수 N의 범위가 1 이상 500000 이하인데 1.5초 시간제한을 가지므로, O(n) 시간 안으로 해결해야 합니다. (1억 번 연산 ≒ 1초) 따라서 각 탑의 높이를 배열에 저장하고..

문제 해설 1부터 n까지의 수를 차례로 스택에 넣었다가 뺌으로써 문제에서 주는 임의의 수열을 만들 수 있다면, 스택에 숫자를 넣고 빼는 순서를, 아니라면 NO를 출력하는 문제입니다. 수를 오름차순으로 차례로 넣고 있기 때문에 스택의 가장 윗부분 숫자 보다 크거나 같은 숫자는 뺄 수 있지만, 작은 숫자는 빼낼 수 없습니다. 따라서 NO를 출력해야 합니다. 문제 풀이 계획 필요 변수 변수명 타입 초기값 설명 n int 첫째 줄에 주어지는 정수 num int n번에 걸쳐 입력 받을 숫자(수열의 숫자) cur int 1 1부터 스택에 들어갈 오름차순 숫자 arr int[] 부른 숫자를 저장할 배열 pos int 0 배열(스택)의 마지막 인덱스를 가리키는 변수 해결 로직 n을 입력 받는다. 수열의 숫자 num을 ..

문제 해설 문제에서 주어지는 정수들을 모두 더한 합을 구하는 문제입니다. 단, 0이 입력 될 때 마다 가장 마지막에 불렀던 숫자를 합계에서 빼야 합니다. 문제 풀이 계획 필요 변수 변수명 타입 초기값 설명 K int 첫째 줄에 주어지는 정수 sum int 0 부른 숫자를 모두 더한 합 (문제에서 수의 합이 2^31-1 보다 작다고 했으므로 int 형을 사용해도 된다.) arr int[] 부른 숫자를 저장할 배열 pos int 0 배열의 마지막 인덱스를 가리키는 변수 해결 로직 K를 입력 받는다. K 번 만큼 숫자를 입력 받는다. 0이라면 arr[--pos] (배열의 가장 마지막 인덱스 원소)를 sum에서 뺀다. 0이 아니라면 arr[pos]에 숫자를 삽입하고 sum에 더한다. sum을 출력한다. 풀이 코..

문제 해설 스택 자료구조를 직접 구현하는 문제입니다. 총 다섯가지의 명령에 따라 기능을 구현하면 됩니다. 문제 풀이 계획 필요 변수 변수명 타입 설명 N int 첫째 줄에 주어지는 명령의 수 arr int[] 숫자를 저장할 배열 top int 배열의 최종 인덱스를 가리킬 변수 해결 로직 명령 수 N을 입력 받는다. N 번에 걸쳐 명령어를 입력 받는다. 명령어 별로 분기 처리하여 각 로직을 처리한다. 풀이 코드 package com.newlecture.app.util; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import jav..