[BOJ] 1920. 수 찾기 - (Java)

Problem

제출일 : 2020-04-02

문제 풀이 시간 : 20M

난이도 : ★★

---

link : https://www.acmicpc.net/problem/11650

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

Input

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 $-2^{31}$ 보다 크거나 같고 $2^{31}$ 보다 작다.

Output

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

Example

input

5
4 1 5 2 3
5
1 3 7 9 5

output

1
1
0
0
1

Solution & Inpression

정렬 후 이분탐색

Code

언어 : JAVA

메모리 : 170092 kb

실행 시간 : 1164 ms

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N;
    static int[] data;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        data = new int[N];

        for (int i = 0; i < N; i++) {
            data[i] = sc.nextInt();
        }

        Arrays.sort(data);

        int M = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            if (find(sc.nextInt()))
                sb.append("1\n");
            else
                sb.append("0\n");
        }
        System.out.println(sb);
    }

    private static boolean find(int x) {
        int s = 0, e = N, m = 0;
        while (s < e) {
            m = (s + e) >> 1;
            if (data[m] == x)
                return true;
            else if (data[m] > x) {
                e = m;
            } else {
                s = m + 1;
            }
        }

        return false;
    }
}

[BOJ] 11650. 좌표 정렬하기 - (Java)

Problem

제출일 : 2020-04-02

문제 풀이 시간 : 10M

난이도 : ★★

---

link : https://www.acmicpc.net/problem/11650

2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

Input

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

Output

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

Example

input

5
3 4
1 1
1 -1
2 2
3 3

output

1 -1
1 1
2 2
3 3
3 4

Solution & Inpression

정렬조건을 Comparator을 이용하여 정의하여 Arrays.sort()함수를 이용하여 정렬뒤 출력하였습니다.

Code

언어 : JAVA

메모리 : 179020 kb

실행 시간 : 1352 ms

import java.awt.Point;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Silver5_11650_좌표정렬하기 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 점의 개수
        Point[] points = new Point[N];

        for (int i = 0; i < N; i++) {
            points[i] = new Point(sc.nextInt(), sc.nextInt());
        }

        Arrays.sort(points, new Comparator<Point>() {

            @Override
            public int compare(Point o1, Point o2) {
                if (o1.x != o2.x)
                    return o1.x - o2.x;
                else
                    return o1.y - o2.y;
            }
        });
        StringBuilder sb = new StringBuilder();
        for (Point point : points) {
            sb.append(point.x).append(" ").append(point.y).append("\n");
        }
        System.out.println(sb);
    }
}

[BOJ] 10814. 나이순 정렬 - (Java)

Problem

제출일 : 2020-04-02

문제 풀이 시간 : 10M

난이도 : ★★

---

link : https://www.acmicpc.net/problem/10814

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

Input

첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.

Output

첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.

Example

input

3
21 Junkyu
21 Dohyun
20 Sunyoung

output

20 Sunyoung
21 Junkyu
21 Dohyun

Solution & Inpression

나이를 오름차순으로 정렬하여 출력... Class를 만들어 User를 저장하는 객체를 생성 Comparable을 이용하여 정렬조건을 정의하여 문제를 해결하였습니다.

Code

언어 : JAVA

메모리 : 147412 kb

실행 시간 : 1832 ms

import java.util.Arrays;
import java.util.Scanner;

public class Silver5_10814_나이순정렬 {
    static class User implements Comparable<User> {
        int age;
        String name;

        public User(int age, String name) {
            super();
            this.age = age;
            this.name = name;
        }

        @Override
        public int compareTo(User o) {
            return this.age - o.age;
        }

