모순관계가 생기면 문제에서 주어진 예시 2번 처럼 어떻게든 0->1로 바뀌는 모습이 나타날 수 밖에 없습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static StringTokenizer st;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[][] people = new int[N][M + 1];
for (int n = 0; n < N; n++) {
st = new StringTokenizer(br.readLine());
int sum = 0;
for (int m = 0; m < M; m++) {
people[n][m] = Integer.parseInt(st.nextToken());
sum += people[n][m];
}
people[n][M] = sum;
}
Arrays.sort(people, (e1, e2) -> {
return e2[M] - e1[M];
});
boolean answer = true;
loop: for (int m = 0; m < M; m++) {
int check = people[0][m];
for (int n = 0; n < N; n++) {
if(check < people[n][m]) {
answer = false;
break loop;
}
check = people[n][m];
}
}
if (answer) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
솔직히 말하면 저도... 검색을 통해 다른 사람들의 풀이를 보고 풀었는데, 이 문제는 LIS(Longest Increase Subsequence)의 응용문제로 DP와 이분 탐색 두 가지의 방법으로 풀이가 가능합니다.
DP의 경우 구현과 이해가 쉽지만 입력의 갯수가 많으면 시간 초과로 문제를 틀릴 가능성이 있다는데,
마침 문제가 입력의 갯수가 100개인 전깃줄 1과 10만 개인 전깃줄 2로 나뉘어 있으니 두 가지 방법을 각각 활용해서 풀어보도록 하겠습니다. 먼저 DP를 활용한 풀이 방법을 보겠습니다.
개념은 간단합니다, 전깃줄이 같은 곳에 걸쳐있지 않는다는 조건을 활용하여 입력을 정렬하고, 사용할 전깃줄의 갯수를 하나씩 늘려가며 전깃줄의 부분집합이 만들 수 있는 최댓값을 기록합니다. 이때 구한 최댓값을 DP 배열에 저장하고, 다음 풀이에서 활용할 수 있습니다.
예제 입력을 통해 확인해 보겠습니다.
(1,8), (3,9), (2,2) ,(4,1), (6,4), (10,10), (9,7), (7,6) 이렇게 8개의 전깃줄이 들어왔습니다.
이를 전깃줄의 시작 위치를 기준으로 정렬하면
(1,8), (2,2) ,(3,9), (4,1), (6,4), (7,6), (9,7), (10,10)와 같은 형태가 됩니다. 진행 방향은 상관이 없지만, 저는 뒤에서부터 쌓아가며 진행하도록 하겠습니다.
(10,10) 하나를 추가하고 -> 이때의 LIS길이는 당연히 1이 됩니다.
(9,7)를 추가하고 -> 9,7 전깃줄과 10,10 전깃줄은 겹치지 않으므로 아까 구한 LIS 길이에 1을 더해 2가 됩니다.
같은 방법으로 (4,1), (6,4), (7,6), (9,7), (10,10) 까지는 전깃줄이 겹치지 않고 LIS길이가 계속 늘어 5가 됩니다.
이 상태에 (3,9) 전깃줄을 추가하면 겹치는 부분이 발생하게 됩니다.
겹치는 영역은 (4,1), (6,4), (7,6), (9,7) 네 전깃줄로 (3,9)와 공존이 가능한 전깃줄은 (10,10) 뿐이고 그때의 LIS 길이에 1을 더한 2가 (3,9)를 포함한 LIS의 길이가 됩니다.
같은 방법으로 (2,2)를 추가했을때는 (2,2)다음으로 올 수 있는 전깃줄이 (6,4)로 (6,4)때 구한 값 4에 1을 더한 5를 얻고
(1,8)을 추가했을때는 (1,8), (3,9), (10,10)의 LIS가 구해집니다.
모든 경우에서 최댓값을 찾으면 예제에서 구할 수 있는 LIS의 길이는 5로 두가지 경우인 것을 알 수 있습니다.
이를 코드로 구현하면,
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static StringTokenizer st;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[][] wires = new int[N][2];
for (int n = 0; n < N; n++) {
st = new StringTokenizer(br.readLine());
wires[n][0] = Integer.parseInt(st.nextToken());
wires[n][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(wires, (e1, e2) -> {
return e1[0] - e2[0];
});
int[] dp = new int[N];
for (int n = N - 1; n >= 0; n--) {
dp[n] = 1;
int end = wires[n][1];
for (int m = n; m < N; m++) {
if (wires[m][1] > end) {
dp[n] = Math.max(dp[n], 1 + dp[m]);
}
}
}
int max = 0;
for (int n = 0; n < N; n++) {
max = Math.max(max, dp[n]);
}
System.out.println(N - max);
}
}
JAVA 언어에 입출력 방법이 많아서 처음 PS를 접하시는 분들이 헷갈릴 법도 하다!라는 생각이 들었습니다.
그래서 JAVA에서 주로 사용되는 입출력 방법들을 총 정리해보도록 하겠습니다!
입력
1. Scanner
import java.util.Scanner;
//util 패키지에서 Scanner import
public class io_test {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// Scanner 선언
int i = sc.nextInt();
// Integer 타입 받아오기
long l = sc.nextLong();
// Long 타입 받아오기 (JAVA의 Long은 C의 LongLong과 같은 크기입니다.)
double d = sc.nextDouble();
// Double 타입 받아오기
float f = sc.nextFloat();
// Float 타입 받아오기
String str1 = sc.next();
//String으로 입력 받아오기 (공백문자로 끊어서 가져옴)
String str2 = sc.nextLine();
//String으로 입력 받아오기 (개행문자로 끊어서 가져옴)
char[] charArr = sc.nextLine().toCharArray();
char c = charArr[i];
//String으로 입력 받아와서 Character 타입의 배열로 변환
}
}
Scanner는 아주 간편하고 강력한 입력방법입니다.
내부적으로 입력을 parsing해서 여러 타입으로 변환하는 메소드들이 미리 구현되어 있기 때문에 간편하고 예외적인 상황을 통제하기도 좋지만, 시간이 오래 걸립니다. (trade off)
PS 문제들은 입력이 정확하게 규칙대로 주어지기 때문에
풀이자가 입력의 예외를 잘 캐치하고 코드를 정확하게 작성했다면 Scanner를 사용하는 일은 괜히 동작 시간만 손해 보는 일이 될 수도 있습니다.
고난도의 PS 문제들은 입력의 개수가 10만, 100만 단위로 주어지기 때문에 A+B 같은 간단한 문제에선 신경 쓰이지 않던 시간 손해가 크리티컬 하게 작동할 수도 있기 때문입니다.
2. BufferedReader
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
//BufferedReader와 InputStreamReader 그리고 입출력 예외 IOException import
public class io_test {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//BufferedReader 선언하기
String str = br.readLine();
//String으로 입력 받아오기 (개행문자로 끊어서 가져옴)
int i = Integer.parseInt(str);
//String을 Integer로 parsing
long l = Long.parseLong(str);
//String을 Long으로 parsing
double d = Double.parseDouble(str);
//String을 Double로 parsing
float f = Float.parseFloat(str);
//String을 Float으로 parsing
char[] charArr = str.toCharArray();
char c1 = charArr[i];
//String으로 입력 받아와서 Character 타입의 배열로 변환
char c2 = str.charAt(i);
//String으로 입력 받아와서 그 문자열의 index가 가리키는 Character 가져오기
}
}
BufferedReader는 그 좋은 대안이 될 수 있습니다.
Buffered란 이름 그대로 버퍼에 입력을 쌓아두었다가 뭉탱이로 가져오는 놈이거든요.
대신 내부적인 타입 변환이 구현되어있지 않아 String, 또는 char[] 형태로 입력을 읽어옵니다.
가져온 값을 사용자가 직접 변환해주어야 하는데, 기본 타입 (Primitive type)들이나 기본적으로 재공 되는 Array, String 같은 Class 내부의 메소드를 이용해서 가능합니다.
하지만 이놈엔 문제가 있으니...
input = "1 2 3" 과 같은 경우, Scanner는 nextInt()를 쓸 때마다 알아서 1,2,3을 가져왔던 반면 BufferedReader는 "1 2 3"의 String을 그대로 가져오게 되고, 이 String을 곧바로 parseInt에 넣는다면 에러가 나오게 됩니다.
parseInt는 하나의 숫자를 기대했는데, 들어온 값을 도무지 이해하기가 힘들기 때문이죠.
그래서 BufferedReader를 사용할 땐 StringTokenizer를 자주 같이 쓰게 됩니다.
3. BufferedReader + StringTokenizer
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
//BufferedReader와 InputStreamReader 그리고 입출력 예외 IOException import
import java.util.StringTokenizer;
//StringTokenizer import
public class io_test {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//BufferedReader 선언하기
StringTokenizer st = new StringTokenizer(br.readLine());
//br에서 가져온 String을 StringTokenizer로 쪼개기
//기본적으로 공백문자로 쪼개지게 됨
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
//nextToken 메소드로 쪼개진 String을 가져옴
System.out.println( a + ", " + b + ", " + c);
}
}
위처럼 StringTokenizer를 사용해서 읽어온 String을 나누어 parsing 해주면, "1 2 3"같은 입력도 원하는 값으로 변환이 가능합니다.
StringTokenizer가 String을 쪼개는 기본적인 값은 공백문자이지만
StringTokenizer st = new StringTokenizer(br.readLine(), "a");
이런 식으로 쪼갤 delim을 지정해주게 되면
원하는 대로 String을 쪼개고 입력을 받을 수 있습니다.
또, hasMoreToken()과 같은 메서드로 남아있는 token이 있는지를 판별해 오류 없이 입력을 마무리할 수 있습니다.
출력
1. System.out.println
System.out.println("Hello JAVA");
정말 간단합니다. 기본적으로 제공되기 때문에 따로 import 할 패키지도 없습니다.
(Eclipse IDE 기준) sysout을 치고 ctrl+space를 누르면 자동으로 완성됩니다.
System.out.print(); 는 출력 문장의 뒤에 개행 문자 \n이 없고 System.out.println();은 기본적으로 줄 바꿈 하나가 들어가며 System.out.printf();는 c언어의 printf와 유사하게 format을 넣고 뒤에 그 안에 들어갈 변수들을 써서 사용할 수 있습니다.
간단한 프로그램에선 이 방법 만으로도 충분할 겁니다.
하지만 출력이 수만, 수십만 개 반복되어야 하는 문제에선 출력 시간으로 인해 문제를 틀리는 경우가 생깁니다.
겉으로 보는 우리는 간편하고, 안정적이지만 메소드의 내부에선 출력마다 Sync와 Outputstream을 부르면서 시간을 잡아먹기 때문입니다.
(trade-off는 프로그래밍에서 뗄 수 없는 진리와도 같습니다.)
2. BufferedWriter
그래서 우리는 BufferedWriter를 사용할 수 있습니다. 이름을 보면 알 수 있듯, BufferedWriter는 BufferedReader의 출력 버전입니다.
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
public class io_test {
public static void main(String[] args) throws IOException{
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//BufferedWriter 선언해주기! Reader와 마찬가지로 Stream의 import가 필요하다.
bw.write("123\n");
bw.write("456\n");
bw.write("789\n");
//Buffer에 출력할 값들을 쌓아놓는다.
bw.flush();
//쌓여있는 문장을 한 번에 출력!
bw.close();
//BufferedWriter를 닫아준다.
}
}
사용법도 BufferedReader와 유사합니다.
여러 문장을 각각 출력하지 않고, Buffer에 Write해놓았다가 flush 메소드로 한 번에 출력하는 방법으로 시간을 단축합니다. 더 이상 BufferedWriter를 사용하지 않을땐 close해주는걸 잊지마세요!
3. System.out.println + StringBuilder
BufferedWriter 사용하기가 어렵게 느껴진다면, StringBuilder를 활용하는것도 좋은 방법입니다.
String을 하나로 만들어주는데 concat 메소드와 달리 시간이 많이 걸리지 않습니다. concat이 새로운 String객체를 계속 생성한다면 StringBuilder는 StringBuilder하나의 값들을 계속 이어 붙이는 방식입니다.
(JAVA 버전에 따라 + 연산이 내부적으로 concat으로도, StringBuilder로도 구현되어있다고 합니다. 헷갈리지 않게 하나로 통일감있게 사용합시다.)
public class io_test {
public static void main(String[] args) {
StringBuilder sb = new StringBuilder();
//StringBuilder 선언, 따로 import할 package가 없다.
sb.append("123 ");
sb.append("456 ");
sb.append("789\n");
//StringBuilder에 출력할 문장을 계속 덧붙여준다.
System.out.println(sb);
//System.out.println(sb.toString());
//출력한다. sb.toString()이 조금 더 명확하지만 그냥 출력해도 동작한다.
//concat 메소드 예시
String str1 = "123 ";
str1 = str1.concat("456 ");
str1 = str1.concat("789\n");
System.out.println(str1);
//+연산 예시
String str2 = "123 "+"456 "+"789\n";
System.out.println(str2);
}
}
백준에서 가장 많은 제출이 이루어진 문제기도 하고, 브론즈~실버 등급 대표 문제들의 정답률이 50%는 가뿐히 넘기는걸 생각하면 생각보다 정답률이 낮은 문제기도 합니다.
1000번 문제를 틀리는 이유는 여러개가 있습니다.
1. 진짜 프로그래밍 언어에 대해 하나도 모른다.
2. 테스트케이스의 존재를 모르고 3을 출력하는 프로그램을 작성한다.
3. 자신이 작성한 언어가 아닌 다른 언어로 제출한다.
4. Main 함수, 또는 클래스의 이름을 잘못 설정한다.
5. 코드를 붙여넣는 과정에서 package, import등을 누락한다.
아무튼..
문제는 아주 간단합니다. 두개의 숫자를 입력받고, 덧셈연산의 결과값을 출력하면 됩니다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();
System.out.println(a+b);
}
}
이렇게요.
java 라이브러리 util 패키지의 Scanner 클래스를 import해주고
시스템의 입력인 System.in을 parameter로 새로운 Scanner 객체를 생성해주면 됩니다.
Scanner의 이름은 어떻게 정하셔도 상관없지만, 가독성과 다른 사람에게 코드를 공유할 때를 대비해 많이 사용하는 이름으로 선언해주시는게 좋습니다.
보통 기능적인 요소에서 따온 input, in 을 쓰기도 하고 Scanner 객체는 한 번 선언하고 계속 재사용하기 때문에 간단하게 scan, sc로 선언하기도 합니다.
Scanner 클래스 안에는 여러가지 메소드가 들어있는데요.
간단한 문제이므로 입력으로 들어오는 다음 숫자를 반환하는 nextInt()를 통해 A와 B값을 받고
JAVA의 기본적인 출력함수인 System.out.println()을 통해 A+B를 출력했습니다.
