deeprun

183. Customers Who Never Order

 문제 설명

Create table If Not Exists Customers (id int, name varchar(255))
Create table If Not Exists Orders (id int, customerId int)
Truncate table Customers
insert into Customers (id, name) values ('1', 'Joe')
insert into Customers (id, name) values ('2', 'Henry')
insert into Customers (id, name) values ('3', 'Sam')
insert into Customers (id, name) values ('4', 'Max')
Truncate table Orders
insert into Orders (id, customerId) values ('1', '3')
insert into Orders (id, customerId) values ('2', '1')

+-------------+------+
| Column Name | Type |
+-------------+------+
| id          | int  |
| customerId  | int  |
+-------------+------+
id is the primary key column for this table.
customerId is a foreign key of the ID from the Customers table.
Each row of this table indicates the ID of an order and the ID of the customer who ordered it.

 입출력 예

Example 1:

Input: 
Customers table:
+----+-------+
| id | name  |
+----+-------+
| 1  | Joe   |
| 2  | Henry |
| 3  | Sam   |
| 4  | Max   |
+----+-------+
Orders table:
+----+------------+
| id | customerId |
+----+------------+
| 1  | 3          |
| 2  | 1          |
+----+------------+
Output: 
+-----------+
| Customers |
+-----------+
| Henry     |
| Max       |
+-----------+

 Oracle Query

select name as customers
from customers
where id not in
(select customerid from orders);

서브쿼리 (select customerid from orders)에서 customerid 결과가 아닌 id일 때, 컬럼 name 출력

* 참고 링크 : https://leetcode.com/problems/customers-who-never-order/discuss/1080196/Oracle-easiest-solution

https://stand-atop.tistory.com/144

 출처

https://leetcode.com/problems/customers-who-never-order/

627. Swap Salary

 문제 설명

Table: Salary

+----------------+-------------+
| Column Name | Type          |
+----------------+-------------+
| id                 | int             |
| name            | varchar       |
| sex               | ENUM        |
| salary            | int             |
+----------------+-------------+

id is the primary key for this table.
The sex column is ENUM value of type ('m', 'f').
The table contains information about an employee.

id는 이 테이블의 프라이머리 키입니다.
Sex 열은 유형의 ENUM 값('m', 'f')입니다.
표에는 직원에 대한 정보가 포함되어 있습니다.

 입출력 예

Input: 
Salary table:
+----+------+-----+--------+
| id | name | sex | salary |
+----+------+-----+--------+
| 1  | A    | m   | 2500   |
| 2  | B    | f   | 1500   |
| 3  | C    | m   | 5500   |
| 4  | D    | f   | 500    |
+----+------+-----+--------+
Output: 
+----+------+-----+--------+
| id | name | sex | salary |
+----+------+-----+--------+
| 1  | A    | f   | 2500   |
| 2  | B    | m   | 1500   |
| 3  | C    | f   | 5500   |
| 4  | D    | m   | 500    |
+----+------+-----+--------+
Explanation: 
(1, A) and (3, C) were changed from 'm' to 'f'.
(2, B) and (4, D) were changed from 'f' to 'm'.

 Oracle Query

UPDATE salary s
SET sex = 
CASE 
  WHEN sex='m' THEN 'f'
  WHEN sex='f' THEN 'm'
END;

update salary 
set sex = decode(sex,'m','f','m');

DECODE문 - ORACLE에서만 존재하는 함수

DECODE(컬럼명, 조건, True 결과값, False 결과값)

https://sseoui.tistory.com/110

* 참고 링크 : https://leetcode.com/problems/swap-salary/discuss/504204/Oracle-solution

https://leetcode.com/problems/swap-salary/discuss/708246/Using-Decode

 출처

https://leetcode.com/problems/swap-salary/

Hashing

 문제 설명

APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정의한다. 해시 함수는 무궁무진한 응용 분야를 갖는데, 대표적으로 자료의 저장과 탐색에 쓰인다.

이 문제에서는 여러분이 앞으로 유용하게 쓸 수 있는 해시 함수를 하나 가르쳐주고자 한다. 먼저, 편의상 입력으로 들어오는 문자열에는 영문 소문자(a, b, ..., z)로만 구성되어있다고 가정하자. 영어에는 총 26개의 알파벳이 존재하므로 a에는 1, b에는 2, c에는 3, ..., z에는 26으로 고유한 번호를 부여할 수 있다. 결과적으로 우리는 하나의 문자열을 수열로 변환할 수 있다. 예를 들어서 문자열 "abba"은 수열 1, 2, 2, 1로 나타낼 수 있다.

