[SWEA] S/W 문제해결 기본 1일차 ~ 2일차 | JAVA

난이도2만 풀다가 지겨워져서.. 어디 한번 문제 해결 능력을 길러보자 💪🏻

 

1204. [S/W 문제해결 기본] 1일차 - 최빈수 구하기 (D2, 54%)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV13zo1KAAACFAYh

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	
	int t = sc.nextInt();
	int[] arr = new int[1000];
	
	for(int tc=0; tc<t; tc++) {
		int idx = sc.nextInt();
		
		arr = new int[101];
		for(int i=0; i<1000; i++) {
			
			int n = sc.nextInt();
			arr[n]+=1;
		}
		
		
		int max = arr[0];
		int result = 0;
		for(int i=1; i<101; i++) {
			if(max<arr[i]) {
				max = arr[i];
				result = i;
			}
			if(max==arr[i]) {
				result = Math.max(result, i);
			}
		}
		
		System.out.printf("#%d %d\n",idx, result);
	}
	
	
}

 

1206. [S/W 문제해결 기본] 1일차 - View (D3, 66%)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV134DPqAA8CFAYh

처음에는 배열 전체 최솟값 구해서 전체 요소에 빼고 별 난리를 칠려고 했던 문제.. 너무 어렵게 생각했던것 같다. '양쪽 모두 거리 2 이상의 공간이 확보되어야한다' 해서 최솟값을 구한 값들이 양 옆 2칸씩 모두 0인지 확인하려고 했었다.

다른 풀이들 참고해본 결과, 그냥 주어진 범위[-2, +2](*기준 높이는 뺀) 최댓값에서 기준 높이(현재 값)을 빼주면 된다. 왜냐! 현재 위치의 건물 높이가 가장 높다는 조건이 걸려있기 때문이다. 

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
		
	int[] buildings;
	
	for(int tc = 0; tc<10; tc++) {
		int n = sc.nextInt();
		buildings = new int[n];
		
		for(int i=0; i<n; i++) buildings[i]=sc.nextInt();
		int cnt=0;
		int max=0;
		for(int i=2; i<n-2; i++) {
			max = Math.max( Math.max(buildings[i-2], buildings[i-1]), Math.max(buildings[i+1], buildings[i+2]));
			if(buildings[i] > max) {
				cnt += (buildings[i]-max);
			}
		}
		
		System.out.println("#"+(tc+1)+" "+cnt);
	}
}

 

1208. [S/W 문제해결 기본] 1일차 - Flatten (D3, 71%)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV139KOaABgCFAYh

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	
	List<Integer> arr = new ArrayList<Integer>();
	for(int tc=1; tc<=1; tc++) {
		int n = sc.nextInt();
		arr.clear();
		for(int i=0; i<100; i++) arr.add(sc.nextInt());
		int max = Collections.max(arr);
		int min =  Collections.min(arr);
		for(int i=0; i<n; i++) {
			if(max == min) break;
			int maxIdx = arr.indexOf(max);
			int minIdx = arr.indexOf(min);
			arr.set(maxIdx, max-1);
			arr.set(minIdx, min+1);
			max = Collections.max(arr);
			min =  Collections.min(arr);
		}
		System.out.println("#"+tc+" "+(max-min));
	}
}

가장 높은 곳과 낮은 곳의 크기와 인덱스를 구하기 위해 Collections의 여러 메소드를 사용했다. 뭔가 완벽한 답은 아닌거같아 다른 풀이를 찾아보니..

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	
	List<Integer> arr = new ArrayList<Integer>();
	for(int tc=1; tc<=10; tc++) {
		int n = sc.nextInt();
		arr.clear();
		for(int i=0; i<100; i++) arr.add(sc.nextInt());
		
		Collections.sort(arr);
		for(int i=0; i<n; i++) {
			if(arr.get(99)==arr.get(0)) break;
			arr.set(99, arr.get(99)-1);
			arr.set(0, arr.get(0)+1);
			Collections.sort(arr);
		}
		System.out.println("#"+tc+" "+(arr.get(99)-arr.get(0)));
	}
}

최대 최소와 그 위치를 구하기 쉬운.. 리스트 정렬이 있었다. 정답 통과 했어도 다른 사람들의 풀이를 찾아보는건 많은 도움이 된다.

 

1209. [S/W 문제해결 기본] 2일차 - Sum (D3, 67%)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV13_BWKACUCFAYh

