[항해99][선택 온보딩-3] 3일차 문제풀이
백준 1002 터렛 java https://www.acmicpc.net/problem/1002
1002번: 터렛
각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 $-1$ 출력한다.
www.acmicpc.net
먼저 이해를 위해 2차원 그래프에 예제 1의 첫번째 케이스의 두 원을 그려봤다.
x1=0
y1=0
r1=13
x2=40
y2=0
r2=37
위의 경우를 그려보면서 두 원의 접점의 개수를 구하면 되는 수학문제니까 중학수학 개념으로 풀 수 있겠다 싶어 가볍게 풀어봤는데 예제는 통과하나 25%에서 실패가 떴다..
[실패한 코드]
static void input(){
int caseNum = scan.nextInt();
for(int z = 0; z < caseNum; z++){
// 문제 조건 정리
int x1 = scan.nextInt();
int y1 = scan.nextInt();
int r1 = scan.nextInt();
int x2 = scan.nextInt();
int y2 = scan.nextInt();
int r2 = scan.nextInt();
// 문제 이해를 위해 그림을 그려보니까
// 두 원이 몇개의 점에서 만나는지를 물어보는 것이다.
// 두 원의 중심 사이의 거리가 중요
double d_CenterOfCircle = Math.pow((x1-x2) * (x1-x2) + (y1-y2) * (y1-y2), 0.5);
// 문제에서 두 원의 접점의 개수가 무한대일수도 있다는 힌트가 있다. 예외 처리
if(d_CenterOfCircle == 0){
// 만약 두 원의 중심이 같다면,
if(r1!=r2)
sb.append(0);
else if(r1==r2)
sb.append(-1); // 무한
}
else if(d_CenterOfCircle < Math.abs(r2-r1)) {
// 두 반지름의 차보다 두 원의 중심사이 거리가 짧은 경우 만나지 않는 포함관계
sb.append(0);
}
else{
//두 원의 중심 사이의 거리가 두 원의 반지름 합보다 크므로 안만남
if(d_CenterOfCircle > r1+r2)
sb.append(0);
// 같으면 두 원이 한점에서 접한다.
if(d_CenterOfCircle == r1+r2)
sb.append(1);
// 두 원의 중심사이 거리가 더 작으므로 두점에서 접한다
if(d_CenterOfCircle < r1+r2)
sb.append(2);
}
//테스트케이스간 줄넘김
sb.append('\\n');
}
print();
}
놓친 조건이 있으리라는 생각에 초심으로 돌아가서 두 원이 평면에 존재하는 모든 경우의 수를 파악해보니까
위의 풀이를 풀 때는 두 원이 서로 포함관계에 있을 때를 놓쳤었다.
((d_CenterOfCircle : 두 원의 중심 사이의 거리, Math.abs(r_2, r_1) 두 원의 반지름 길이의 차이))
위 사진이 내가 놓친 상황으로, 계산식도 쓰여있다.
아래는 나머지 가능한 케이스들.
+ 나의 풀이에서 하나 더 잘못된 점을 찾았다. 위의 풀이의 첫 if문에서
d_CenterOfCircle ==0 일 때, 즉 두 원의 중심이 같을 때, 반지름의 길이가 같은지 아닌지 검사하여 결과를 내는 부분이 있었는데,
// 문제에서 두 원의 접점의 개수가 무한대일수도 있다는 힌트가 있다. 예외 처리
if(d_CenterOfCircle == 0){
// 만약 두 원의 중심이 같다면,
if(r1!=r2)
sb.append(0);
else if(r1==r2)
sb.append(-1); // 무한
}
위 사진에서 볼 수 있듯, 두 원의 중심이 같든 같지 않든 그냥 한 원이 다른 원을 포함하고 있으면서 내접하지 않는 관계임을 깨달을 수 있었다.
따라서 두 원의 중심이 일치하는지, 일치하지 않는지로 이원화하기에는 깔끔하게 딱 떨어지는 조건이 아니였고, 오히려 하나의 케이스에 대해서 두번 검사해야하는 어려움이 생기므로, 잘못 쓴 코드라는 생각이 들었다.
결과적으로 케이스 하나하나 단위로 처리하는 것이 더 깔끔했다. 앞으로 조건이 복잡하고 케이스들을 분리할 조건이 이래저래 복잡하게 걸쳐있는 경우의 if else 문 사용을 한번 더 고민하고 해야겠다.
백준 10828 스택 java https://www.acmicpc.net/problem/10828
10828번: 스택
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net
프로그램을 짜는 과제를 하는 느낌이 드는 문제였다.
switch 문이 쓰고 싶어서 명령어 문자열을 숫자로 매핑 해주는 HashMap을 활용했는데 짜고나니 굳이 귀찮게 풀었다는 느낌이 들긴 함
java는 switch( String) 문법이 된다고한다. 아래는 성능 테스트한 결과
[java] switch string, switch int switch문 성능 비교
문제의 발단 : 내가 원래 쓰던 c++은 string에 대하여 switch문을 사용할 수가 없었다. switch() 안에 int 형의 변수만 들어갈 수 있다 보니까 여러 String 조건에 대하여 if else 지옥을 만들지 않으려면 Map
paralleldev.tistory.com
static void input() throws Exception {
int operationCount = scan.nextInt();
Stack<Integer> s = new Stack<>();
HashMap<String, Integer> operationMapper = Map.of(
"push", 1,
"empty", 2,
"size", 3,
"top", 4,
"pop", 5
);
for(int i = 0 ; i < operationCount; i++){
String[] operation = scan.nextLine().split(" ");
switch(operationMapper.get(operation[0])){
case 1:
s.add(Integer.parseInt(operation[1]));
break;
case 2:
sb.append(s.isEmpty() ? 1 : 0).append('\\n');
break;
case 3:
sb.append(s.size()).append('\\n');
break;
case 4:
if(s.isEmpty())
sb.append(-1).append('\\n');
else
sb.append(s.peek()).append('\\n');
break;
case 5:
if(s.isEmpty())
sb.append(-1).append('\\n');
else
sb.append(s.pop()).append('\\n');
break;
}
}
print();
}
백준 18258 큐2 java https://www.acmicpc.net/problem/18258
18258번: 큐 2
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net
스택 문제와 달리 if, else if 문으로 풀어봤는데 아까 switch, Integer Mapper 로 푼거보다 더 더러운듯..
스택 문제나 큐2 문제나 요구사항 자체가 지저분해서 요구사항마다 메소드로만드는거 아니면 그냥 지저분하긴하겠다.
데크 자료구조는 단방향으로만 add, pop이 가능한 큐와 달리 양방향으로 add, pop이 가능한 자료구조로, 다른 고난도 문제에서는 필수로 사용해야만 풀 수 있는 경우도 있지만, 큐2 문제에서는 필수는 아닌 것 같아서 그냥 최근에 add한 숫자를 한개만 저장하고 있도록 하여 구현했다. ( 가장 뒤에있는 숫자는 숫자를 새로 add하지 않는한 변하지 않으므로)
static void input() throws Exception {
int operationCount = scan.nextInt();
// 간단한 데크 자료구조 문제인데,
// 앞뒤로 add, pop, peek이 가능한 데크로 풀면 너무 쉬우니까 큐로 풀면서
// 4바이트짜리 캐시 메모리 느낌으로 최근에 push한 수를 들고 있다가 back 연산할떄 쓰자
Queue<Integer> q = new LinkedList<>();
int recentPushedNumber = -1;
for(int z = 0 ; z < operationCount; z++) {
String[] operation = scan.nextLine().split(" ");
if (operation[0].equals("push")) {
recentPushedNumber = Integer.parseInt(operation[1]);
q.add(recentPushedNumber);
}
else if (operation[0].equals("pop")) {
if (q.isEmpty())
sb.append(-1).append('\\n');
else
sb.append(q.poll()).append('\\n');
}
else if (operation[0].equals("size"))
sb.append(q.size()).append('\\n');
else if (operation[0].equals("empty"))
sb.append(q.isEmpty() ? 1 : 0).append('\\n');
else if (operation[0].equals("front")) {
if (q.isEmpty())
sb.append(-1).append('\\n');
else
sb.append(q.peek()).append('\\n');
}
else if (operation[0].equals("back")) {
if (q.isEmpty())
sb.append(-1).append('\\n');
else
sb.append(recentPushedNumber).append('\\n');
}
}
print();
}
백준 10773 제로 java https://www.acmicpc.net/problem/10773
10773번: 제로
첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경
www.acmicpc.net
단순 스택 문제, 아이디어는 주석에 적었다.
static void input() throws Exception {
int k = scan.nextInt();
// 총합을 구해야하므로 받은 수를 저장하고 있어야 한다.
// 가장 최근에 쓴 수를 지우는데, 지우는 명령이 연속될 수 있다.
// 스택 자료구조
Stack<Integer> s = new Stack<>();
for(int z = 0 ; z < k ; z ++){
int num = scan.nextInt();
if(num==0)
s.pop();
else
s.add(num);
}
int sum = 0;
while(!s.isEmpty())
sum+=s.pop();
System.out.println(sum);
}
터렛 문제를 풀며 많은 도움이 되었다.