우유

https://www.acmicpc.net/problem/4949

풀이 

어렵게 생각하면 어렵고 쉽게 생각하면 쉬운 문제였다.
많은 문자열을 입력받지만, 우리가 생각해야될 것은 괄호 뿐이므로 '(', ')', '[', ']'가 들어오는 경우만
생각해주면 된다.

'(' , '['이 들어오는 경우는 Stack에 Push 하였고
')', ']' 이 들어오는 경우는 앞에 여는 괄호가 일치한지만 판단하여 pop하였다.

기타

풀다가 문자열을 비교할 때 equals 와 == 차이가 궁금해서 글로 한번 요약 정리 해보았다.

https://studywithus.tistory.com/88

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {

	public static void main(String[] agrs) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		while (true) {
			String input = br.readLine();

			if (input.equals("."))
				break;

			sb.append(solve(input) + '\n');
		}
		System.out.println(sb);
	}

	static String solve(String input) {

		Stack<Character> stack = new Stack<Character>();

		for (int i = 0; i < input.length(); i++) {
			char c = input.charAt(i);

			if (c == '(' || c == '[')
				stack.push(c);

			if (c == ')') {
				if (stack.isEmpty() || stack.peek() != '(')
					return "no";
				else
					stack.pop();
			}

			if (c == ']') {
				if (stack.isEmpty() || stack.peek() != '[')
					return "no";
				else
					stack.pop();
			}
		}

		if (stack.isEmpty())
			return "yes";
		else
			return "no";
	}
}

Java에서 int와 boolean과 같은 일반적인 데이터 타입의 비교는 ==이라는 연산자를 사용하여 비교합니다. 하지만 String처럼 Class의 값을 비교할때는 ==이 아닌 equals()라는 메소드를 사용하여 비교를 합니다. equals와 == 은 어떤 차이점이 있을까요.

String 변수 생성시 주소할당

String변수를 생성할때는 두가지 방법이 있습니다.

1. 리터럴을 이용한 방식 
2. new 연산자를 이용한 방식 

위의 두 가지 방식에는 큰 차이점이 있습니다. 리터럴을 사용하게 되면 string constant pool이라는 영역에 존재하게 되고 new를 통해 String을 생성하면 Heap 영역에 존재하게 됩니다. String을 리터럴로 선언할 경우 내부적으로 String의 intern() 메서드가 호출되게 되고 intern() 메서드는 주어진 문자열이 string constant pool에 존재하는지 검색하고 있다면 그 주소값을 반환하고 없다면 string constant pool에 넣고 새로운 주소값을 반환합니다. 

여기서 String pool 이란?

Pool 하면 보통 수영장 풀, 풀장 등을 떠올리실 텐데요. 이처럼 String pool 하면 string이 존재하는 영역을 생각하시면 될 것 같습니다. 같은 String이지만 생성 방식에 따라 차이가 있어 문자열 비교 시 혼란을 주기도 하는데요. 다음 예제를 통해 설명해보겠습니다.

String a = "apple";
String b = new String("apple");
String c = "apple";
String d = new String("apple");

System.out.println(a==b); // false
System.out.prrintln(a==c); // true

첫 번째 줄에서 String a가 생성될 때, 'apple'은 리터럴 문자열이므로 Heap영역 중에서 String pool에 위치하게 됩니다.
두 번째 줄에서 String b는 new 연산자를 통해 객체를 생성합니다. Heap영역에 위치하지만 String pool이 아닌 다른 주소값을 참조합니다.

'=='연산자는 같은 메모리를 참조하는가를 비교합니다. 때문에  a와 b의 비교(a==b)는 false를 반환하게 됩니다.

그렇다면 c는 어떨까요? c가 가리키는 'apple'을 String pool에 넣으려고 보니 이미 'apple'이 존재합니다. 그러면 c는 a와 같은 String pool의 'apple'을 가리키게 됩니다.

a와 c가 같은 값을 참조하므로 a==c는 true를 반환합니다.

이를 그림으로 표현해보면 다음과 같습니다.

주소값 비교(==)와 값 비교(equals)

==연산자와 equals()메소드의 가장 큰 차이점은 == 연산자는 비교하고자 하는 두개의 대상의 주소값을 비교하는데 반해 String클래스의 equals 메소드는 비교하고자 하는 두개의 대상의 값 자체를 비교한다는 것입니다. 기본 타입의 int형, char형등은 Call by Value 형태로 기본적으로 대상에 주소값을 가지지 않는 형태로 사용됩니다. 하지만 String은 일반적인 타입이 아니라 클래스입니다. 클래스는 기본적으로 Call by Reference형태로 생성 시 주소값이 부여됩니다. 그렇기에 String타입을 선언했을때는 같은 값을 부여하더라도 서로간의 주소값이 다릅니다.