해시 값을 계산하기 위해서 우리는 문자열 혹은 수열을 하나의 정수로 치환하려고 한다. 간단하게는 수열의 값을 모두 더할 수도 있다. 해시 함수의 정의에서 유한한 범위의 출력을 가져야 한다고 했으니까 적당히 큰 수 M으로 나눠주자. 짜잔! 해시 함수가 완성되었다. 이를 수식으로 표현하면 아래와 같다.

해시 함수의 입력으로 들어올 수 있는 문자열의 종류는 무한하지만 출력 범위는 정해져있다. 다들 비둘기 집의 원리에 대해서는 한 번쯤 들어봤을 것이다. 그 원리에 의하면 서로 다른 문자열이더라도 동일한 해시 값을 가질 수 있다. 이를 해시 충돌이라고 하는데, 좋은 해시 함수는 최대한 충돌이 적게 일어나야 한다. 위에서 정의한 해시 함수는 알파벳의 순서만 바꿔도 충돌이 일어나기 때문에 나쁜 해시 함수이다. 그러니까 조금 더 개선해보자.

어떻게 하면 순서가 달라졌을때 출력값도 달라지게 할 수 있을까? 머리를 굴리면 수열의 각 항마다 고유한 계수를 부여하면 된다는 아이디어를 생각해볼 수 있다. 가장 대표적인 방법은 항의 번호에 해당하는 만큼 특정한 숫자를 거듭제곱해서 곱해준 다음 더하는 것이 있다. 이를 수식으로 표현하면 아래와 같다.

보통 r과 M은 서로소인 숫자로 정하는 것이 일반적이다. 우리가 직접 정하라고 하면 힘들테니까 r의 값은 26보다 큰 소수인 31로 하고 M의 값은 1234567891(놀랍게도 소수이다!!)로 하자.

이제 여러분이 할 일은 위 식을 통해 주어진 문자열의 해시 값을 계산하는 것이다. 그리고 이 함수는 간단해 보여도 자주 쓰이니까 기억해뒀다가 잘 써먹도록 하자.

 입력

첫 줄에는 문자열의 길이 L이 들어온다. 둘째 줄에는 영문 소문자로만 이루어진 문자열이 들어온다.

입력으로 주어지는 문자열은 모두 알파벳 소문자로만 구성되어 있다.

 출력

문제에서 주어진 해시함수와 입력으로 주어진 문자열을 사용해 계산한 해시 값을 정수로 출력한다.

 Python 코드

n = int(input()) #제시할 문자열의 길이를 입력받는다.
str_ = list(input()) #문자열을 입력받아 리스트에 대입한다.
res = 0 # 출력할 변수 res를 선언한다.

for i in range(n): # 문자열의 길이만큼 반복한다.
    res += ((ord(str_[i]) - 96) * (31 ** i))
# 리스트 내 각각의 요소들은 아스키코드값으로 변경 후 96을 빼면 
# a는 1, b는 2의 값을 지니게 된다.
# 계수가 31이고 문자열의 순서에 따라 지수가 높아지므로 이를 고려하여 식을 짜면 위와 같다.

print(res % 1234567891)
# 해시 함수의 정의에서 유한한 범위의 출력을 가져야 한다고 했으므로 M을 나누어 출력한다.

* 참고 링크 : https://velog.io/@cornflower_blue/%EB%B0%B1%EC%A4%80%ED%8C%8C%EC%9D%B4%EC%8D%AC-15829%EB%B2%88-Hashing-%ED%92%80%EC%9D%B4

# readline을 사용하기 위해 Import
from sys import stdin

# 첫 줄에는 문자열의 길이 L을 입력
# 1 <= L <= 50
# 정수형으로 변환합니다.
L = int(stdin.readline())

# 둘째 줄에는 영문 소문자로만 이루어진 문자열을 입력
# 맨 끝의 \n은 떼어준다.
string = stdin.readline().rstrip()

# 해시 값을 계산할 때 필요한 r, M의 값을 저장하는 변수를 선언
r = 31
M = 1234567891

# mod M을 구하기 전의 ai * r^i의 합계를 저장할 변수를 선언
ar_sum = 0

