소소한필통

Problem https://programmers.co.kr/learn/courses/30/lessons/42888 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr About Problem 문제 1. 사람들이 들어왔는지 나갔는지 닉네임을 변경했는지 구분하기 2. 들어왔을때, "[닉네임]님이 들어왔습니다." 나갔을때, "[닉네임]님이 나갔습니다." 순서대로 리스트에 넣기 3. 닉네임 변경 - 채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다. 채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다. 채팅..

Problem https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net About Problem 두 용액을 합하여 0에 가까운 수를 만드는 문제이다. input이 2이상 100,000 이므로 완전탐색은 할 수 없다. 정렬을 통해서 조건을 통해서 양끝을 줄여가면 빅오 N으로 값을 찾을 수 있다. 이 방식이 바로 two pointer다. 이 문제와 같이 two pointer는 두 값을 비교해서 특정 조건을 찾을 때 자주 쓰..

Problem https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net About Problem 문제 그대로 deque를 구현을 하면된다. python은 collection 라이브러리에 deque모듈이 있기 때문에 구현이 쉽다. 시간 계산은 N이 100000이기 때문에 시간은 여유롭다. Code deque모듈의 함수를 쓰면 되기 때문에 주석을 보고 순서와 push만 판단하면 문제는 쉽다. from sys import stdin from ..

Problem https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net About Problem 문제에서 첫번째로 list의 수 N이 주어지고 두번째 줄에 list가 주어지고 세번째에 목표값이 주어진다. 리스트에서 두 수합이 tartgetnum인 것을 찾아야한다. 완탐으로 할 경우 100000 * 99999 이므로 10억번을 찾아야 하므로 제한시간이 1초이므로 timeover가 될것이다. 그러므러 ..

Problem https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net About Problem input에서 N이 최대 100000 이고 M이 최대 100000이므로 결국 Output을 0 또는 1로 판단하기 위해서는 M에 들어 있는 숫자를 다 찾아야한다. 하지만 둘다 최대일 때는 100억번을 반복해야 하므로 완전 탐색으로 찾을 수 없다. 그래서 정렬을 하고 빅오를 줄 일 수있는 이분탐색을 통해서 ind..