문자열 비교 (==연산자)

public class compare {
    public static void main(String[] args) {
        String s1 = "abcd";
        String s2 = new String("abcd");
		
        if(s1 == s2) {
            System.out.println("두개의 값이 같습니다.");
        }else {
            System.out.println("두개의 값이 같지 않습니다.");
        }
    }
}

위의 결과를 보시면 ==으로 비교한 두개의 값은 서로 다르다는 결론이 나오게 됩니다. == 연산자의 경우 참조 타입 변수들 간의 연산은 동일한 객체를 참조하는지, 다른 객체를 참조하는지 알아볼 때 사용됩니다. 참조 타입의 변수의 값은 힙 영역의 객체 주소이므로 결국 주소 값을 비교하는 것이 되어 다르다는 결론이 나온것입니다. 그래서 자바에서 문자열을 비교하려면 equals라는 메서드를 활용하여 두개의 값을 비교해주어야 합니다.

문자열 비교 (equals메서드)

public class compare {
    public static void main(String[] args) {
        String s1 = "abcd";
        String s2 = new String("abcd");
		
        if(s1.equals(s2)) {
            System.out.println("두개의 값이 같습니다.");
        }else {
            System.out.println("두개의 값이 같지 않습니다.");
        }
    }
}

String 클래스안에 있는 equals라는 메서드를 사용하면 두 비교대상의 주소 값이 아닌 데이터값을 비교하기 때문에 어떻게 String을 생성하느냐에 따라 결과가 달라지지 않고 정확한 비교를 할 수 있습니다.

https://www.acmicpc.net/problem/2477

풀이 

처음에는 간단하게 생각해서 ( 전체 큰 사각형 - 작은 사각형 ) 빼면 되는 쉬운 문제 인줄 알았으나 생각보다 시간이 오래 걸렸다. 

큰 사각형 = (가장 큰 세로 X 가장 큰 가로)
작은 사각형 = (가장 작은 세로 X 가장 작은 가로)
Result = 큰 사각형 - 작은 사각형  
이렇게 생각했으나 작은 사각형의 가로,세로값이 가장 작지 않을 수도 있는 경우를 생각하지 못해서 다른 방법을 찾았다.

방법은, 접한 (가로, 세로)의 쌍을 곱해서 모두 더하는 것  

빨간색 사각형은 3번씩, 파란색 사각형 2번씩 더해진다. (x = 빨간색, y = 파란색)
3x + 2y = 22800 (160*50 + 160*30 + 30*20 + 20*60 + 20*100 + 50*160)     // 인접한 가로*세로의 합
x + y = 160*50 = 8000 // 큰사각형 전체의 넓이
비례식을 이용하여 풀이하면 

즉, (인접한 가로*세로 값들의 합 - 가장 큰 사각형의 넓이 X 2) * K

( 22800 - 8000 * 2 ) * 7 = 47600 

※ 여기서 가장 큰 사각형의 넓이는 코드에서 인접한 사각형끼리 곱했을 때 나오는 최댓값을 갱신 하여 구하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] agrs) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int sum = 0;
		int max = Integer.MIN_VALUE;
		int K = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine());
		st.nextToken();

		int first = Integer.parseInt(st.nextToken());
		int pre = first;

		for (int i = 1; i < 6; i++) {
			st = new StringTokenizer(br.readLine());
			st.nextToken();
			int cur = Integer.parseInt(st.nextToken());
			max = Math.max(cur * pre, max);
			sum += cur * pre;
			pre = cur;
		}
		max = Math.max(pre * first, max);
		sum += pre * first;
		System.out.println((sum - max * 2)*K);
	}
}

https://www.acmicpc.net/problem/7562

