알파벳 소문자로 이루어진 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)
인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.
사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1= 3, P2= 1, P3= 4, P4= 3, P5= 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.
줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.
줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi≤ 1,000)
출력
첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.
풀이
오름차순 정렬 후 계산한다
코드
# 11399 ATM
n = int(input())
arr = list(map(int,input().split()))
ans = 0
# 배열을 오름차순으로 정렬한 후 더하주면 최소값이 나온다
arr.sort()
# 개인이 기다리는 시간을 저장할 임시변수 temp
temp = 0
# 앞에서부터 대기 시간을 temp에 더한 후 ans에 temp값을 더한다
for i in arr:
temp += i
ans += temp
print(ans)
평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다.
매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대학교가 자신과 맞는가에 대한 고민을 항상 해왔다.
중앙대학교와 자신의 길이 맞지 않다고 생각한 JH 교수님은 결국 중앙대학교를 떠나기로 결정하였다.
떠나기 전까지도 제자들을 생각하셨던 JH 교수님은 재귀함수가 무엇인지 물어보는 학생들을 위한 작은 선물로 자동 응답 챗봇을 준비하기로 했다.
JH 교수님이 만들 챗봇의 응답을 출력하는 프로그램을 만들어보자.
입력
교수님이 출력을 원하는 재귀 횟수 N(1 ≤ N ≤ 50)이 주어진다.
출력
출력 예시를 보고 재귀 횟수에 따른 챗봇의 응답을 출력한다.
풀이
재귀를 풀 수 있는가 하는 문제
'____'를 for를 사용해서 작성하니 코드가 엄청 길어졌다
'____'반복을 위해 line수를 재귀할 때 함께 넘겨주도록 하였다
코드
#17478 재귀함수가 뭔가요?
def recursive(m,line):
if m == 0:
for i in range(line):
print('____', end="")
print('\"재귀함수가 뭔가요?\"')
for i in range(line):
print('____', end="")
print('\"재귀함수는 자기 자신을 호출하는 함수라네\"')
for i in range(line):
print('____', end="")
print('라고 답변하였지.')
return
for i in range(line):
print('____',end="")
print('\"재귀함수가 뭔가요?\"')
for i in range(line):
print('____',end="")
print('\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.')
for i in range(line):
print('____',end="")
print('마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.')
for i in range(line):
print('____',end="")
print('그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"')
recursive(m - 1,line + 1)
for i in range(line):
print('____',end="")
print('라고 답변하였지.')
n = int(input())
print('어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.')
recursive(n,0)
