백준 1002 터렛 java https://www.acmicpc.net/problem/1002
먼저 이해를 위해 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
프로그램을 짜는 과제를 하는 느낌이 드는 문제였다.
switch 문이 쓰고 싶어서 명령어 문자열을 숫자로 매핑 해주는 HashMap을 활용했는데 짜고나니 굳이 귀찮게 풀었다는 느낌이 들긴 함
java는 switch( String) 문법이 된다고한다. 아래는 성능 테스트한 결과
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
스택 문제와 달리 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
단순 스택 문제, 아이디어는 주석에 적었다.
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);
}
터렛 문제를 풀며 많은 도움이 되었다.