동서남북으로 방향이 정해져있던 기존 BFS 와 다르게 나이트의 이동경로 8방향으로 dx,dy 배열을 초기화해주면 되는 간단한 문제이다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N, l;
	static int map[][];
	static boolean visited[][];
	static int startX, startY, endX, endY;
	static int dy[] = { -2, -2, -1, -1, 1, 1, 2, 2 };
	static int dx[] = { -1, 1, -2, 2, -2, 2, -1, 1 };

	public static void main(String[] agrs) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine());

		while (N-- != 0) {
			l = Integer.parseInt(br.readLine());

			map = new int[l][l];
			visited = new boolean[l][l];

			st = new StringTokenizer(br.readLine());

			startY = Integer.parseInt(st.nextToken());
			startX = Integer.parseInt(st.nextToken());

			st = new StringTokenizer(br.readLine());

			endY = Integer.parseInt(st.nextToken());
			endX = Integer.parseInt(st.nextToken());

			System.out.println(BFS(startY, startX));
		}
	}

	static int BFS(int y, int x) {
		
		if (y == endY && x == endX)
			return 0;
		
		Queue<int[]> qu = new LinkedList<int[]>();
		visited[y][x] = true;

		map[y][x] = 0;
		qu.add(new int[] { y, x });

		while (!qu.isEmpty()) {
			int[] temp = qu.poll();

			int curY = temp[0];
			int curX = temp[1];

			if (curY == endY && curX == endX)
				return map[endY][endX];

			for (int k = 0; k < 8; k++) {
				int ny = curY + dy[k];
				int nx = curX + dx[k];

				if (ny < 0 || nx < 0 || l-1 < ny || l-1 < nx)
					continue;

				if (visited[ny][nx])
					continue;

				qu.add(new int[] { ny, nx });
				map[ny][nx] = map[curY][curX] + 1;
				visited[ny][nx] = true;

			}
		}
		return -1;
	}
}

https://www.acmicpc.net/problem/2206

BFS의 최단거리를 찾아낸다는 특성을 가지고 풀수 있는 문제지만 벽을 한번 부수고 가야하는 것을 고려해야 하기때문에 생각이 조금 필요한 문제였다.

1. 벽을 부수고 온 경우와 부수고 오지 않은 경우 각각 다른 방문배열에 저장 (3차원 배열)

2.  Class 내에 내부 클래스를 사용하여 필요한 변수를 저장

핵심 포인트는 벽을 부수고 가는 경우와 벽을 부수고가지 않는 경우를 모두 고려해야하는데 벽을 부수고 가지 않는 경우가 더 최단거리 일수도 있기때문에  3차원 배열을 사용하여 [0][ny][nx]에 벽을 부수지 않고 방문한 경우, [1][ny][nx]에는 벽을 부수고 방문한 경우, 모두 저장해줘야한다. 

​

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N, M;
	static boolean visited[][][];
	static int map[][];
	static int dy[] = { 1, 0, -1, 0 };
	static int dx[] = { 0, 1, 0, -1 };

	static class Point {
		int x, y, dis;
		boolean destroyed;

		public Point(int x, int y, int dis, boolean destroyed) {
			this.x = x;
			this.y = y;
			this.dis = dis;
			this.destroyed = destroyed;
		}
	}

	public static void main(String[] agrs) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		visited = new boolean[2][N + 1][M + 1];
		map = new int[N + 1][M + 1];

		for (int i = 1; i <= N; i++) {
			String temp = br.readLine();
			for (int j = 1; j <= M; j++) {
				map[i][j] = temp.charAt(j - 1) - '0';
			}
		}

		BFS();

	}

	static void BFS() {
		Queue<Point> qu = new LinkedList<Point>();

		qu.add(new Point(1, 1, 1, false));

		visited[0][1][1] = true;

		while (!qu.isEmpty()) {

			Point curP = qu.poll();

			if (curP.y == N && curP.x == M) {
				System.out.println(curP.dis);
				return;
			}
			
			for (int i = 0; i < 4; i++) {
				int ny = curP.y + dy[i];
				int nx = curP.x + dx[i];

				if (ny <= 0 || nx <= 0 || N < ny || M < nx)
					continue;

				// 벽이 아닌 경우
				if (map[ny][nx] == 0) {
					//지금까지 벽을 부순적인 없는 경우
					if (!curP.destroyed && !visited[0][ny][nx]) {
						qu.add(new Point(nx, ny, curP.dis + 1, false));
						visited[0][ny][nx] = true;
					}
					// 벽을 부수고 온경우
					else if(curP.destroyed && !visited[1][ny][nx]) {
						qu.add(new Point(nx, ny, curP.dis + 1, true));
						visited[1][ny][nx] = true;
					}
				}
				// 벽인 경우
				else {
					// 벽을 부시고 방문한 적이 없으면
					if (!visited[1][ny][nx] && !curP.destroyed) {
						// 벽을 부시고 방문
						qu.add(new Point(nx, ny, curP.dis + 1, true));
						visited[1][ny][nx] = true;
					}
				}
			}

		}

		System.out.println(-1);

	}

}