# 입력한 문자열에서 한 글자씩 반복
for idx in range(L):
    # 현재 글자의 고유 번호를 저장하는 변수를 선언
    ai = ord(string[idx]) -ord('a') +1

    #현재 글자의 ai * r^i 값을 ar_sum에 더해준다.
    ar_sum += ai * (r ** idx)

# 해시값인 ar_sum을 M으로 나눈 뒤의 나머지의 값을 출력
print(ar_sum % M)

 C++ 코드

#include <iostream> 
#include <string> 
using namespace std; 

const int MOD = 1234567891; 
const int MULTIPLY = 31; 

int main(void) { 
int L; 
cin >> L; 
string s; 
cin >> s; 

long long sum = 0; 
long long R = 1; 

for (int i = 0; i < s.length(); i++) { 
	sum = (sum + (s[i] - 'a' + 1) * R) % MOD; 
	R = (R*MULTIPLY) % MOD; 
} 

cout << sum << "\n"; 
return 0; 
}

* 참고 링크 : https://jaimemin.tistory.com/1445

 출처

https://www.acmicpc.net/problem/15829

전자레인지

 문제 설명

3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 각각 5분, 1분, 10초이다.

냉동음식마다 전자레인지로 요리해야할 시간 T가 초단위로 표시되어 있다. 우리는 A, B, C 3개의 버튼을 적절히 눌러서 그 시간의 합이 정확히 T초가 되도록 해야 한다. 단 버튼 A, B, C를 누른 횟수의 합은 항상 최소가 되어야 한다. 이것을 최소버튼 조작이라고 한다. 

만일 요리시간이 100초라고 하면(T=100) B를 1번, C는 4번 누르면 된다. 이와 다르게 C를 10번 눌러도 100초가 되지만 이 경우 10번은 최소 횟수가 아니기 때문이 답이 될 수 없다. 이 경우 B 1번, C 4번, 총 5번이 최소버튼 조작이다. 그리고 T=234와 같이 3개의 버튼으로 시간을 정확히 맞출 수 없는 경우도 있다. 

여러분은 주어진 요리시간 T초를 맞추기 위한 최소버튼 조작 방법을 구하는 프로그램을 작성해야 한다. 

 입력

첫 번째 줄에는 요리시간 T(초)가 정수로 주어져 있으며 그 범위는 1 ≤ T ≤ 10,000 이다. 

 출력

여러분은 T초를 위한 최소버튼 조작의 A B C 횟수를 첫 줄에 차례대로 출력해야 한다. 각각의 횟수 사이에는 빈 칸을 둔다. 해당 버튼을 누르지 않는 경우에는 숫자 0을 출력해야한다. 만일 제시된 3개의 버튼으로 T초를 맞출 수 없으면 음수 -1을 첫 줄에 출력해야 한다. 

 Python 코드

T = int(input())                # 요리 시간 T를 int type으로 입력을 받는다.

button = [300, 60 ,10]          # 버튼 300, 60, 10을 리스트에 담아준다.

if T % 10 != 0:                 # 만약 T를 10으로 나누었을 때 나머지가 0이 아니면 -1 출력
    print(-1)
