문제
해결 방안 고민
// 주몽
갑옷을 만드는 재료는 고유의 번호
두 개의 재료 => 고유한 번호를 합쳐서 M이 되면 갑옷을 만든다
갑옷을 몇 개나 만들 수 있는지를 확인
N개의 재료
갑옷을 만드는 데 필요한 수
N개의 재료들이 가진 고유한 번호들 (공백 있음)
br.readLine();
br.readLine();
StringTokenizer st = new StringTokenizer();
int[] arr = Integer.parseInt(st.nextToken());
// 정렬과 투 포인터를 활용하여 두 수가 M보다 작거나 크거나 같을 때를 고려하여 count를 증가시켜주면 끝
1 2 3 4 5 7
Java
복사
해결 방법
•
두 수를 더했을 때 M과 일치하는 경우의 수를 구하는 문제이다.
•
처음에는 이중 for문을 통해 count에 증가시키는 방향으로 코드를 작성하였지만 시간이 다소 걸린다는 점을 감안하여 이중 for문을 사용하지 않으면서 경우의 수를 구할 수 있는 방법을 고민했다.
•
정렬을 활용하지 않고도 구할 수 있으나 시간이 더 걸린다는 점에서 정렬을 활용하여 count를 알아내는 시간을 줄일 수 있다.
코드
•
처음 작성한 코드
◦
참고로 이렇게 작성하면 BufferedWriter를 활용하더라도 시간이 많이 걸린다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
int[] arr = new int[N];
int length = arr.length;
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int count = 0;
// 2 7 4 1 5 3 => 1 2 3 4 5 7
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
if (arr[i] + arr[j] == M) {
count++;
}
}
}
System.out.println(count);
}
}
Java
복사
•
수정한 코드
◦
정렬을 활용하면 count 수를 확인하는 과정을 줄일 수 있다.
◦
예를 들어 2 7 4 1 5 3 을 1 2 3 4 5 7 로 바꾸면 다음과 같다.
▪
start를 0, end를 length - 1 로 설정한다.
▪
M이 9일 때 1과 2를 더하면 M보다 작으므로 end 변수를 증가시켜준다. 정렬을 하였기에 뒤의 수를 더하면 더 큰 수를 얻을 수 있다. 반대로 두 수를 더했을 때 M보다 크다면 end를 감소시켜 9와 가까워질 수 있는 조건으로 변경하면 된다.
▪
참고로 bw.write() 에 count를 그대로 넣어 출력하면 오답이 된다. String.valueOf(count)으로 해야 정답이 된다. bw.write() 활용시 정수형 결과는 string 으로 변환하여 출력해야 한다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
int[] arr = new int[N];
int length = arr.length;
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int count = 0;
int start = 0;
int end = length - 1;
Arrays.sort(arr);
// 2 7 4 1 5 3 => 1 2 3 4 5 7
while (start < end) {
if (arr[start] + arr[end] < M) {
start++;
} else if (arr[start] + arr[end] > M) {
end--;
} else if (arr[start] + arr[end] == M) {
start++;
end--;
count++;
}
}
bw.write(String.valueOf(count));
bw.flush();
bw.close();
br.close();
}
}
Java
복사