https://www.acmicpc.net/problem/1697

1차원 BFS 를 활용하여 풀수 있는 단순한 문제다.

+1, -1, *2 가 되는 경우를 각각 변수에 저장하여 Queue에 넣어주고

Map 배열에 몇초에 방문할수 있는지 저장하였다.

N = K 인 경우까지 고려하여야 하고, N,K 범위가 0도 가능하다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N, K;
	static int cnt = 0;
	static int map[] = new int[100001];

	static Queue<Integer> qu = new LinkedList<Integer>();

	public static void main(String agrs[]) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		BFS(N);
		System.out.println(map[K]-1);
	}

	static void BFS(int N) {
		qu.add(N);
		map[N] = 1;

		if (N == K)
			return;
		
		
		while (!qu.isEmpty()) {
			int cur = qu.poll();

			if (cur == K)
				break;

			int a = cur + 1;
			int b = cur - 1;
			int c = cur * 2;

			if (0 <= a && a < 100001 && map[a] == 0) {
				qu.add(a);
				map[a] = map[cur]+1;
			}

			if (0 <= b && b < 100001 && map[b] == 0) {
				qu.add(b);
				map[b] = map[cur]+1;
			}

			if (0 <= c && c < 100001 && map[c] == 0) {
				qu.add(c);
				map[c] = map[cur]+1;
			}
		}
	}
}

https://www.acmicpc.net/problem/7569

7576번 문제의 3차원 배열 버전이다

푸는 방식은 동일하지만, 높이를 고려해야 하기때문에 배열을 3차원으로 선언하여 x,y 뿐만아니라 z까지 이동하는

방법으로 풀었다. static int N , M, H, 을 선언하고 int N, M, H 를 또 선언해줘서 괜한 시간 낭비를 했었다 ..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int M, N, H;
	static int cnt = 0;
	static int map[][][];
	static int dx[] = { 1, 0, -1, 0, 0, 0 };
	static int dy[] = { 0, 1, 0, -1, 0, 0 };
	static int dz[] = { 0, 0, 0, 0, 1, -1 };
	static boolean visited[][][];
	static Queue<int[]> qu = new LinkedList<int[]>();

	public static void main(String agrs[]) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());

		map = new int[H + 1][N + 1][M + 1];

		for (int i = 1; i <= H; i++) {
			for (int j = 1; j <= N; j++) {
				st = new StringTokenizer(br.readLine());
				for (int k = 1; k <= M; k++) {
					map[i][j][k] = Integer.parseInt(st.nextToken());

					if (map[i][j][k] == 1) {
						qu.add(new int[] { i, j, k });
					}
				}
			}
		}

		BFS();

		Loop1: for (int i = 1; i <= H; i++) {
			for (int j = 1; j <= N; j++) {
				for (int k = 1; k <= M; k++) {
					cnt = Math.max(map[i][j][k], cnt);

					if (map[i][j][k] == 0) {
						cnt = -1;
						break Loop1;
					}

				}
			}
		}
		if (cnt != -1)
			System.out.println(cnt - 1);
		else 
			System.out.println(cnt);
	
		

	}

	static void BFS() {

		while (!qu.isEmpty()) {
			int curH = qu.peek()[0];
			int curY = qu.peek()[1];
			int curX = qu.peek()[2];

			qu.poll();

			for (int i = 0; i < 6; i++) {
				int nh = curH + dz[i];
				int ny = curY + dy[i];
				int nx = curX + dx[i];

				if (nh <= 0 || ny <= 0 || nx <= 0 || nh > H || ny > N || nx > M)
					continue;

				if (map[nh][ny][nx] != 0)
					continue;

				qu.add(new int[] { nh, ny, nx });

				map[nh][ny][nx] = map[curH][curY][curX] + 1;

			}

		}
	}
}

https://www.acmicpc.net/problem/7576

기존에 BFS를 돌렸던 방식과 다르게 BFS를 돌릴 Queue 를 static 으로 선언해서

처음부터 익은 토마토가 있으면 순차적으로 Queue 에 넣어서 BFS를 돌리면 해결되는 문제였다.

또한, 전체 토마토가 익지 않은 경우를 생각하기 위해 BFS가 모두 돌았을 때 익지 않은 토마토 (0인 값)이 있으면

