개발/☕ JAVA
🎃 코딩 테스트 스터디 2주차
정소은
2024. 8. 9. 15:30
이번주 큰 주제는 1. 자료구조 2. 탐색과 정렬
# 10828 - 스택
https://www.acmicpc.net/problem/10828
Python
import sys
input = sys.stdin.readline
stack = []
N = int(input())
for i in range(N):
command = list(map(str, input().split()))
if command[0] == "push":
command[1] = int(command[1])
stack.append(command[1])
else:
if command[0] == "pop":
if stack:
print(stack.pop())
else:
print(-1)
elif command[0] == "size":
print(len(stack))
elif command[0] == "empty":
if stack:
print(0)
else:
print(1)
elif command[0] == "top":
if stack:
a = stack.pop()
print(a)
stack.append(a)
else:
print(-1)
Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
ArrayList<Integer> stack = new ArrayList<>();
Integer N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String cmd = st.nextToken();
if (cmd.equals("push")) {
Integer num = Integer.parseInt(st.nextToken());
stack.add(num);
} else if (cmd.equals("pop")){
if (!stack.isEmpty()){
System.out.println(stack.get(stack.size()-1));
stack.remove(stack.size()-1);
} else
System.out.println(-1);
} else if (cmd.equals("size")){
System.out.println(stack.size());
} else if (cmd.equals("empty")){
if(stack.isEmpty())
System.out.println(1);
else
System.out.println(0);
} else {
if(stack.isEmpty())
System.out.println(-1);
else
System.out.println(stack.get(stack.size()-1));
}
}
}
}
# 10845 - 큐
https://www.acmicpc.net/problem/10845
Python
import sys
input = sys.stdin.readline
n = int(input())
q = deque()
for i in range(n):
cmd = list(map(str, input().split()))
if cmd[0] == "push":
q.append(cmd[1])
elif cmd[0] == "pop":
if len(q) == 0:
print(-1)
else:
print(q.popleft())
elif cmd[0] == "size":
print(len(q))
elif cmd[0] == "empty":
if len(q) == 0:
print(1)
else:
print(0)
elif cmd[0] == "front":
if len(q) == 0:
print(-1)
else:
print(q[0])
else:
if length == 0:
print(-1)
else:
print(q[-1])
# 10866 - 덱
Python
from collections import deque
import sys
d = deque()
n = int(input())
for i in range(n):
cmd = sys.stdin.readline().split()
if cmd[0] == "push_front":
d.appendleft(cmd[1])
elif cmd[0] == "push_back":
d.append(cmd[1])
elif cmd[0] == "pop_front":
if d:
print(d.popleft())
else:
print(-1)
elif cmd[0] == "pop_back":
if d:
print(d.pop())
else:
print(-1)
elif cmd[0] == "size":
print(len(d))
elif cmd[0] == "empty":
if d:
print(0)
else:
print(1)
elif cmd[0] == "front":
if d:
print(d[0])
else:
print(-1)
elif cmd[0] == "back":
if d:
print(d[-1])
else:
print(-1)
💡 Python에서는 스택은 list로, 큐와 덱은 deque 라이브러리를 활용해서 구현하는 것이 좋다
스택은 하나의 통로에서 데이터의 삽입과 삭제를 행하고
이는 append()와 pop()을 이용하면 되며 각각의 시간복잡도가 O(1)이다
반면에 큐와 덱은 두개의 통로에서 데이터의 삽입과 삭제를 행하고
이를 list로 구현할 시 pop(0), pop(-1) 등을 사용해야 하는데 이는 pop()과 달리 O(n)의 시간복잡도를 갖는다
하지만 큐와 덱을 deque 라이브러리의 popleft(), appendleft()를 이용해서 구현하게 되면 O(1)의 시간복잡도를 갖는다
# 1406 - 에디터
https://www.acmicpc.net/problem/1406
Python
import sys
st1 = list(sys.stdin.readline().rstrip())
st2 = []
for _ in range(int(sys.stdin.readline())):
command = list(sys.stdin.readline().split())
if command[0] == 'L':
if st1:
st2.append(st1.pop())
elif command[0] == 'D':
if st2:
st1.append(st2.pop())
elif command[0] == 'B':
if st1:
st1.pop()
else:
st1.append(command[1])
st1.extend(reversed(st2))
print(''.join(st1))이건 사실.. 계속 안 풀려서 남의 코드 긁어왔다..
커서를 기준으로 왼쪽 문자들은 st1에, 오른쪽 문자들은 st2에, 스택을 두개로 나눠서 푸는 방식이었다.. 진짜 똑똑한 방법..
커서를 왼쪽으로 옮기면 st1에서 pop하고 st2에 append해주고
커서를 오른쪽으로 옮기면 st2에서 pop하고 st1에 append해준다
커서 왼쪽 거를 삭제하고 싶으면 st1에서 pop
커서 왼쪽에 문자 추가하고 싶으면 st1에 append해준다
# 1026 - 보물
https://www.acmicpc.net/problem/1026
Python
N = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
a.sort()
b.sort()
b.reverse()
S = 0
for i in range(N):
S+=a[i]*b[i]
print(S)
# 1181 - 단어 정렬하기
https://www.acmicpc.net/problem/1181
Python
N = int(input())
wordList = []
for i in range (N):
wordList.append(input())
wordList = set(wordList)
wordList = list(wordList)
wordList.sort()
for j in range(len(wordList)):
for k in range(len(wordList)-j-1):
if len(wordList[k]) > len(wordList[k+1]):
wordList[k], wordList[k+1] = wordList[k+1], wordList[k]
for a in wordList:
print(a)
# 11650 - 좌표 정렬하기
https://www.acmicpc.net/problem/11650
Python
import sys
input = sys.stdin.readline
n = int(input())
num = []
for i in range(n):
a, b = map(int, input().split())
num.append((a, b))
num.sort()
for i in range(n):
for j in range(2):
print(num[i][j], end=' ')
print()
# 11651 - 좌표 정렬하기2
https://www.acmicpc.net/problem/11651
Python
import sys
input = sys.stdin.readline
n = int(input())
num = []
for i in range(n):
x, y = map(int, input().split())
num.append((y, x))
num.sort()
for i in range(n):
for j in range(1, -1, -1):
print(num[i][j], end=' ')
print()
# 10867 - 중복 빼고 정렬하기
https://www.acmicpc.net/problem/10867
Python
import sys
input = sys.stdin.readline
n = int(input())
num = list(map(int, input().split()))
num.sort()
num = set(num)
num = list(num)
for i in range(len(num)):
print(num[i], end = " ")
위 문제들은 Python 모듈을 활용해서 쉽게 풀이 가능하다
#10816 - 숫자 카드2
https://www.acmicpc.net/problem/10816
import sys
input = sys.stdin.readline
n = int(input())
nums = list(map(int, input().split()))
m = int(input())
check = list(map(int, input().split()))
count = {}
for num in nums:
if num in count:
count[num] += 1
else:
count[num] = 1
for num in check:
result = count.get(num)
if result == None:
print(0, end = " ")
else:
print(result, end = " ")
처음에는 python의 count를 사용해야 하나? 싶었는데
count의 시간복잡도가 O(n)이기 때문에 시간복잡도가 초과날 거 같아서 다른 방법을 고민해봤다
그래서 애초에 각 숫자마다 방을 만들고 num을 돌면서 개수를 늘려줘야겠다 싶었다
자료구조를 고민했었는데 사실 처음에는 리스트를 쓰다가 index 에러가 너무 많이 나서 딕셔너리로 구현했다