else:                           # 그게 아니라면
    for i in button:            # button 안에 있는 i 요소 반복
        print(T//i, end = " ")  # T를 i로 나누었을 때 몫을 띄어쓰기로 출력
        T = T % i               # T는 T를 i로 나누었을 때 몫으로 바꾼다.

* 참고 링크 : https://www.youtube.com/watch?v=FoTqNiXgd-0 

 C++ 코드

#include<iostream>
using namespace std;

int main() {
	
	// A : 300초, B : 60초, C : 10초
	int a, b, c = 0;
	int t;
	cin >> t;

	if (t % 10 != 0) cout << "-1";
	else {
		a = t / 300;
		b = (t % 300) / 60;
		c = ((t % 300) % 60) / 10;
		cout << a << " " << b << " " << c;
	}

	return 0;

}

* 참고 링크 : https://jeongminhee99.tistory.com/86

 출처

https://www.acmicpc.net/problem/10162

Not Boring Movies

 문제 설명

Create table If Not Exists cinema (id int, movie varchar(255), description varchar(255), rating float(2, 1))
Truncate table cinema
insert into cinema (id, movie, description, rating) values ('1', 'War', 'great 3D', '8.9')
insert into cinema (id, movie, description, rating) values ('2', 'Science', 'fiction', '8.5')
insert into cinema (id, movie, description, rating) values ('3', 'irish', 'boring', '6.2')
insert into cinema (id, movie, description, rating) values ('4', 'Ice song', 'Fantacy', '8.6')
insert into cinema (id, movie, description, rating) values ('5', 'House card', 'Interesting', '9.1')

+----------------+----------+
| Column Name    | Type     |
+----------------+----------+
| id             | int      |
| movie          | varchar  |
| description    | varchar  |
| rating         | float    |
+----------------+----------+
id is the primary key for this table.
Each row contains information about the name of a movie, its genre, and its rating.
rating is a 2 decimal places float in the range [0, 10]

 입출력 예

Example 1:

Input: 
Cinema table:
+----+------------+-------------+--------+
| id | movie      | description | rating |
+----+------------+-------------+--------+
| 1  | War        | great 3D    | 8.9    |
| 2  | Science    | fiction     | 8.5    |
| 3  | irish      | boring      | 6.2    |
| 4  | Ice song   | Fantacy     | 8.6    |
| 5  | House card | Interesting | 9.1    |
+----+------------+-------------+--------+
Output: 
+----+------------+-------------+--------+
| id | movie      | description | rating |
+----+------------+-------------+--------+
| 5  | House card | Interesting | 9.1    |
| 1  | War        | great 3D    | 8.9    |
+----+------------+-------------+--------+
Explanation: 
We have three movies with odd-numbered IDs: 1, 3, and 5. The movie with ID = 3 is boring so we do not include it in the answer.

 Oracle Query

select * 
from cinema 
where description!='boring' and mod(id, 2) = 1 
order by rating desc;

* 참고 링크 : https://leetcode.com/problems/not-boring-movies/discuss/1192216/simple-or-100-memory-or-oracle

MOD ( ) - 나눈 나머지 값 반환

select mod(3,2)
from dual
-- 결과값: 1

* 참고 링크 : https://devjhs.tistory.com/404, https://20140501.tistory.com/80

 출처

https://leetcode.com/problems/not-boring-movies/

Classes More Than 5 Students

 문제 설명

Create table If Not Exists Courses (student varchar(255), class varchar(255))
Truncate table Courses
insert into Courses (student, class) values ('A', 'Math')
insert into Courses (student, class) values ('B', 'English')
insert into Courses (student, class) values ('C', 'Math')
insert into Courses (student, class) values ('D', 'Biology')
insert into Courses (student, class) values ('E', 'Math')
insert into Courses (student, class) values ('F', 'Computer')
insert into Courses (student, class) values ('G', 'Math')
insert into Courses (student, class) values ('H', 'Math')
insert into Courses (student, class) values ('I', 'Math')

Write an SQL query to report all the classes that have at least five students.

Return the result table in any order.

The query result format is in the following example.

5명 이상의 학생이 있는 클래스 쿼리 확인

 입출력 예

Example 1:

Input: 
Courses table:
+---------+----------+
| student | class    |
+---------+----------+
| A       | Math     |
| B       | English  |
| C       | Math     |
| D       | Biology  |
| E       | Math     |
| F       | Computer |
| G       | Math     |
| H       | Math     |
| I       | Math     |
+---------+----------+
Output: 
+---------+
| class   |
+---------+
| Math    |
+---------+
Explanation: 
- Math has 6 students, so we include it.
- English has 1 student, so we do not include it.
- Biology has 1 student, so we do not include it.
- Computer has 1 student, so we do not include it.

 Oracle Query

/* Write your PL/SQL query statement below */
select class 
from courses
group by class
having count(distinct student) > 4

* 참고 링크 : https://leetcode.com/problems/classes-more-than-5-students/discuss/927995/Oracle-Solution

• 5명 이상의 학생이 있는 class 쿼리— having절은 group by와 같이 사용될 수 있음having count(distinct student) > 4having절은 집계함수를 가지고 조건비교를 할 때 사용한다.
  • 참고 링크 : http://www.gurubee.net/lecture/1032
  집계함수 종류
  • count / sum / avg / max / min 등
  • 참고 링크 : https://life-with-coding.tistory.com/218
• distinct 중복값 처리 (5명 이상의 학생이 중복되는 경우를 having절로 카운트)
• (5명 이상의 학생이 있는 클래스를 찾는 것이니 class로 묶어줌
• group by class

 출처

https://leetcode.com/problems/classes-more-than-5-students/

평균 구하기

 문제 설명

N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다. 다음은 N = 5, K = 3인 경우의 예시입니다.

위 그림에서 1번 마을에 있는 음식점은 [1, 2, 4, 5] 번 마을까지는 3 이하의 시간에 배달할 수 있습니다. 그러나 3번 마을까지는 3시간 이내로 배달할 수 있는 경로가 없으므로 3번 마을에서는 주문을 받지 않습니다. 따라서 1번 마을에 있는 음식점이 배달 주문을 받을 수 있는 마을은 4개가 됩니다.
마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 하도록 solution 함수를 완성해주세요.

 제한 사항

• 마을의 개수 N은 1 이상 50 이하의 자연수입니다.
• road의 길이(도로 정보의 개수)는 1 이상 2,000 이하입니다.
• road의 각 원소는 마을을 연결하고 있는 각 도로의 정보를 나타냅니다.
• road는 길이가 3인 배열이며, 순서대로 (a, b, c)를 나타냅니다.
  • a, b(1 ≤ a, b ≤ N, a != b)는 도로가 연결하는 두 마을의 번호이며, c(1 ≤ c ≤ 10,000, c는 자연수)는 도로를 지나는데 걸리는 시간입니다.
  • 두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있습니다.
  • 한 도로의 정보가 여러 번 중복해서 주어지지 않습니다.
• K는 음식 배달이 가능한 시간을 나타내며, 1 이상 500,000 이하입니다.
• 임의의 두 마을간에 항상 이동 가능한 경로가 존재합니다.
• 1번 마을에 있는 음식점이 K 이하의 시간에 배달이 가능한 마을의 개수를 return 하면 됩니다.

 입출력 예

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
주어진 마을과 도로의 모양은 아래 그림과 같습니다.

1번 마을에서 배달에 4시간 이하가 걸리는 마을은 [1, 2, 3, 5] 4개이므로 4를 return 합니다.

 Python 코드

플로이드워셜

def solution(N, road, K):
    INF = 1000000000
    answer = 0
    graph = [[INF] * (N + 1) for _ in range(N + 1)]
 
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            if i == j:
                graph[i][j] = 0
 
    for r in road:
        a, b, c = r[0], r[1], r[2]
        if graph[a][b] > c:
            graph[a][b] = c
            graph[b][a] = c
 
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            for k in range(1, N + 1):
                graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])
 
    for j in range(1, N + 1):
        if graph[1][j] <= K:
            answer += 1
 
    return answer