-1을 출력하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int M, N;
	static int map[][];
	static int dy[] = { 1, 0, -1, 0 };
	static int dx[] = { 0, 1, 0, -1 };
	static int cnt1 = 0, cnt2 = 0, day = 0;
	static Queue<int[]> qu = new LinkedList<int[]>();

	public static void main(String[] agrs) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		M = Integer.parseInt(st.nextToken()); // 가로
		N = Integer.parseInt(st.nextToken()); // 세로

		map = new int[N + 1][M + 1];

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());

				if (map[i][j] == 1)
					qu.add(new int[] { i, j });
				else if (map[i][j] == -1)
					cnt1++;
			}
		}

		BFS();

		Loop1: for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				day = Math.max(day, map[i][j]);

				if (map[i][j] == 0) {
					day = -1;
					break Loop1;
				}
			}
		}
		if (day != -1)
			System.out.println(day - 1);
		else
			System.out.println(day);
	}

	static void BFS() {

		while (!qu.isEmpty()) {
			int curY = qu.peek()[0];
			int curX = qu.peek()[1];

			qu.poll();

			for (int i = 0; i < 4; i++) {
				int ny = curY + dy[i];
				int nx = curX + dx[i];

				if (ny <= 0 || nx <= 0 || ny > N || nx > M)
					continue;

				if (map[ny][nx] != 0)
					continue;

				qu.add(new int[] { ny, nx });

				map[ny][nx] = map[curY][curX] + 1;

			}
		}

	}
}

https://www.acmicpc.net/problem/2606

간단한 DFS로 해결할수 있는 문제지만 ArrayList 와 Array 두가지 방법을 사용했을 때를 비교하고

두개 다 구현하는 방법을 연습하는 문제로 활용하였다.

Array로 구현한 DFS 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N, M, V;
	static int map[][];
	static boolean visited[];
	static int cnt =0;

	public static void main(String[] agrs) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());

		map = new int[N + 1][N + 1];
		visited = new boolean[N + 1];

		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			map[y][x] = 1;
			map[x][y] = 1;
		}

//		DFS(1);
//
//		Arrays.fill(visited, false);
//		System.out.println();
		
		BFS(1);
		System.out.println(cnt);
	}

	static void DFS(int i) {
		visited[i] = true;
		System.out.print(i + " ");

		for (int j = 1; j < N; j++) {

			if (map[i][j] == 1 && visited[j] == false) {
				visited[j] = true;
				DFS(j);
			}
		}
	}

	static void BFS(int i) {
		Queue<Integer> q = new LinkedList<Integer>();

		q.offer(i);
		visited[i] = true;

		while (!q.isEmpty()) {

			int temp = q.poll();
//			System.out.print(temp + " ");

			for (int j = 1; j <= N; j++) {

				if (map[temp][j] == 1 && visited[j] == false) {
					cnt ++;
					visited[j] = true;
					q.offer(j);
				}
			}
		}
	}
}

ArrayList 로 구현한 DFS 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

	static ArrayList<ArrayList<Integer>> al = new ArrayList<>();
	static int N, M;
	static boolean[] Visited;

	static int cnt =0;

	public static void main(String[] agrs) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());

		Visited = new boolean[N + 1];

		Arrays.fill(Visited, false);
		for (int i = 0; i <= N; i++) {
			al.add(new ArrayList<Integer>());
		}

		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			al.get(x).add(y);
			al.get(y).add(x);
		}

		DFS(1);
		
		System.out.println(cnt-1);
	}

	static void DFS(int V) {
		Visited[V] = true;

		cnt ++;
		for (int i = 0; i < al.get(V).size(); i++) {
			int temp = al.get(V).get(i);

			if (!Visited[temp]) {
				DFS(temp);
			}
		}
	}
}

Map 의 기본 개념만 알면 풀수 있는 간단한 문제였다.

오름차순으로 sort_arr 정렬에 재 배치하고

각 정렬된 해당 값을 키값으로 저장한뒤 순서를 value 값으로 Map 에 저장하여

해당 key값에 저장된 value를 가져오는 방법

But,,,, StringBuilder를 쓰지 않을땐 시간초과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] agrs) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		int[] sort_arr = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			sort_arr[i] = arr[i];
		}

		Arrays.sort(sort_arr);

		int n = 0;
		for (int i = 0; i < N; i++) {
			if (!hm.containsKey(sort_arr[i])) {
				hm.put(sort_arr[i], n);
				n++;
			}
		}

		for (int i = 0; i < N; i++) {
			sb.append(hm.get(arr[i]) + " ");
		}
		
		System.out.println(sb);
	}
}

https://www.acmicpc.net/problem/18870