분류 전체보기

[백준] 1427 - 소트인사이드 (자바/Java) : 계수 정렬(Counting Sort)

문제 배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자. 입력 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다. 자리수를 내림차순으로 정렬한다고 해서 계수 정렬(Counting Sort)가 생각 났다 계수 정렬은 O(N)의 시간 복잡도를 가지는 매우 빠른 정렬으로, 입력되는 숫자들의 범위가 작을수록 사용하기 좋다. 이 문제는 각 자리수를 정렬하는 것이니 0~9까지만 정렬하면 되기 때문에, 계수 정렬을 사용하여 빠른 정렬이 가능하다. 숫자를 String으로 입력 받아, charAt(i)를 이용하여 각 자리수를 int로 바꾸어 주었다. 그리고 0~9까지의..

[백준] 2751 - 수 정렬하기2 (자바/JAVA): 합병 정렬(Merge Sort)

https://www.acmicpc.net/problem/2751 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 처음에 선택 정렬을 썼다가 시간 초과가 나서 합병 정렬을 사용했는데도 시간 초과가 났다. 그래서 Scanner를 BufferedReader로, sysout println을 BufferedWriter로 바꿨는데도 시간 초과가 났다. 정렬 자체에 문제가 있는 것 같아서 질문을 ..

[자바/Java] 클래스 다형성(Polymorphism)

다형성 Animal > Person > Student 학생 객체 → 사람 관점 → 학생 관점 (O) 사람 객체 → 사람 관점 → 학생 관점 (X) Person s2 = new Student(); // 조상 클래스의 타입(Person)으로 자식 클래스 객체(Student)를 참조 //s2.study(); // 오류남.. Person으로 보고 있음 Student st = new Person(); // 참조 불가능 상속 관계에 있을 때 조상 클래스의 타입으로 자식 클래스 객체를 참조할 수 있다. 활용 다른 타입의 객체를 다루는 배열 Person[] persons = new Person[3]; persons[0] = new Person(); persons[1] = new Student(); persons[2] ..

[자바/Java] 클래스(Class), 상속, 생성자(Constructor), 오버라이딩(Override)

상속 확장성, 재사용성: 부모의 생성자와 초기화 블록은 상속x 클래스 선언 시 extends 키워드를 명시: 자바는 다중 상속X 관계 부모(상위, Super) 클래스 : Person 자식(하위, Sub) 클래스 : Student 자식 클래스는 부모 클래스의 멤버변수, 메소드를 자신의 것처럼 사용할 수 있다 Object 클래스는 모든 클래스의 조상 클래스 -별도의 extends 선언이 없는 클래스는 extends Object가 생략 super 키워드생성자 호출 순서: 부모 생성자 호출 → 자식(호출된 클래스) 생성자 호출 public class Person { String name; int age; public Person() { System.out.prinln("Person 생성자"); } public ..

[자바/Java] 싱글톤(Singleton) 패턴, Static

생성자가 여러 차례 호출되더라도 실제로 생성되는 객체는 하나이고, 최초 생성 이후에 호출된 생성자는 최초의 생성자가 생성한 객체를 리턴 public class Manager { private static Manager = manager = new Manager(); private Manager() {} public static Manager getManager() { return manager; } 기본 생성자를 private으로 → 외부에서 인스턴스를 새로 생성할 수 없음 getManager() 메서드는 인스턴스 생성과 상관없이 호출할 수 있어야 하기 때문에 반드시 static 용도/쓰임 여러 클래스에서 동시에 공유할 때 ex. 게임 - score cf. static class와 차이: Singleto..

[자바/Java] 배열, 1차원 배열, 2차원 배열 정리

배열 참조형 data type: String JVM 메모리 영역 스택 - 힙 참조형: String, 배열 → heap에 주소 값을 갖고 있음, 주소 1을 stack에 저장하여 힙의 값을 참조함 new로 생성: stack에 생성됨 String str1 = "서울"; //literal String str2 = new String("서울"); //object 객체 String str3 = str2; ==로 비교할 때, true 나올 수도 있음 배열의 생성과 초기화 자료형[] 배열이름 = {값1, 값2, 값3, 값4} 선언과 동시에 초기화 배열이름 = new 자료형[] {값1, 값2, 값3, 값4} 배열 생성 및 값 초기화 배열이름 = new 자료형[길이]; 배열 생성 (자료형의 초기값으로 초기화) 타입 Dat..

[백준] 2563 - 색종이 (자바/Java)

https://www.acmicpc.net/problem/2563 문제 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오. 예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다. 입력 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 ..

[백준] 2605 - 줄 세우기 (자바/Java)

https://www.acmicpc.net/problem/2605 문제 점심시간이 되면 반 학생 모두가 한 줄로 줄을 서서 급식을 탄다. 그런데 매일 같이 앞자리에 앉은 학생들이 앞에 줄을 서 먼저 점심을 먹고, 뒷자리에 앉은 학생들은 뒤에 줄을 서 늦게 점심을 먹게 된다. 어떻게 하면 이러한 상황을 바꾸어 볼 수 있을까 고민하던 중 선생님이 한 가지 방법을 내 놓았다. 그 방법은 다음과 같다. 학생들이 한 줄로 줄을 선 후, 첫 번째 학생부터 차례로 번호를 뽑는다. 첫 번째로 줄을 선 학생은 무조건 0번 번호를 받아 제일 앞에 줄을 선다. 두 번째로 줄을 선 학생은 0번 또는 1번 둘 중 하나의 번호를 뽑는다. 0번을 뽑으면 그 자리에 그대로 있고, 1번을 뽑으면 바로 앞의 학생 앞으로 가서 줄을 선다..

[백준] 2578 - 빙고 (자바/Java)

https://www.acmicpc.net/problem/2578 문제 빙고 게임은 다음과 같은 방식으로 이루어진다. 먼저 아래와 같이 25개의 칸으로 이루어진 빙고판에 1부터 25까지 자연수를 한 칸에 하나씩 쓴다 다음은 사회자가 부르는 수를 차례로 지워나간다. 예를 들어 5, 10, 7이 불렸다면 이 세 수를 지운 뒤 빙고판의 모습은 다음과 같다. 차례로 수를 지워가다가 같은 가로줄, 세로줄 또는 대각선 위에 있는 5개의 모든 수가 지워지는 경우 그 줄에 선을 긋는다. 이러한 선이 세 개 이상 그어지는 순간 "빙고"라고 외치는데, 가장 먼저 외치는 사람이 게임의 승자가 된다. 철수는 친구들과 빙고 게임을 하고 있다. 철수가 빙고판에 쓴 수들과 사회자가 부르는 수의 순서가 주어질 때, 사회자가 몇 번째..

[백준] 2309 - 일곱 난쟁이 (자바/Java)

https://www.acmicpc.net/problem/2309 문제 왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다. 아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다. 아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오. 입력 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. ..