다익스트라 

from queue import PriorityQueue
 
 
def solution(N, road, K):
    INF = 1000000000
    answer = 0
    distance = [INF] * (N + 1)
 
    q = PriorityQueue()
    q.put([1, 0])
    distance[1] = 0
    while not q.empty():
        now, now_cost = q.get()
 
        if now_cost > distance[now]: continue
        for start, dest, cost in road:
            next_cost = now_cost + cost
            if start == now and next_cost < distance[dest]:
                distance[dest] = next_cost
                q.put([dest, next_cost])
            elif dest == now and next_cost < distance[start]:
                distance[start] = next_cost
                q.put([start, next_cost])
 
    for i in range(1, N + 1):
        if distance[i] <= K:
            answer += 1
 
    return answer

* 참고 링크 : https://foameraserblue.tistory.com/86

 C++ 코드

#include <vector>
#include <queue>
using namespace std;
 
vector<pair<int,int>> V[55];
vector<int> Dist;
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Dijkstra(int N)
{
    priority_queue<pair<int, int>> PQ;
    PQ.push(make_pair(0, 1));
    Dist[1] = 0;
 
    while (PQ.empty() == 0)
    {
        int Cost = -PQ.top().first;
        int Cur = PQ.top().second;
        PQ.pop();
 
        for (int i = 0; i < V[Cur].size(); i++)
        {
            int Next = V[Cur][i].first;
            int nCost = V[Cur][i].second;
 
            if (Dist[Next] > Cost + nCost)
            {
                Dist[Next] = Cost + nCost;
                PQ.push(make_pair(-Dist[Next], Next));
            }
        }
    }
}
 
int solution(int N, vector<vector<int> > road, int K)
{
    Dist.resize(N + 1, 2e9);
    for (int i = 0; i < road.size(); i++)
    {
        int N1 = road[i][0];
        int N2 = road[i][1];
        int Dist = road[i][2];
 
        V[N1].push_back(make_pair(N2, Dist));
        V[N2].push_back(make_pair(N1, Dist));
    }
 
    Dijkstra(N);
    int answer = 0;
    for (int i = 1; i <= N; i++)
    {
        if (Dist[i] <= K) answer++;
    }
 
    return answer;
}