        @Override
        public String toString() {
            return age + " " + name;
        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        User[] users = new User[N];
        for (int i = 0; i < N; i++) {
            users[i] = new User(sc.nextInt(), sc.next());
        }

        Arrays.sort(users);

        for (User user : users) {
            System.out.println(user);
        }
    }
}

[BOJ] 2751. 수 정렬하기 2 - (Java)

Problem

제출일 : 2020-04-02

문제 풀이 시간 : 10M

난이도 : ★★

---

link : https://www.acmicpc.net/problem/2751

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

Input

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

Output

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

Example

input

5
5
4
3
2
1

output

1
2
3
4
5

Solution & Inpression

Arrays.sort() >> 시간초과,

BufferedReader >> 시간초과,

정렬알고리즘을 구현하여 문제를 해결해야 하나 고민하다 그냥 값의 범위만큼 배열을 만들어 각 위치에 저장한뒤 순서대로 StringBuilder을 이용하여 값을 출력했다.

이때 주의해야할 점이 값의 범위가 절대값이 1,000,000 보다 작거나 같은 정수이기때문에 범위에 음수가 포함된다.

저장할때 음수를 제거하기위해 +1000000을 수행했고 출력할때 -1000000을 한뒤 원상복구후 출력하였습니다.

Code

언어 : JAVA

메모리 : 126104 kb

실행 시간 : 676 ms

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        boolean[] data = new boolean[2000001];

        for (int i = 0; i < N; i++) {
            data[Integer.parseInt(br.readLine()) + 1000000] = true;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < data.length; i++) {
            if (data[i])
                sb.append(i - 1000000).append('\n');
        }
        System.out.println(sb);
    }
}

[BOJ] 1181. 단어정렬 - (Java)

Problem

제출일 : 2020-04-02

문제 풀이 시간 : 30M

난이도 : ★★

---

link : https://www.acmicpc.net/problem/1181

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

Input

첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

Output

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다

Example

input

13
but
i
wont
hesitate
no
more
no
more
it
cannot
wait
im
yours

output

i
im
it
no
but
more
wait
wont
yours
cannot
hesitate

Solution & Inpression

Set을 이용하여 중복을 제거한 뒤 ArrayList에 옮겨 정렬하였습니다

정렬은 Comparator을 이용하여 문제에 조건에 따라 재정의 하였습니다.

Code

언어 : JAVA

메모리 : 35944 kb

실행 시간 : 720 ms

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Silver5_1181_단어정렬 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Set<String> set = new HashSet<>();
        for (int i = 0; i < N; i++) {
            set.add(sc.next());
        }
        ArrayList<String> data = new ArrayList<>(set);
        Collections.sort(data, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if (o1.length() != o2.length())
                    return o1.length() - o2.length();
                else
                    return o1.compareTo(o2);
            }
        });
        for (String string : data) {
            System.out.println(string);
        }
    }
}

[BOJ] 2798. 블랙잭 - (Java)

제출일 : 2020-04-01

문제 풀이 시간 : 10M

난이도 : ★

---

link : https://www.acmicpc.net/problem/2798

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버젼의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

예제

입력

5 21
5 6 7 8 9

출력

21

해결방안

조합을 이용하여 문제를 해결하였습니다. 조합의 결과가 M 이하이고 현재보다 값이 크다면 갱신하여 최종적인 답을 구했습니다.

코드

언어 : JAVA

메모리 : 14616 kb

실행 시간 : 124 ms

package BOJ.BF;
import java.util.Scanner;

public class Bronze2_2798_블랙잭 {
    static int N, M, ans;
    static int[] card;
    static boolean[] visit;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        card = new int[N];
        visit = new boolean[N];
        for (int i = 0; i < N; i++) {
            card[i] = sc.nextInt();
        }
        ans = -1;
        solve(0, 0, 0);
        System.out.println(ans);
    }

    private static void solve(int index, int depth, int sum) {
        if (depth == 3) {
            if (sum <= M && ans < sum)
                ans = sum;
            return;
        }
        for (int i = index; i < N; i++) {
            if (!visit[i]) {
                visit[i] = true;
                solve(i, depth + 1, sum + card[i]);
                visit[i] = false;
            }
        }

    }
}