문제를 풀 수 있는 특별한 방법이 있을까 하였지만 그냥 주어진대로 풀면 되는 문제. 2차원 배열을 돌며 각 열과 행의 합을 구하고, 각 왼쪽 오른쪽 대각선 합을 구해 최종적으로 최대값을 구하면 된다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	
	int[][] arr = new int[100][100];
	for(int tc=0; tc<1; tc++) {
		arr=new int[100][100];
		int n = sc.nextInt();
		int max = 0;
		
		for(int i=0; i<100; i++) {
			for(int j=0; j<100; j++) {
				arr[i][j]=sc.nextInt();
			}
		}

		int sum1 = 0;
		int sum2 = 0;
		int sum3 = 0;
		int sum4 = 0;
		for(int i=0; i<100; i++) {
			sum1 =0;
			sum2=0;
			for(int j=0; j<100; j++) {
				sum1 += arr[i][j];
				sum2 += arr[j][i];
			}
			sum3 += arr[i][i];
			sum4 += arr[i][99-i];
			max = Math.max(max, Math.max(Math.max(sum3, sum4), Math.max(sum1, sum2)));
		}
		
		System.out.println("#"+n+" "+max);
	}
}

 

1210. [S/W 문제해결 기본] 2일차 - Ladder1 (D3, 69%)

난 문제가 점점 어려워지는데.. 왜 정답률은 점점 더 높아질까.. 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14ABYKADACFAYh

그래도 나름 발전한게 있다면! 이전에는 이렇게 그림부터 복잡한 문제 보면 아무 생각도 못했었는데 이제는 아 그래프 순회가 필요한 문제겠구나 생각한다. 아쉽게도 혼자힘으로 완벽히 풀어내진 못했지만, 다른 풀이들 보다 그래프 순회 문제가 맞다는 것을 보고 그 뒤로 혼자 생각해서 풀었다!!

static int[][] arr;
static boolean[][] visited;
static int n;
static int[][] idxs = {{0, -1}, {0, 1}, {-1, 0}}; // 순서 중요!! 좌우 먼저 살핀 뒤 위로 올라감 
public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	
	for(int tc=1; tc<=10; tc++) {
		n = sc.nextInt();
		arr = new int[100][100];
		visited = new boolean[100][100];
		
		int x=99;
		int y=99;
		for(int i=0; i<100; i++) {
			for(int j=0; j<100; j++) {
				int input = sc.nextInt();
				if(input==2) {
					x=i;
					y=j;
				}
				arr[i][j]=input;
				
			}
		}
		
		dfs(x, y);
		
	}
}

public static void dfs(int x, int y) {
	visited[x][y]=true;
	if(x==0) {
		System.out.printf("#%d %d\n", n, y);
		return;
	} 
	
	int dx, dy;
	for(int i=0; i<3; i++) {
		dx = x+idxs[i][0];
		dy = y+idxs[i][1];
		if(dx>=0 && dx<100 && dy>=0 && dy<100 && arr[dx][dy]==1 && !visited[dx][dy]) {
			visited[dx][dy]=true;
			dfs(dx, dy);
			return;
		}
	}
}

문제 풀면서 놓쳤던 & 중요했던 부분들

• 일단 위에서부터 도착점까지 내려오는 것이 아니라 도착점에서부터 x=0인 지점까지 올라가야한다. 그게 더 빠름. 도착 지점이 정해져있기에 가능하다.
• 사다리를 아래서부터 위로 올라갈 때 이동할 수 있는 방향이 좌, 우, 상 이렇게 3가지이다. 하지만 사다리를 타고 내려올 때 보통 양 옆으로 이동 가능한지 먼저 확인 후 내려감으로, 거꾸로 갈때도 순서가 중요하다. 위로 순회하는 것보다 좌, 우로 이동 가능한지 파악하고 좌, 우로 이동하는게 더 먼저 진행되어야한다. 그래서 순회할 인덱스 정보를 저장한 idxs 배열을 위와 같은 순서로 {{0, -1}, {0, 1}, {-1, 0}} 하였다.
• 처음에 사다리를 타고 내려올 때 오른쪽으로만 이동하니까 거꾸로 올라갈땐 무조건 좌측에 사다리가 있으면 글로 이동하는 것으로 작성했다. 하지만 생각해보니.. 사다리를 타고 내려올 때 꼭 모든 가로를 거치는 것이 아니라 내려오는 루트에 따라 다르다는 것이다.. 처음 방법대로 풀땐 좌측에 1이 있으면 무조건 가로로 이동, 없으면(0이면) 위로 이동하게 하였는데 도저히 안풀려서 사람들 풀이를 찾아봤다. 사람들이 좌, 우측이동, 위로 이동 모두 순회하는 것을 보고 왜 그럴까 하고 사다리를 위에서부터 타보다 깨달았다. 그렇지만 위의 포스팅처럼 순회하는 순서는 중요하다는 것. 이거때매 꽤 오랜시간 헤매었다ㅠ

 

1211. [S/W 문제해결 기본] 2일차 - Ladder2 (D3, 69%)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14BgD6AEECFAYh

(24.08.25) 2일차까지는 모두 풀고 자려했는데.. 늦게 공부 시작해서 Ladder2는 못풀었다.. 빠른 시일 내에 추가할 예정..