터렛 ) P 1002
조규현과 백승환은 터렛에 근무하는 직원이다. 하지만 워낙 존재감이 없어서 인구수는 차지하지 않는다. 다음은 조규현과 백승환의 사진이다.
이석원은 조규현과 백승환에게 상대편 마린(류재명)의 위치를 계산하라는 명령을 내렸다. 조규현과 백승환은 각각 자신의 터렛 위치에서 현재 적까지의 거리를 계산했다.
조규현의 좌표 와 백승환의 좌표 가 주어지고, 조규현이 계산한 류재명과의 거리 과 백승환이 계산한 류재명과의 거리 가 주어졌을 때, 류재명이 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성하시오.
첫째 줄에 테스트 케이스의 개수 가 주어진다. 각 테스트 케이스는 다음과 같이 이루어져 있다.
한 줄에 공백으로 구분 된 여섯 정수 , , , , , 가 주어진다.
T : 테스트 케이스 갯수
x1, y1 : A의 위치
x2, y2 : B의 위치
r1 : A에서의 거리
r2 : B에서의 거리
A의 위치에서 r1만큼 떨어진 위치의 좌표들의 리스트를 구한다. List 1
B의 위치에서 r2만큼 떨어진 위치의 좌표들의 리스트를 구한다. List 2
for List 1의 길이만큼 반복
List 1[0]부터 List 2와 비교
만약 같다면 count++
최종 count 출력
x1+r1, y1
x1+r1-1, y1+1
...
x1, y1+r1
각 정점 (x1, y1-r1),(x1-r, y1), (x1+r, y1), (x1, y1+r)
로 했었으나 잘 되지 않아서 찾아보니 두 점 간의 거리를 구하고, 원을 그린다고 생각을 하여
r1+r2와 비교해서 distance == r1+r2-> 접하니까 1개 distance<r1+r2 2개, distance > r1+r2 0개
액셀로 그려가면서 생각을 해보았다.
package thirdday;
import java.util.Scanner;
public class P1002 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int T = scanner.nextInt();
for(int i =0;i<T;i++){
int x1 = scanner.nextInt();
int y1 = scanner.nextInt();
int r1 = scanner.nextInt();
int x2 = scanner.nextInt();
int y2 = scanner.nextInt();
int r2 = scanner.nextInt();
double distance = Math.sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
int r_big,r_small;
if(r1>r2){
r_big = r1;
r_small = r2;
}else{
r_big = r2;
r_small = r1;
}
if (distance==0){
if(r1==r2){
System.out.println("-1"); // 두 원이 일치함
}else{
System.out.println("0"); // 두 원이 만나지 않음
}
}else {
if (r1+r2 < distance){ // 두 원이 만나지 않는 경우
System.out.println("0");
}else if (distance == r1+r2){ // 두 원이 외접하는 경우
System.out.println("1");
}else if (r_big - r_small < distance && distance<r1+r2 ){ //두 원이 만나는 경우
System.out.println("2");
}else if (distance==r_big - r_small){ // 두 원이 내접하는 경우
System.out.println("1");
}
else {
System.out.println("0");
}
}
}
}
}
제로) P10773
나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.
재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.
재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.
재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!
첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)
이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.
정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.
package thirdday;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class P10773 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int K = Integer.parseInt(bf.readLine());
ArrayList<Integer> X = new ArrayList<Integer>();
int count = 0; //현재 들어있는 정수의 갯수
for(int i = 0;i<K;i++){
int num = Integer.parseInt(bf.readLine());
if(num == 0){
X.remove(count-1);
count--;
}else{
X.add(num);
count++;
}
}
int result = 0;
for(int j = 0;j<count;j++){
result = result+X.get(j);
}
System.out.println(result);
}
}
스택) 10828
정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 다섯 가지이다.
- push X: 정수 X를 스택에 넣는 연산이다.
- pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 스택에 들어있는 정수의 개수를 출력한다.
- empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
- top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
package thirdday;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class P10828 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(bf.readLine());
ArrayList<Integer> X = new ArrayList<Integer>();
int count=0;
for(int i=0;i<T;i++){
String s = bf.readLine();
StringTokenizer st = new StringTokenizer(s); //StringTokenizer인자값에 입력 문자열 넣음
String Q = st.nextToken();
//System.out.println(Q+num);
if( Q.equals("push")){
int num = Integer.parseInt(st.nextToken());
//int num = bf.read();
X.add(num);
count++;
}else if(Q.equals("pop")){
if(count !=0) {
int result = X.get(count-1);
X.remove(count-1);
count--;
System.out.println(result);
}else {
System.out.println("-1");
}
}else if(Q.equals("size")){
System.out.println(count);
}else if(Q.equals("empty")){
if(count==0){
System.out.println("1");
}else {
System.out.println("0");
}
}else if(Q.equals("top")){
if(count==0){
System.out.println("-1");
}else {
System.out.println(X.get(count-1));
}
}else{
System.out.println("잘못 입력하셨습니다.");
}
}
}
}
큐2) P 18258
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여섯 가지이다.
- push X: 정수 X를 큐에 넣는 연산이다.
- pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 큐에 들어있는 정수의 개수를 출력한다.
- empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
- front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
위의 10828 문제의 답을 응용하면 쉬울 줄 알았다.
초기버전
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 bf = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(bf.readLine());
ArrayList<Integer> X = new ArrayList<Integer>();
int count=0;
for(int i=0;i<T;i++){
String s = bf.readLine();
StringTokenizer st = new StringTokenizer(s); //StringTokenizer인자값에 입력 문자열 넣음
String Q = st.nextToken();
//System.out.println(Q+num);
if( Q.equals("push")){
int num = Integer.parseInt(st.nextToken());
//int num = bf.read();
X.add(num);
count++;
}else if(Q.equals("pop")){
if(count !=0) {
int result = X.get(count-1);
X.remove(count-1);
count--;
System.out.println(result);
}else {
System.out.println("-1");
}
}else if(Q.equals("size")){
System.out.println(count);
}else if(Q.equals("empty")){
if(count==0){
System.out.println("1");
}else {
System.out.println("0");
}
}else if(Q.equals("back")){
if(count==0){
System.out.println("-1");
}else {
System.out.println(X.get(count-1));
}
}else if(Q.equals("front")){
if(count==0){
System.out.println("-1");
}else{
System.out.println(X.get(0));
}
}else{
System.out.println("잘못 입력하셨습니다.");
}
}
}
public class Que{
}
}위의 버전에서 계속 시간초과가 발생하여
좀 더 세련되게 Class Que를 만들어서 그 안에 기능들을 구현하고 출력 방식도 변경하고 ArrayList를 사용하지 않는 버전으로 바꿔 보았다.
//출력방식도 변경
//ArrayList 대신 그냥 int[] 사용
import java.io.*;
import java.util.StringTokenizer;
public class asd {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(bf.readLine());
Que Qe = new Que(T);
for(int i=0;i<T;i++){
String s = bf.readLine();
StringTokenizer st = new StringTokenizer(s); //StringTokenizer인자값에 입력 문자열 넣음
String Q = st.nextToken();
switch(Q){
case "push": int num = Integer.parseInt(st.nextToken()); Qe.push(num); break;
case "pop": Qe.pop(); break;
case "size": Qe.size();break;
case "empty": Qe.empty();break;
case "back": Qe.back();break;
case "front": Qe.front();break;
default: System.out.println("잘못 입력하셨습니다.");
}
}
}
public static class Que{
int[] X;
int count=0;
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); //할당된 버퍼에 값 넣어주기
public Que(int num){
X = new int[num];
}
void push(int N){
X[count]=N;
count++;
}
void pop() throws IOException {
if(count !=0) {
bw.write(X[count-1]+"\n"); bw.flush();
count--;
}else {
bw.write("-1\n"); bw.flush();
}
}
void size() throws IOException {
bw.write(count+"\n"); bw.flush();
}
void empty() throws IOException {
if(count==0){
bw.write("1\n"); bw.flush();
}else {
bw.write("0\n"); bw.flush();
}
}
void front() throws IOException {
if(count==0){
bw.write("-1\n"); bw.flush();
}else{
bw.write(Integer.toString((X[0]))+"\n"); bw.flush();
}
}
void back() throws IOException {
if(count==0){
bw.write("-1\n"); bw.flush();
}else {
bw.write(Integer.toString((X[count-1]))+"\n"); bw.flush();
}
}
}
}
한 번에 묶어서 마지막에 bw.flush()를 하면 속도는 매우 빨라지나 한 줄 입력 한 줄 출력이라는 정답 방식 때문에 사용할 수 없었다.
추후에 다시 다듬을 예정