Django Tutorial PJT

Part 1 : 장고 앱 작성하기

1. Django 설치 확인

   python -m django --version

2. 프로젝트 만들기

   jango-admin startproject [프로젝트명]

3. 디렉토리 구조와 역할

   tutorial
   │  manage.py         # Django 프로젝트와 다양한 방법으로 상호작용 하는 커맨드 라인의 유틸리티
   │
   └─tutorial           # 디렉토리 내부에는 프로젝트를 위한 실제 Python 패키지들이 저장 
           settings.py  # 현재 Django 프로젝트의 환경 및 구성을 저장(환경설정이 어떻게 동작하는지 확인할 수 있음)
           urls.py      # 현재 Django 프로젝트의 URL 선언을 저장합니다. (Django로 작성된 사이트의 "목차"라 할수 있음)
           wsgi.py      #  현재 프로젝트를 서비스하기 위한 WSGI 호환 웹 서버의 진입점입니다
           __init__.py  # Python으로 하여금 이 디렉토리를 패키지처럼 다루라고 알려주는 용도의 단순한 빈파일

개발서버

1. 프로젝트가 제대로 동작하는지 확인

   cd tutorial
   python mange.py runserver

   커맨드 라인에서 다음과 같은 출력을 확인할 수 있다.

   Watching for file changes with StatReloader
   Performing system checks...
   
   System check identified no issues (0 silenced).
   
   You have 17 unapplied migration(s). Your project may not work properly until you apply the migrations for app(s): admin, auth, contenttypes, sessions.        
   Run 'python manage.py migrate' to apply them.
   March 31, 2020 - 14:52:22
   Django version 2.2.7, using settings 'tutorial.settings'
   Starting development server at http://127.0.0.1:8000/
   Quit the server with CTRL-BREAK.

   
   

   포트 변경하기

   $ python manage.py runserver 8080

   $ python manage.py runserver 0:8000

   runserver 명령은 내부 IP의 8000번 포트로 개발 서버를 띄우지만 위 명령어로 포트를 8080으로 서버를 시작할 수 있습니다.

   아래와 같이 http://127.0.0.1:8000/에 접속하여 잘 동작하는 것을 확인 할 수 있습니다.

   

Reference

https://docs.djangoproject.com/ko/3.0/intro/tutorial01/

[BOJ] 12851. 숨바꼭질2 - (Java)

Problem

제출일 : 2020-03-22

문제 풀이 시간 : 1H 30M

난이도 : ★★

---

link : https://www.acmicpc.net/problem/12851

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

Output

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

Example

input

8 9 10

output

1 2 8 9 10

Solution & Inpression

같은 점을 중복으로 방문을 가능하게 하기 위해 q에서 값을 뺄 때 방문 처리를 해주었음.

Code

언어 : JAVA

메모리 : 48664 kb

실행 시간 : 236 ms

package BOJ.DFS_BFS;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Gold5_12851_숨바꼭질2 {
    static int N, K;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();

        boolean[] visited = new boolean[100001];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] { N, 0 });
        visited[N] = true;

        int[] next = new int[3];
        int time = Integer.MAX_VALUE;
        int count = 0;

        while (!q.isEmpty()) {
            int[] now = q.poll();

            if (now[1] > time)
                continue;
            else if (now[0] == K) {
                if (time > now[1]) {
                    time = now[1];
                    count = 1;
                } else if (time == now[1])
                    count++;
            }

            visited[now[0]] = true;

            next[0] = now[0] - 1;
            next[1] = now[0] + 1;
            next[2] = now[0] << 1;

            for (int i = 0; i < 3; i++) {
                if (0 <= next[i] && next[i] <= 100000 && !visited[next[i]])
                    q.add(new int[] { next[i], now[1] + 1 });
            }
        }
        System.out.println(time);
        System.out.println(count);
    }

}