현재의 층수인 int 형이 주어지고 이를 +-10^n층을 옮겨 다니며 0층으로 이동하는 최수 횟수를 구하는 것이다. 10^n층을 옮기는데 1의 횟수가 추가된다.
입력
현재 층수가 입력으로 주어진다.
1 <= storey <= 100,000,000
풀이
10^0의 값인 1층부터 0으로 맞추며 storey값이 0이 될 때까지 %10, /=10을 해주며 구하면 된다고 생각했다.
5층 이하인 경우 현재 1의 자리 층수만을 더 해준다.
answer += rest;
6층 이상인 경우 (10-현재 1의 자리 층수)만을 더 해주며 storey에 1을 더해준다.
answer += (10-rest); storey++;
오답 코드
class Solution {
public int solution(int storey) {
int answer = 0;
while(storey != 0) {
int rest = storey%10;
storey /= 10;
if(rest <= 5) {
answer += rest;
} else {
storey++;
answer += (10-rest);
}
}
return answer;
}
}
하지만, 해당 코드는 정확도에서 문제가 발생했다.
문제는 1의 자리 수가 5일 때 발생한다. 만약, storey 값이 55라고 가정해보자. +5를 해도, -5를 해도 총 횟수는 10으로 문제가 발생하지 않는다. 하지만, storey 값이 195라고 가정해보자. +5를 하면 200이되고 총 7번만에 0층으로 간다. 하지만, -5를 하면 총 8번만에 0층으로 간다.
위의 문제를 해결하는 방법은 1의 자리 수가 5인 경우 10을 나눈 storey 값의 1의 자리 수가 5 이상인 경우 아래의 작업을 해야한다.
놀이터에 시소가 있다. 시소는 중심으로 부터 2, 3, 4m 거리의 지점에 좌석이 하나씩 있다.
각 사람마다 무게가 존재하고 거리 X 사람의 무게가 같다면 시소 짝꿍이 될 수 있다.
입력
int 배열 weights가 주어지며 길이는 2이상 10만 이하이다.
weights[i]는 100이상 1000이하이다.
풀이
문제를 정확하게 풀어내기 위해서는 완탐으로 10만 X 10만의 시간복잡도가 처음으로 생각날 것이다. 하지만, 10만X10만은 문제를 많이 풀어보면 알겠지만 완탐으로 시간초과가 나오기 아주 좋은 숫자이다. 보통 O(N^2)로 풀어낼 때, N이 10만이상이면 시간을 줄일 생각을 먼저해야한다.
그렇다면, 어떻게 시간을 줄일까? 제한 사항을 읽어보며, weights[i]의 숫자가 문제를 풀어낼 수 있는 key임을 알 수 있었다. weights 배열을 한바퀴 돌며, 100에서 1000사이의 값의 개수를 구한 뒤 100~1000사이를 돌면 끝나는 문제였다. 이대로 구현하면 문제는 크게 O(N+900)으로 O(N)만에 문제를 풀어낼 수 있다.
오답 코드
class Solution {
public long solution(int[] weights) {
long answer = 0;
int[] arr = new int[1001];
for(int i = 0; i < weights.length; i++) {
arr[weights[i]]++;
}
long[] sameNumber = new long[100001];
sameNumber[0] = 0;
sameNumber[1] = 0;
for(int i = 2; i <= 100000; i++) {
sameNumber[i] = (sameNumber[i-1]+(i-1));
}
for(int i = 100; i <= 1000; i++) {
if(arr[i] == 0) continue;
answer += sameNumber[(int)arr[i]];
double divideOfTwo = i/2.0;
double divideOfThree = i/3.0;
if(divideOfTwo*3 <= 1000) {
if(isInteger(divideOfTwo*3)) {
answer += (arr[i]*arr[(int)(divideOfTwo*3)]);
}
}
if(divideOfTwo*4 <= 1000) {
if(isInteger(divideOfTwo*4)) {
answer += (arr[i]*arr[(int)(divideOfTwo*4)]);
}
}
if(divideOfThree*4 <= 1000) {
if(isInteger(divideOfThree*4)) {
answer += (arr[i]*arr[(int)(divideOfThree*4)]);
}
}
}
return answer;
}
public boolean isInteger(double num) {
return Math.floor(num) == num;
}
}
풀이대로 구현했지만 3개의 답안이 통과되지 못했다. 약 30분을 고민하며 코드를 살펴본 결과 답을 알 수 있었다. 문제는 아래에 있었다.
int[] arr = new int[1001];
int형 배열로 선언한 것이 무엇이 문제일까? 아래를 보고선 힌트를 얻어보자.
answer += (arr[i]*arr[(int)(divideOfTwo*3)]);
문제가 무엇인지 알 수 있을까? 모르겠다면 조금 더 고민해보자.
정답은 arr[i]가 5만 arr[(int)(divideOfTwo*3)]가 5만이라고 생각해보자. 곱하면 25억이 나오지만 int형은 21억까지만 표현할 수 있기때문에 쓰레기 값이 나오게된다. 해결방법은 arr배열을 long타입으로 선언하면 된다.
정답 코드
class Solution {
public long solution(int[] weights) {
long answer = 0;
long[] arr = new long[1001];
for(int i = 0; i < weights.length; i++) {
arr[weights[i]]++;
}
for(int i = 100; i <= 1000; i++) {
if(arr[i] == 0) continue;
answer += (arr[i]-1)*arr[i]/2;
double divideByTwo = i/2.0;
double divideByThree = i/3.0;
if(divideByTwo*3 <= 1000) {
if(isInteger(divideByTwo*3)) {
answer += (arr[i]*arr[(int)(divideByTwo*3)]);
}
}
if(divideByTwo*4 <= 1000) {
if(isInteger(divideByTwo*4)) {
answer += (arr[i]*arr[(int)(divideByTwo*4)]);
}
}
if(divideByThree*4 <= 1000) {
if(isInteger(divideByThree*4)) {
answer += (arr[i]*arr[(int)(divideByThree*4)]);
}
}
}
return answer;
}
public boolean isInteger(double num) {
return Math.floor(num) == num;
}
}
!TIP 추가로 sameNumber 배열은 같은 수일 때 짝꿍 개수를 얻기 위해 dp형식으로 만들었지만, (n-1)*n/2로 표현할 수 있음을 이후에 알게되어 고쳤다.
입력으로 호텔을 예약하는 사람들의 "시작 시간", "종료 시간"이 String 배열로 주어진다.
운영자는 시작 시간과 종료 시간이 겹치는 사람의 최대 수 만큼 객실을 운영하여 비용을 최소로 하려고 한다. 겹치는 고객의 최대 수를 구해보자.
풀이
문제를 보자마자 생각한 방법은 dp인가? 누적합인가? 하는 방식이다.
입력은 HH:MM으로 주어지고 최대 시간은 23:59이다. 이를 int형으로 바꾸면 HH*60+MM으로 최대로 가질 수 있는 int 값은 1439이지만 청소 시간을 추가해야한다. 청소시간은 10분으로 10을 더한 값인 1449가 최대로 가질 수 있는 시간 값으로 볼 수 있다. 여기서 시간값은 배열의 인덱스로 가질 수 있는 값임을 인지했다.
먼저 String 배열을 한바퀴 돌며 int형 배열에 시작 시간 index에 +1, 종료시간 +10한 값에 -1을 하면 배열을 한 바퀴 돌 때 겹치는 고객의 최대 수를 구할 수 있을 것이라고 판단했다.
파단해본 알고리즘으로 문제를 가정해보자. 아래 "시작 시간", "종료시간 + 청소시간"을 가진 고객 4명이 주어졌다.
"1", "9"
"2", "8"
"3", "7"
"7", "9"
아래는 위 의 4개의 고객이 존재할 때, 구현된 표이다.
index
1
2
3
4
5
6
7
8
9
배열 값
1
1
1
0
0
0
0
-1
-2
누적합
1
2
3
3
3
3
3
2
0
index 3부터 고객 3명이 함께 사용할 때 누적합의 값이 3을 가진다. index 7 때는 종료 고객 1명, 시작 고객 1명이 겹쳐서 고객 3명이 그대로 유지하는 모습이다.
이처럼 판단한 알고리즘 대로 구현하면 O(1440) 정도의 시간으로 문제를 정확하게 풀어낼 수 있다.
풀이
class Solution {
public int solution(String[][] book_time) {
int answer = 0;
int[] dp = new int[1450];
for(int i = 0; i < book_time.length; i++) {
int start_time = getStringToTime(book_time[i][0]);
int end_time = getStringToTime(book_time[i][1])+10;
dp[start_time]++;
dp[end_time]--;
}
for(int i = 1; i <= 1440; i++) {
dp[i] += dp[i-1];
answer = Math.max(answer, dp[i]);
}
return answer;
}
public int getStringToTime(String s) {
String[] t = s.split(":");
return Integer.parseInt(t[0])*60+Integer.parseInt(t[1]);
}
}
N개의 섬으로 이루어진 섬들 사이에서 다리가 M개 설치되어 있다. 다리는 양방향으로 연결되어있고, c라는 최대 용량이 존재한다.
A섬에서 B섬으로 갈 때, 이동할 수 있는 다리 중 최대 용량을 옮길 수 있는 값을 출력해야 한다.
입력
N M
M개의 다리 (a, b, c) - 양방향
A섬 B섬
풀이
가장 먼저 생각한 방법은 다익스트라 였다. (무게를 내림차순으로 bfs를 도는 방식)
distance라는 int 배열을 통해 해당 섬으로 갔을 때의 최대 용량을 업데이트 하면서 bfs를 도는 방식이다. (최대 용량보다 낮다면 굳이 이후 작업을 할 필요가 없기 때문)
Add 문제를 풀고 다른 사람들의 코드를 보며 안 방법인데, 이분탐색 방식도 가능하다. 아래 코드추가 해놓음
코드 (메모리 초과)
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Main {
static int N, M, start, end, answer;
static int[] distance;
static List<Node>[] lists;
public static void main(String[] args) throws Exception {
InputReader in = new InputReader(System.in);
N = in.nextInt();
M = in.nextInt();
distance = new int[N+1];
lists = new ArrayList[N+1];
answer = 0;
for(int i = 1; i <= N; i++) lists[i] = new ArrayList<Node>();
// A, B, C
// 1 <= A,B <= N
// 1 <= C <= 10억
for(int i = 0; i < M; i++) {
int a = in.nextInt();
int b = in.nextInt();
int c = in.nextInt();
lists[a].add(new Node(b,c));
lists[b].add(new Node(a,c));
}
start = in.nextInt();
end = in.nextInt();
bfs();
System.out.println(distance[end]);
}
public static void bfs() {
PriorityQueue<Node> pq = new PriorityQueue<>();
distance[start] = 1000000001;
pq.add(new Node(start, 1000000001));
while(!pq.isEmpty()) {
Node node = pq.poll();
if(distance[node.next] > node.weight) continue;
for(int i = 0; i < lists[node.next].size(); i++) {
Node next = lists[node.next].get(i);
if(distance[next.next] > Math.min(node.weight, next.weight) ||
distance[end] > Math.min(node.weight, next.weight)) continue;
distance[next.next] = Math.min(node.weight, next.weight);
pq.add(new Node(next.next, Math.min(node.weight, next.weight)));
}
}
}
}
class Node implements Comparable<Node>{
int next;
int weight;
public Node(int next,int weight) {
this.next = next;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
return o.weight - this.weight;
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
class가 8바이트로 10만개를 추가해도 80만 바이트이기 때문에 128MB를 넘지 않으리라고 생각했다. 어디서 무한루프를 빠진다고 생각했고 문제가 되는 부분은 if(distance[next.next] > Math.min(node.weight, next.weight)) 였다. >=를 추가하지 않았다. 업데이트하면서 bfs를 돌지만 distance값과 Math.min 값이 같기 때문에 무한루프에 빠지는 것이였다.
코드 (정답)
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Main {
static int N, M, start, end, answer;
static int[] distance;
static List<Node>[] lists;
public static void main(String[] args) throws Exception {
InputReader in = new InputReader(System.in);
N = in.nextInt();
M = in.nextInt();
distance = new int[N+1];
lists = new ArrayList[N+1];
answer = 0;
for(int i = 1; i <= N; i++) lists[i] = new ArrayList<Node>();
// A, B, C
// 1 <= A,B <= N
// 1 <= C <= 10억
for(int i = 0; i < M; i++) {
int a = in.nextInt();
int b = in.nextInt();
int c = in.nextInt();
lists[a].add(new Node(b,c));
lists[b].add(new Node(a,c));
}
start = in.nextInt();
end = in.nextInt();
bfs();
System.out.println(distance[end]);
}
public static void bfs() {
PriorityQueue<Node> pq = new PriorityQueue<>();
distance[start] = 1000000001;
pq.add(new Node(start, 1000000001));
while(!pq.isEmpty()) {
Node node = pq.poll();
if(distance[node.next] > node.weight) continue;
for(int i = 0; i < lists[node.next].size(); i++) {
Node next = lists[node.next].get(i);
if(distance[next.next] >= Math.min(node.weight, next.weight) ||
distance[end] >= Math.min(node.weight, next.weight)) continue;
distance[next.next] = Math.min(node.weight, next.weight);
pq.add(new Node(next.next, Math.min(node.weight, next.weight)));
}
}
}
}
class Node implements Comparable<Node>{
int next;
int weight;
public Node(int next,int weight) {
this.next = next;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
return o.weight - this.weight;
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
이분탐색 코드 (정답)
ㄴimport java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Main {
static int N, M, start, end, answer;
static List<Node>[] lists;
public static void main(String[] args) throws Exception {
InputReader in = new InputReader(System.in);
N = in.nextInt();
M = in.nextInt();
lists = new ArrayList[N+1];
answer = 0;
for(int i = 1; i <= N; i++) lists[i] = new ArrayList<Node>();
int left = Integer.MAX_VALUE;
int right = Integer.MIN_VALUE;
for(int i = 0; i < M; i++) {
int a = in.nextInt();
int b = in.nextInt();
int c = in.nextInt();
lists[a].add(new Node(b,c));
lists[b].add(new Node(a,c));
left = Math.min(left, c);
right = Math.max(right, c);
}
start = in.nextInt();
end = in.nextInt();
while(left <= right) {
int middle = (left + right) / 2;
if(bfs(middle)) {
left = middle + 1;
answer = middle;
}
else right = middle - 1;
}
System.out.println(answer);
}
public static boolean bfs(int weight) {
Queue<Node> q = new LinkedList<>();
boolean[] visited = new boolean[N+1];
q.offer(new Node(start, 0));
while(!q.isEmpty()) {
Node node = q.poll();
if(node.next == end) return true;
for(int i = 0; i < lists[node.next].size(); i++) {
Node next = lists[node.next].get(i);
if(weight <= next.weight && !visited[next.next]) {
visited[next.next] = true;
q.add(next);
}
}
}
return false;
}
}
class Node{
int next;
int weight;
public Node(int next,int weight) {
this.next = next;
this.weight = weight;
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
시작 정점 s가 주어졌을 때, 시작정점에서부터 각 정점까지 최단거리를 출력하자. 단, 시작정점부터 못 가는 정점은 INF를 출력하자.
풀이
각 정점마다 가장 빠른 거리만 최신화하며 탐색하면 된다고 판단했다. -> 다익스트라
정점의 개수만큼 distance라는 int형 배열을 만들고, 간선 w의 최대값인 10과 정점의 최대값인 20,000을 곱한 200,000보다 1큰 200,001로 초기화했다. 그래프를 탐색하며 distance 배열을 최신화시킬 수 있는 탐색만 진행했다.
코드
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.stream.IntStream;
public class Main {
static int v,e,s;
static List<Node>[] list;
static int[] distance;
public static void main(String[] args) throws Exception {
InputReader in = new InputReader(System.in);
v = in.nextInt();
e = in.nextInt();
s = in.nextInt();
list = new ArrayList[v+1];
distance = new int[v+1];
for(int i = 1; i <= v; i++) {
list[i] = new ArrayList<Node>();
distance[i] = 200001;
}
for(int i = 0; i < e; i++) {
int s = in.nextInt();
int e = in.nextInt();
int w = in.nextInt();
list[s].add(new Node(e, w));
}
bfs();
StringBuilder sb = new StringBuilder();
for(int i = 1; i <= v; i++) {
if(i==s) sb.append("0");
else if(distance[i] != 200001) sb.append(distance[i]);
else sb.append("INF");
sb.append("\n");
}
System.out.println(sb);
}
public static void bfs() {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(s, 0));
distance[s] = 0;
while(!pq.isEmpty()) {
Node node = pq.poll();
for(int i = 0; i < list[node.next].size(); i++) {
Node next = list[node.next].get(i);
if(distance[next.next] <= distance[node.next] + next.distance) continue;
distance[next.next] = distance[node.next] + next.distance;
pq.add(new Node(next.next, node.distance+next.distance));
}
}
}
}
class Node implements Comparable<Node> {
int next;
int distance;
public Node(int next, int distance) {
this.next = next;
this.distance = distance;
}
@Override
public int compareTo(Node o) {
return this.distance - o.distance;
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
해당 문제의 경우 전화번호 수인 N이 최대 10만이기 때문에, O(N^2)의 경우 시간내에 들어오지 못한다. O(NlogN) 방법을 생각했고, 같은 접두어인 경우 인접해있기 때문에 정렬을 사용했다.
코드
public class Main {
public static void main(String[] args) throws Exception {
InputReader in = new InputReader(System.in);
int testcase = in.nextInt();
StringBuilder sb = new StringBuilder();
while(testcase-->0) {
int N = in.nextInt();
String[] numberOfPhone = new String[N];
for(int i = 0; i < N; i++) {
numberOfPhone[i] = in.nextLine();
}
Arrays.sort(numberOfPhone);
boolean flag = false;
for(int i = 1; i < N; i++) {
if(numberOfPhone[i].startsWith(numberOfPhone[i-1])) {
flag = true;
break;
}
}
sb.append((flag) ? "NO\n" : "YES\n");
}
System.out.println(sb);
}
}
1. 일단 입력 받은 배열을 오름차순 정렬을 통해 왼쪽부터 오른쪽으로 점점 수가 커지게 정렬시킨다.
2. 용액 배열 양쪽에서 다가오면서, 두 개의 합이 0에 가장 가까울 경우 저장해준다.
3. 두 개의 합이 0 보다 작을 경우, 조금 더 0보다 가까운 경우가 있는지 알아보기 위해 왼쪽에서 다가오는 index를 하나 늘려준다.
4. 두 개의 합이 0보다 클 경우, 조금 더 0보다 가까운 경우가 있는지 알아보기 위해 오른쪽에서 다가오는 index를 하나 줄여준다.
코드
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.InputMismatchException;
public class Main {
static int[] array;
static int N, answer1, answer2;
public static void main(String[] args) throws Exception {
SetData();
TwoPointer();
System.out.println(answer1 + " " + answer2);
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
N = in.nextInt();
array = new int[N];
answer1 = answer2 = 0;
for (int i = 0; i < N; ++i) {
array[i] = in.nextInt();
}
Arrays.sort(array);
}
private static void TwoPointer() {
int min = Integer.MAX_VALUE;
int left = 0, right = N - 1;
// 투 포인터
while (left < right) {
int sum = array[left] + array[right];
// v가 최소일 때 특성값 갱신
if (min > Math.abs(sum)) {
min = Math.abs(sum);
answer1 = array[left];
answer2 = array[right];
}
if (sum > 0)
right--;
else
left++;
}
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String readString() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
Retry
2024.1.15 코드
풀이
일단, N개의 입력은 정렬된 상태로 입력이 된다고 주어진다. (-> 굳이 정렬을 할 필요가 없다는 뜻)
두 수의 합이 0에 가장 가까운 방법을 찾으면 되기때문에 가장 왼쪽과 가장 오른쪽을 더 해주면서 절대값이 더 큰 값의 index를 왼쪽은 + 1, 오른쪽은 - 1하며 반복하면 된다고 생각했다. 왼쪽 index가 오른쪽 index보다 작을 때까지만!
public static void main(String[] args) throws Exception {
InputReader in = new InputReader(System.in);
int n = in.nextInt();
int[] arr = new int[n];
for(int i = 0; i < n; i++) arr[i] = in.nextInt();
int minimum = 100;
int al=0, san=0;
int left = 0, right = n-1;
while(left < right) {
int sum = arr[left] + arr[right];
// 합이 이전 비교보다 0에 가까울 경우
if(Math.abs(sum) <= minimum) {
al = arr[left];
san = arr[right];
minimum = Math.abs(sum);
}
if(Math.abs(arr[left]) <= Math.abs(arr[right])) {
right--;
} else {
left++;
}
}
System.out.println(al + " " + san);
}
첫 풀이는 위와 같다. 하지만, 27% 정도에서 틀렸습니다.
문제를 다시 잘 읽어본 결과 minimum 초기 값이 너무 작아서 틀렸다고 나온 것 같았다. 10억 2개만 있는 경우 더하면 20억이 될 수도 있기때문이다.
public static void main(String[] args) throws Exception {
InputReader in = new InputReader(System.in);
int n = in.nextInt();
int[] arr = new int[n];
for(int i = 0; i < n; i++) arr[i] = in.nextInt();
int minimum = 2000000001; // 20억보다 1큰 20억 1로 초기화
int al=0, san=0;
int left = 0, right = n-1;
while(left < right) {
int sum = arr[left] + arr[right];
// 합이 이전 비교보다 0에 가까울 경우
if(Math.abs(sum) <= minimum) {
al = arr[left];
san = arr[right];
minimum = Math.abs(sum);
}
if(Math.abs(arr[left]) <= Math.abs(arr[right])) {
right--;
} else {
left++;
}
}
System.out.println(al + " " + san);
}
위의 코드로 Success!
Go 풀이
package main
import (
"bufio"
"fmt"
"math"
"os"
)
var reader *bufio.Reader = bufio.NewReader(os.Stdin)
var writer *bufio.Writer = bufio.NewWriter(os.Stdout)
func main() {
defer writer.Flush()
var n int
fmt.Fscan(reader, &n)
arr := make([]int, n)
for i := 0; i < n; i++{
fmt.Fscan(reader, &arr[i])
}
minimum := 2000000001
al := 0
san := 0
left := 0
right := n-1
for left < right {
sum := arr[left] + arr[right]
if(int(math.Abs(float64(sum))) <= minimum) {
al = arr[left];
san = arr[right];
minimum = int(math.Abs(float64(sum)));
}
if(int(math.Abs(float64(arr[left]))) <= int(math.Abs(float64(arr[right])))) {
right--;
} else {
left++;
}
}
fmt.Fprintln(writer, al, san)
}
기존 fmt.Scanf혹은 Println을 사용하면 시간 초과가 뜬다. 더 빠르게 입출력을 할 수 있도록 도와주는 라이브러리를 사용해야 한다고 함.