* 참고 링크 : https://yabmoons.tistory.com/633

 출처

https://programmers.co.kr/learn/courses/30/lessons/12978

Big Countries

 문제 설명

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| name        | varchar |
| continent   | varchar |
| area        | int     |
| population  | int     |
| gdp         | int     |
+-------------+---------+
name is the primary key column for this table.
Each row of this table gives information about the name of a country, the continent to which it belongs, its area, the population, and its GDP value.

 입출력 예

Example 1:

Input: 
World table:
+-------------+-----------+---------+------------+--------------+
| name        | continent | area    | population | gdp          |
+-------------+-----------+---------+------------+--------------+
| Afghanistan | Asia      | 652230  | 25500100   | 20343000000  |
| Albania     | Europe    | 28748   | 2831741    | 12960000000  |
| Algeria     | Africa    | 2381741 | 37100000   | 188681000000 |
| Andorra     | Europe    | 468     | 78115      | 3712000000   |
| Angola      | Africa    | 1246700 | 20609294   | 100990000000 |
+-------------+-----------+---------+------------+--------------+
Output: 
+-------------+------------+---------+
| name        | population | area    |
+-------------+------------+---------+
| Afghanistan | 25500100   | 652230  |
| Algeria     | 37100000   | 2381741 |
+-------------+------------+---------+

 Oracle Query

select name, population, area 
from world 
where area >= 3000000 or population >= 25000000;

 출처

https://leetcode.com/problems/big-countries/

Contains Duplicate 

 문제 설명

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

 제한 사항

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109

 입출력 예

Example 1:

Input: nums = [1,2,3,1]
Output: true

Example 2:

Input: nums = [1,2,3,4]
Output: false

Example 3:

Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

 Python 코드

Python code 

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(set(nums)) != len(nums)

* 참고 링크 : https://leetcode.com/problems/contains-duplicate/discuss/1159570/Python-99.25-faster

https://leetcode.com/problems/contains-duplicate/discuss/471215/Python-sol-by-native-set-and-length.-run-time-90%2B

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
    	hashset = set()
        
        for n in nums:
        	if n in hashset:
            	    return True
        	hashset.add()
        return False

* 참고 링크 : https://www.youtube.com/watch?v=3OamzN90kPg 

 C++ 코드

C ++ code

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_map<int,bool> map;
        for(size_t i = 0;i<nums.size();++i)
        {
            if(map[nums[i]]==true)
                return true;
            map[nums[i]]=true;
        }
        return false;
    }
};

* 참고 링크 : https://kkminseok.github.io/posts/leetcode_Contains_Duplicate/

 출처

https://leetcode.com/problems/contains-duplicate/

평균 구하기

 문제 설명

자연수 N이 주어진다. N을 이진수로 바꿔서 출력하는 프로그램을 작성하시오.

 입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000,000,000,000)

 출력

N을 이진수로 바꿔서 출력한다. 이진수는 0으로 시작하면 안 된다.

 Python 코드

# 첫째 줄에 자연수 N을 입력하고 정수형으로 변환
N = int(input())

# N을 이진수로 변환하고 앞의 0b를 제외한 값을 저장
N = bin(N)[2:]

# 이진수로 변환한 결과 출력
print(N)

# print(bin(n)[2:])
# print(bin(int(input()))[2:])

* 참고 링크 : https://brightnightsky77.tistory.com/122

def trans(n):
    if (n<1):
        return '0'
    elif (n==1):
        return '1'
    if (n%2==0):
        return trans(int(n/2)) + '0'
    elif (n%2==1):
        return trans(int(n/2)) + '1'

n = int(input())
answer = trans(n)
print(answer)

* 참고 링크 : https://velog.io/@sxxzin/BaekjoonPython%EC%9D%B4%EC%A7%84%EC%88%98-%EB%B3%80%ED%99%98

https://my-coding-notes.tistory.com/137

 C++ 코드

#include <iostream>
using namespace std;

int facto(int n) {
	if (n <= 1)
		return 1;
	else
		return n * facto(n - 1);
}

int main() {
	int n;
	cin >> n;
	cout << facto(n) << '\n';
}

* 참고 링크 : https://codesyun.tistory.com/73

 출처

https://www.acmicpc.net/problem/10829

