온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)
둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.
출력
첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.
풀이
sort를 사용했다.
숫자만을 기준으로 하기위해 lambda를 사용했다
python 코드
# 10814 나이순 정렬
N = int(input())
people = []
for t in range(N):
age, name = input().split()
people.append([int(age),name])
# 숫자만 기준으로 정렬
people.sort(key = lambda people:people[0])
for i in range(N):
print('{} {}'.format(people[i][0],people[i][1]))
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.
여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.
입력
입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.
출력
출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.
# 9012 괄호
T = int(input())
for i in range(T):
test = input()
bracket = []
flag ='YES'
for t in test:
if len(bracket) == 0:
if t == ')':
flag = 'NO'
break
elif t == '(':
bracket.append(t)
else:
if t == '(':
bracket.append(t)
if t == ')' and bracket[-1] == '(':
bracket.pop()
elif t == ')' and bracket[-1] != '(':
flag = 'NO'
break
if len(bracket) > 0:
flag = 'NO'
print(flag)
아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(1, K) < N ≤ 1000)
출력
첫째 줄에 K번째 지워진 수를 출력한다.
풀이
문제에 충실하게 풀었다
모든 정수를 적고, 가장 작은 수의 배수를 지웠다
C++로 먼저 풀려고 했는데 1시간 30분을 쏟았는데 안풀려서 열받아서 python으로 풀기 시작했고 11분만에 풀었다.
화가 나는 것이다.
python 코드
# 2960 에라노스테네스의 체
N, K = map(int,input().split())
arr = []
cnt = 0
ans = 0
for i in range(2, N+1):
arr.append(i)
min_num = arr[0]
while cnt < K:
i = 1
while min_num * i < N + 1:
if min_num * i in arr:
cnt += 1
arr.remove(min_num * i)
if cnt == K:
ans = min_num * i
i += 1
# print(arr)
if len(arr) > 0:
min_num = arr[0]
print(ans)
세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.
정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.
문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.
모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.
정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.
입력
하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다.
입력의 종료조건으로 맨 마지막에 점 하나(".")가 들어온다.
출력
각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.
풀이
스택을 사용하여 풀었다.
리스트를 만들어두고 괄호를 넣고 조건에 맞는 괄호가 들어오면 pop 해줬다.
C++로 먼저 풀어 볼 생각이었지만,
엇... 이거 C++로 입력 어떻게 받지... 멍해져서 그냥 python 으로 먼저 풀었다.
마지막에 배열에 남는 괄호가 없는지도 꼭 파악해줘야한다.
코드
# 4949 균형잡힌 세상
while True:
t = input()
bracket = []
flag = 'yes'
if t == '.':
break
for i in range(len(t)):
if len(bracket) == 0:
if t[i] == ')' or t[i] ==']':
flag = 'no'
break
elif t[i] == '(' or t[i] == '[':
bracket.append(t[i])
else:
if t[i] == '(':
bracket.append(t[i])
if t[i] == '[':
bracket.append(t[i])
if t[i] == ')' and bracket[-1] == '(':
bracket.pop()
elif t[i] == ')' and bracket[-1] != '(':
flag = 'no'
break
elif t[i] == ']' and bracket[-1] == '[':
bracket.pop()
elif t[i] == ']' and bracket[-1] != '[':
flag= 'no'
break
if len(bracket) != 0:
flag = 'no'
print(flag)
알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.
길이가 짧은 것부터
길이가 같으면 사전 순으로
입력
첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.
출력
조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.
풀이
엥 이렇게 쉬워보이는 문제를 전에 왜 못풀었지 내가 그동안 성장한건가 싶었는데 시간초과 냈다.
역시 sort 짱짱이다
아마 전에는 C++로 먼저 시도해서 못풀었던 것 같다
python 코드
# 1181 단어 정렬
import sys
N = int(sys.stdin.readline())
text = []
for i in range(N):
text.append(sys.stdin.readline().strip())
# 중복 제거를 위해 set 사용
set_text = set(text)
text = list(set_text)
text.sort()
text.sort(key=len)
for i in range(len(text)):
print(text[i])
# 아래 코드는 시간 초과 난 코드 또륵 하나하나 비교했다
# for i in range(len(text)):
# for j in range(i,len(text)):
# if len(text[i]) > len(text[j]):
# text[i],text[j] = text[j],text[i]
# # print(text)
# for i in range(len(text)):
# for j in range(i,len(text)):
# if text[i] > text[j] and len(text[i]) == len(text[j]):
# text[i],text[j] = text[j], text[i]
N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.
지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.
지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다.
지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다.
지붕의 가장자리는 땅에 닿아야 한다.
비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.
그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 다각형을 창고 다각형이라고 하자.
그림1 . 기둥과 지붕(굵은 선)의 예
창고 주인은 창고 다각형의 면적이 가장 작은 창고를 만들기를 원한다. 그림 1에서 창고 다각형의 면적은 98 ㎡이고, 이 경우가 가장 작은 창고 다각형이다.
기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.
입력
첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 빈 칸을 사이에 두고 주어진다. L과 H는 둘 다 1 이상 1,000 이하이다.
출력
첫 줄에 창고 다각형의 면적을 나타내는 정수를 출력한다.
풀이
가장 높은 기둥을 기준으로 왼쪽그룹, 높은 그룹, 오른쪽 그룹 3개로 나누어 면적을 구하고 더하는 식으로 진행하였다.
실버 2 인데두 어렵지 않게 풀 수 있었다! (뿌듯)
python 코드
# 2304 창고 다각형
N = int(input())
pillars = []
ans = 0
# 기둥 입력받기
for pillar in range(N):
L,H = map(int,input().split())
pillars.append([L,H])
pillars.sort()
# print(pillars)
#가장 높은 기둥의 높이를 저장해둔다
max_h = 0
for i in pillars:
if i[1] >= max_h:
max_h = i[1]
# print(max_h)
# 왼쪽부터 지금 기둥 위치보다 높은 기둥을 찾을 때 마다 기둥과 거리 값을 갱신
# ans 에 현재까지의 값을 더해준다
h = pillars[0][1]
w = pillars[0][0]
for i in pillars:
if i[1] > h and h != max_h:
ans += h * (i[0] - w)
h = i[1]
w = i[0]
# 가장 높은 기둥을 만나면 반복문을 종료
elif h == max_h:
break
# print(ans)
# 오른쪽부터 계산한다
h = pillars[N-1][1]
w = pillars[N-1][0]
for i in range(N-1,-1,-1):
if pillars[i][1] > h and h != max_h:
ans += h * (w - pillars[i][0])
h = pillars[i][1]
w = pillars[i][0]
# 가장 높은 기둥을 만나면 반복문 종료
elif h == max_h:
break
# print(ans)
# 가장 높은 기둥이 여러개 있을 수 있으니 가장 높은 기둥과 기둥 사이의 넓이를 구한다
highest =[]
for i in pillars:
if i[1] == max_h:
highest.append(i[0])
ans += (max(highest) - min(highest) + 1) * max_h
print(ans)
C++코드
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
int N;
cin >> N;
vector<pair<int, int>>pillars;
int ans = 0;
for (int i = 0; i < N; i++) {
int N, H;
cin >> N >> H;
pillars.push_back(make_pair(N, H));
}
sort(pillars.begin(), pillars.end());
int max_h = 0;
for (int i = 0; i < N; i++) {
if (pillars[i].second >= max_h) {
max_h = pillars[i].second;
}
}
int h, w;
h = pillars[0].second;
w = pillars[0].first;
for (int i = 0; i < N; i++) {
if (pillars[i].second > h && h != max_h) {
ans = ans + (h * (pillars[i].first - w));
h = pillars[i].second;
w = pillars[i].first;
}
else if (h == max_h) {
break;
}
}
h = pillars[N - 1].second;
w = pillars[N - 1].first;
for (int i = N - 1; i > 0; i--) {
if (pillars[i].second > h && h != max_h) {
ans = ans + (h * (w - pillars[i].first));
h = pillars[i].second;
w = pillars[i].first;
}
else if (h == max_h) {
break;
}
}
vector<int>highest;
for (int i = 0; i < N; i++) {
if (pillars[i].second == max_h) {
highest.push_back(pillars[i].first);
}
}
int max = *max_element(highest.begin(), highest.end());
int min = *min_element(highest.begin(), highest.end());
ans = ans + (max - min + 1) * max_h;
cout << ans;
}
python 으로 작성한 코드를 그대로 C++로 옮겼다.
vector에서 pair를 사용하는 부분이나 vector의 sort, 그리고 min, max 값 구하는 부분은 검색해서 해결했다.
python 코드를 작성 후 C++로 옮기는 작업은 어느정도 할 수 있을 것 같으나 처음부터 C++로 사고하는건 아직 힘들다... 내일부터는 난이도가 좀 낮아도 처음부터 C++로 풀어봐야겠다.
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.
셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다
출력
첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.
풀이
in을 사용해서 풀었을 때 시간 초과가 나와서 검색 후 이진 탐색을 통해 문제를 풀었다
틀린python코드
# 10815 숫자 카드
import sys
N = int(sys.stdin.readline())
mycard = list(map(int,sys.stdin.readline().split()))
M = int(sys.stdin.readline())
card = list(map(int,sys.stdin.readline().split()))
mycard.sort()
visited = [0] * M
for i in range(M):
if card[i] in mycard:
visited[i] = 1
print(*visited)
답은 쉽게 나오지만 시간 초과,,,
맞은python코드
# 10815 숫자 카드
import sys
N = int(sys.stdin.readline())
mycard = list(map(int,sys.stdin.readline().split()))
M = int(sys.stdin.readline())
card = list(map(int,sys.stdin.readline().split()))
mycard.sort()
# 출력할 배열
visited = [0] * M
for i in range(M):
start = 0
end = N - 1
# print(visited)
# start의 값이 end 와 같거나 작은 동안 실행
# start가 end 보다 커지면 반복문 실행 중지
while start <= end:
mid = (start + end) // 2
if card[i] == mycard[mid]:
visited[i] = 1
break
# 값이 작은 경우 처음 부터 mid 앞숫자까지 탐색하므로 mid -1 해준다
# [0 0 0 mid 0 0 0]
elif card[i] < mycard[mid]:
end = mid - 1
else:
start = mid + 1
print(*visited)
C++ 코드
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
int N;
cin >> N;
vector<int>mycard(N,0);
for (int i = 0; i < N; i++) {
cin >> mycard[i];
}
int M;
cin >> M;
vector<int>card(M,0);
for (int i = 0; i < M; i++) {
cin >> card[i];
}
vector<int>visited(M,0);
sort(mycard.begin(), mycard.end());
for (int i = 0; i < M; i++) {
int start = 0;
int end = N-1;
while (start <= end) {
int mid = (start + end) / 2;
if (card[i] == mycard[mid]) {
visited[i] = 1;
break;
}
else if (card[i] < mycard[mid]) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
}
for (int i = 0; i < M; i++) {
cout << visited[i] << ' ';
}
}
C++ 너무 오랜만이라 작성하면서 vector나 sort 쓰는걸 다 잊어가지구,,, python 코드 그대로 보면서 검색해가면서 작성해본 코드
준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.
지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19)
우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다.
예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 되면 16 16 16이 아니라 1 16 16이 된다. 이유는 1 ≤ E ≤ 15 라서 범위를 넘어가기 때문이다.
E, S, M이 주어졌고, 1년이 준규가 사는 나라에서 1 1 1일때, 준규가 사는 나라에서 E S M이 우리가 알고 있는 연도로 몇 년인지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 세 수 E, S, M이 주어진다. 문제에 나와있는 범위를 지키는 입력만 주어진다.
출력
첫째 줄에 E S M으로 표시되는 가장 빠른 연도를 출력한다. 1 1 1은 항상 1이기 때문에, 정답이 음수가 나오는 경우는 없다.
풀이
당연히 시간초과가 나오지 않을까 싶을 정도로 정직하게 부르트포스로 풀었다
e, s, m에 반복문으로 계속 1씩 더해주고 범위를 넘기면 1부터 다시 1씩 더해준 다음 입력된 값과 같아질 때 카운트를 출력하도록 하였다.
코드
# 1476 날짜 계산
# 입력받음
E,S,M = map(int,input().split())
# 더해질 함수 초기화
e = s = m = 0
# 값
cnt = 0
# 계속 반복
while True:
e += 1
# 15 넘어가면 1로 돌아옴
if e > 15:
e = 1
s += 1
# 28 넘어가면 1로 돌아옴
if s > 28:
s = 1
m += 1
# 19 넘어가면 1로 돌아옴
if m > 19:
m = 1
cnt += 1
# 입력값과 같을 때 반복문 탈출
if e == E and s == S and m == M:
break
print(cnt)
N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.
출력
첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.
풀이
부르트보스로 풀이를 하고자 하였다.
틀린코드
다음과 같이 풀면 (내가 사용한 테스트케이스 내에서) 모든 순열이 출력이 되지만 사전순으로 출력이 되지 않아서 고생하다가 다른 사람의 풀이를 참고하여 풀었다
f arr(n):
global ans
if n == N:
print(*visited)
else:
for i in range(N):
if visited[i] == 0:
visited[i] = n+1
arr(n+1)
visited[i] = 0
N = int(input())
visited = [0] * N
ans = []
arr(0)
맞은코드
def arr(depth):
global ans
if depth == n:
print(*visited)
else:
for i in range(n):
if i + 1 in visited:
continue
visited[depth] = i + 1
arr(depth + 1)
visited[depth] = 0
n = int(input())
visited = [0] * n
arr(0)
세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.
입력
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.
출력
첫째 줄에 정답을 출력한다.
풀이
가장 작은 값을 가지기 위해서는 가장 큰 값을 빼야하기 때문에 +를 묶어서 한번에 -해준다.
정수로 변환하기 위해 try except문을 사용하였다
코드
# 1541 잃어버린 괄호
# '-'를 기준으로 나누어 입력받는다
num = list(map(str,input().split('-')))
# print(num)
# 최종적으로 빼지는 수들이 들어올 리스트
arr = []
for i in range(len(num)):
# 만약 list 안에 수가 정수로 변환이 가능하다면 arr 리스트로 들어오고
# +를 포함한 문자라 변환이 되지 않을 경우 except로 이동한다
try:
arr.append(int(num[i]))
except:
add_ans = 0
add = []
add += num[i].split('+')
# +를 기점으로 수를 더해준다
for j in add:
add_ans += int(j)
# print(j)
# 더해진 수를 arr 리스트로 보낸다
arr.append(int(add_ans))
# 최종적으로 arr 리스트에 있는 수들을 모두 빼준다.
ans = arr[0]
for i in range(1,len(arr)):
ans -= arr[i]
print(ans)