팩토리얼

 문제 설명

0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.

 입력

첫째 줄에 정수 N(0 ≤ N ≤ 12)이 주어진다.

 출력

첫째 줄에 N!을 출력한다.

 Python 코드

def factorial(n):
    result = 1
    if n > 0:
        result = n * factorial(n-1)
    return result

n = int(input())
print(factorial(n))

* 참고 링크 : https://ooyoung.tistory.com/114

 C++ 코드

#include <cstdio>

int factorial(int n)
{
    if(n <= 1)
        return 1;
    return n * factorial(n-1);
}

int main() {
    int num;
    scanf("%d",&num);
    printf("%d",factorial(num));
}

* 참고 링크 : https://cryptosalamander.tistory.com/36

 출처

https://www.acmicpc.net/problem/10872

Hashing

 문제 설명

APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정의한다. 해시 함수는 무궁무진한 응용 분야를 갖는데, 대표적으로 자료의 저장과 탐색에 쓰인다.

이 문제에서는 여러분이 앞으로 유용하게 쓸 수 있는 해시 함수를 하나 가르쳐주고자 한다. 먼저, 편의상 입력으로 들어오는 문자열에는 영문 소문자(a, b, ..., z)로만 구성되어있다고 가정하자. 영어에는 총 26개의 알파벳이 존재하므로 a에는 1, b에는 2, c에는 3, ..., z에는 26으로 고유한 번호를 부여할 수 있다. 결과적으로 우리는 하나의 문자열을 수열로 변환할 수 있다. 예를 들어서 문자열 "abba"은 수열 1, 2, 2, 1로 나타낼 수 있다.

해시 값을 계산하기 위해서 우리는 문자열 혹은 수열을 하나의 정수로 치환하려고 한다. 간단하게는 수열의 값을 모두 더할 수도 있다. 해시 함수의 정의에서 유한한 범위의 출력을 가져야 한다고 했으니까 적당히 큰 수 M으로 나눠주자. 짜잔! 해시 함수가 완성되었다. 이를 수식으로 표현하면 아래와 같다.

 H=∑i=0l−1aimodM\[H = \sum_{i=0}^{l-1}{a_i} \mod M\] 

해시 함수의 입력으로 들어올 수 있는 문자열의 종류는 무한하지만 출력 범위는 정해져있다. 다들 비둘기 집의 원리에 대해서는 한 번쯤 들어봤을 것이다. 그 원리에 의하면 서로 다른 문자열이더라도 동일한 해시 값을 가질 수 있다. 이를 해시 충돌이라고 하는데, 좋은 해시 함수는 최대한 충돌이 적게 일어나야 한다. 위에서 정의한 해시 함수는 알파벳의 순서만 바꿔도 충돌이 일어나기 때문에 나쁜 해시 함수이다. 그러니까 조금 더 개선해보자.

어떻게 하면 순서가 달라졌을때 출력값도 달라지게 할 수 있을까? 머리를 굴리면 수열의 각 항마다 고유한 계수를 부여하면 된다는 아이디어를 생각해볼 수 있다. 가장 대표적인 방법은 항의 번호에 해당하는 만큼 특정한 숫자를 거듭제곱해서 곱해준 다음 더하는 것이 있다. 이를 수식으로 표현하면 아래와 같다.

 H=∑i=0l−1airimodM\[H = \sum_{i=0}^{l-1}{a_ir^i} \mod M\] 

보통 r과 M은 서로소인 숫자로 정하는 것이 일반적이다. 우리가 직접 정하라고 하면 힘들테니까 r의 값은 26보다 큰 소수인 31로 하고 M의 값은 1234567891(놀랍게도 소수이다!!)로 하자.

이제 여러분이 할 일은 위 식을 통해 주어진 문자열의 해시 값을 계산하는 것이다. 그리고 이 함수는 간단해 보여도 자주 쓰이니까 기억해뒀다가 잘 써먹도록 하자.

 입력

첫 줄에는 문자열의 길이 L이 들어온다. 둘째 줄에는 영문 소문자로만 이루어진 문자열이 들어온다.

입력으로 주어지는 문자열은 모두 알파벳 소문자로만 구성되어 있다.

 출력

문제에서 주어진 해시함수와 입력으로 주어진 문자열을 사용해 계산한 해시 값을 정수로 출력한다.

 Python 코드

def solution(arr):
    return sum(arr) / len(arr)

 C++ 코드

 출처