이것저것 개발 블로그

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

문제)

풀이)

사실 어려운 문제는 아닌데, 구현해야 할 부분이 많다.

진짜 빡구현 문제!!

map 정보를 받은 이후, direction에 따라 dir이라는 인덱스를 초기화해준다.

또한 명령어에 따라 switch를 통해 명령을 수행한다.

이때, S명령어에서 dir에 따라 포탄을 쏘고, map에 따라 변경되는 것을 업데이트 해준다. 

코드가 길어서 좀 보기 어려울 수는 있지만, 구조 자체는 어렵지 않다.

전차가 움직이는 부분과 포탄을 쏘는 부분을 따로 함수로 만들면 더 깔끔하다!

import java.util.Scanner;
import java.io.FileInputStream;

public class Solution_D3_1873_상호의배틀필드 {

	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();

		for(int test_case = 1; test_case <= T; test_case++)
		{
			
			int H = sc.nextInt();
			int W = sc.nextInt();
			char[][] map = new char[H][W];
			char direction = '*'; // 전차 방향
			int dir=-1; // 전차 방향 인덱스 
			int x=0, y=0;	//전차 위치
			// map 입력
			for(int i=0; i<H; i++) {
				String temp = sc.next();
				for(int j=0; j<W; j++) {
					map[i][j] = temp.charAt(j);
					if(map[i][j] == '^' || map[i][j] == 'v' || map[i][j] == '<' || map[i][j] == '>') {
						direction = map[i][j];
						x = i;
						y = j;
					}	
				}
			}
			switch(direction) {
				case '^':
					dir=0;
					break;
				case 'v':
					dir=1;
					break;
				case '<':
					dir=2;
					break;
				case '>':
					dir=3;
					break;
			}
			
			// 명령어 입력
			int N = sc.nextInt();
			char[] cmd = new char[N];
			String temp = sc.next();
			cmd = temp.toCharArray();
			
			// U D L R
			//char[] d = {'U', 'D', 'L', 'R', 'S'};
			int[] dx = {-1, 1, 0, 0}; // row
			int[] dy = {0, 0, -1, 1}; //col
			
			for(int i=0; i<N; i++) {
				char c = cmd[i];
				
				switch(c) {
					case 'U':{
						dir=0;
						map[x][y] = '^';
						int nx = x + dx[dir];
						int ny = y + dy[dir];
						if(0<=nx && nx<H && 0<=ny && ny<W && map[nx][ny] == '.') {
							map[nx][ny] = map[x][y];
							map[x][y]='.';
							x=nx;
							y=ny;
						}
						break;
					}
						
					case 'D':{
						dir=1;
						map[x][y] = 'v';
						int nx = x + dx[dir];
						int ny = y + dy[dir];
						if(0<=nx && nx<H && 0<=ny && ny<W && map[nx][ny] == '.') {
							map[nx][ny] = map[x][y];
							map[x][y]='.';
							x=nx;
							y=ny;
						}
						break;
					}
						
					case 'L':{
						dir=2;
						map[x][y] = '<';
						int nx = x + dx[dir];
						int ny = y + dy[dir];
						if(0<=nx && nx<H && 0<=ny && ny<W && map[nx][ny] == '.') {
							map[nx][ny] = map[x][y];
							map[x][y]='.';
							x=nx;
							y=ny;
						}
						break;
					}
						
					case 'R':{
						dir=3;
						map[x][y] = '>';
						int nx = x + dx[dir];
						int ny = y + dy[dir];
						if(0<=nx && nx<H && 0<=ny && ny<W && map[nx][ny] == '.') {
							map[nx][ny] = map[x][y];
							map[x][y]='.';
							x=nx;
							y=ny;
						}
						break;
					}
						
					case 'S':
						int s_idx=0;
						switch(dir) {
							case 0://U
								s_idx = x;
								while(true) {
									if(s_idx-1<0 || map[s_idx-1][y]=='#')
										break;
									if(map[s_idx-1][y] == '*') {
										map[s_idx-1][y] = '.';
										break;
									}
									s_idx--;
								}
								break;

							case 1:
								s_idx = x;
								while(true) {
									if(s_idx+1>=H || map[s_idx+1][y]=='#')
										break;
									if(map[s_idx+1][y] == '*') {
										map[s_idx+1][y] = '.';
										break;
									}
									s_idx++;
								}
								break;
								
							case 2:
								s_idx = y;
								while(true) {
									if(s_idx-1<0 || map[x][s_idx-1]=='#')
										break;
									if(map[x][s_idx-1] == '*') {
										map[x][s_idx-1] = '.';
										break;
									}
									s_idx--;
								}
								break;
								
							case 3:
								s_idx = y;
								while(true) {
									if(s_idx+1>=W || map[x][s_idx+1]=='#')
										break;
									if(map[x][s_idx+1] == '*') {
										map[x][s_idx+1] = '.';
										break;
									}
									s_idx++;
								}
								break;
						}//case S
						break;
				}//switch
				
			}//cmd
			
			//출력
			System.out.print("#"+test_case+" ");
			for(int i=0; i<H; i++) {
				for(int j=0; j<W; j++) {
					System.out.print(map[i][j]);
				}
				System.out.println();
			}
			
		
		}//test_case
		sc.close();
	}//main
}

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

문제)

풀이)

바로 직전 문제를 풀면 이것도 누적합을 구해야 하겠거니~~ 는 알 것이다.

안 그럼 바로 시간초과!!

크게 두 가지로 푸는 것 같다.

첫 번째는 내가 푼 것과 같이 한 행을 기준으로 구간합을 구하고, y1 이전까지 더한 구간 합을 빼는 것이다!

그리고 그 행을 x1부터 x2까지 더해주면 끝!

이때, 입력값을 용이하게 사용하기 위해 배열은 [N+1][N+1]의 이차원 배열로 선언했다.

코드를 보면 알겠지만, 이렇게 해도 시간 초과가 나와서, 최대한 시간을 줄이기 위해 노력했다.

bufferedreader, stringbuilder를 사용하여 입력, 출력 모두 시간 단축을 했다!

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
//import java.util.Scanner;

public class Main_BJ_11660_구간합구하기5 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		//Scanner sc = new Scanner(System.in);
//		int N = sc.nextInt();
//		int M = sc.nextInt();
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int[][] arr = new int[N+1][N+1];
		for(int i=1; i<N+1; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<N+1; j++) {
				//arr[i][j] = arr[i][j-1]+sc.nextInt();	//행별로 누적합
				arr[i][j] = arr[i][j-1] + Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=0; i<M; i++) {
//			int x1 = sc.nextInt();
//			int y1 = sc.nextInt();
//			int x2 = sc.nextInt();
//			int y2 = sc.nextInt();
			st = new StringTokenizer(br.readLine());
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());
			
			int sum = 0;
			for(int k=x1; k<=x2; k++) {
				//y2있는곳까지 누적합 - y1 전 위치까지 누적합 => 각 행마다 반복
				sum+=arr[k][y2]-arr[k][y1-1];
			}
			sb.append(sum + "\n");
			//System.out.println(sum);	
		}
		System.out.println(sb);	//시간초과 없애기..
		//sc.close();

	}

}

두 번째 방법은 DP를 사용한, 구글링을 하면 많이 나오는 방법이다.

https://subbak2.com/m/65

이 분의 글을 보고 이해했다.

그림 잘 그려주셔서 이해가 쉬웠다!

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

public class Main_BJ_11660_구간합구하기5_2 {

	static int[][] arr; // 입력 배열
	static int[][] dp; // dp [i][j] = (1,1)에서 (i,j) 까지의 합

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
        //입력
		arr = new int[N+1][N+1];
        dp = new int[N + 1][N + 1];
		for(int i=1; i<N+1; i++) {
        	st = new StringTokenizer(br.readLine());
        	for(int j=1; j<N+1; j++){
            	arr[i][j] = Integer.parseInt(st.nextToken());
            }
          }

		// DP: dp[i][j] = (1,1)에서 (i,j)까지의 합
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				// (왼쪽← 값) + (위에↑ 값) - (↖중복되는 대각선 값) + (인풋값)
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j];
			}
		}

		// 정답 구해서 출력
		int x1, y1, x2, y2;
		for (int i = 1; i <= M; i++) {
			st = new StringTokenizer(br.readLine());
			x1 = Integer.parseInt(st.nextToken());
			y1 = Integer.parseInt(st.nextToken());
			x2 = Integer.parseInt(st.nextToken());
			y2 = Integer.parseInt(st.nextToken());

			sb.append((dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1]) + "\n");
		}
		System.out.println(sb);
	}
}

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

문제)

풀이)

당연히 가장 쉬운 것은 배열을 입력받아 구간 합을 구하는 것이지만, 당연히 시간 초과가 난다.

따라서 입력을 받으면서 더해가는 방식으로 진행했다.

일차원 배열이므로 누적합을 구하는건 간단하다!

결국 구간 합을 구하기 위해선 마지막 인덱스까지 구한 누적 합 - 처음 인덱스까지 구한 누적 합으로 작성하면 된다!

원래 입력받은 배열

누적합

3 ~ 7까지 구간합

28 - 6 = 22

import java.util.Scanner;

public class Main_BJ_11659_구간합구하기4 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		int[] arr = new int[N+1];
		//누적합 구하기
		for(int i=1; i<=N; i++) {
			arr[i] = arr[i-1] + sc.nextInt();
		}
			
		for(int i =0; i<M; i++) {
			int start = sc.nextInt();
			int end = sc.nextInt();
			System.out.println(arr[end]-arr[start-1]);
		}
		
		sc.close();

	}

}

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

문제)

풀이)

이 문제는 방향을 바꾸는데 신경을 조금 쓰면 해결되는 문제다.

먼저, 시계방향으로 계속 회전하며 전진하므로 오른쪽, 아래, 왼쪽, 위를 반복하면서 간다.

따라서, 해당 방향을 유지하다 index가 map 범위 밖으로 나가거나, map에 숫자가 채워져 있으면 방향을 바꾸면 된다.

또한 숫자는 입력받은 n의 제곱만큼의 숫자가 채워지므로, whlie문 탈출 조건을 이것으로 정했다.

import java.util.Scanner;

public class Solution_D2_1954_달팽이숫자 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();

		for(int test_case = 1; test_case <= T; test_case++){
			int n = sc.nextInt();
			int[][] map = new int[n][n];
			int num = 1;
			// right, down, left, up
			int[] dx= {0,1,0,-1};
			int[] dy= {1,0,-1,0};
			int idx=0;
			int x=0;
			int y=0;
			
			while (num<=n*n) {	// 숫자를 다 채울 때까지
                //map 범위 내인가? 맞으면 채우고, 다음 곳으로
				if(0<=x && x<n && 0<=y && y<n && map[x][y]==0) { 				
                	map[x][y] = num;
					x += dx[idx%4];
					y += dy[idx%4];
					num++;
				}
				else {
					//범위 내가 아닐 때, 한 칸 더 계산되었으므로 원상태 복구 
					x -= dx[idx%4];
					y -= dy[idx%4];
                    //방향 틀기
					idx+=1;
					x += dx[idx%4];
					y += dy[idx%4];
				}
					
			}//while
			
			
			System.out.println("#"+test_case);
			for(int i=0; i<n; i++) {
				for(int j=0; j<n; j++) {
					System.out.print(map[i][j]+" ");
				}
				System.out.println();
				
			}	
		}//test_case
		sc.close();
	}//main
}

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

문제)

풀이)

이 문제는 목적지에서 거꾸로 원하는 장소를 찾아가면 된다!

즉, 아래에서 위로 올라가므로 행의 값은 -1을 계속 해주고, 왼쪽 또는 오른쪽에 길이 있으면 전체 범위 내에서 길이 있을 때까지 반복해서 전진한다.

이때, 내 코드에서는 이미 한 번 더 더했으므로, 빼주는 작업이 필요하다!

마지막으로, 행인 x의 값이 0이면 끝났으므로 탈출!

y값을 출력해주면 답이다.

//import java.io.FileInputStream;
import java.util.Scanner;

public class Solution_D4_1210_Ladder1 {

	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("input2.txt"));
		Scanner sc = new Scanner(System.in);
		for(int test_case = 1; test_case <= 10; test_case++)
		{
			int tc = sc.nextInt();
			int x=0;
			int y=0;
			int[][] ladder = new int[100][100];
			for(int i=0; i<100; i++) {
				for(int j=0; j<100; j++) {
					ladder[i][j] = sc.nextInt();
					if (ladder[i][j] == 2) {
						x=i;
						y=j;
					}
				}
			}
			
			// 좌, 우
			int[] dx= {0, 0};
			int[] dy= {-1, 1};
			int nx=0;
			int ny=0;
			while(true) {
				//전진
				x -= 1;
				//y=y;
				
				//좌, 우 살피기
				for(int i=0; i<2; i++) {
					nx = x + dx[i];
					ny = y + dy[i];
					
					if(0<=nx && nx<100 && 0<=ny && ny<100 && ladder[nx][ny]==1) {
						while(0<=nx && nx<100 && 0<=ny && ny<100 &&ladder[nx][ny]==1) {
							nx += dx[i];
							ny += dy[i];
						}
						//한 칸 더 갔으므로 빼주기
						x=nx-dx[i];
						y=ny-dy[i];
						break;
					}
				}
				
				if(x==0)	//맨 위므로 정답 찾았다!
					break;
			}
			System.out.println("#"+test_case+ " "+y);		
		}
		sc.close();
	}
}

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

문제)

풀이)

이 문제는 말 그래도 평탄했다.

다만 좀 오래 걸렸던 부분이 있었는데, 그냥 dumpNum 줄여가면서 하나씩 빼면 되는데 괜히 횟수 줄여보겠다고 옆자리 애랑 비교하고 난리났다.

어차피 sort하면 작은 애가 앞으로 올 것이고, 같은애가 여러개 있더라도 더해지면 다시 작은 애가 앞으로 올 것인데 그걸 생각 못했다.

어쨌든, 정렬을 통해 오름차순으로 줄세워두고, 맨 뒤에서 하나를 빼 맨 앞으로 넘기는 작업을 반복했다.

그리고, flatten 됨을 확인까지 한다면, 쓸데없이 빼는 작업을 줄일 수 있다!

확인하는 작업은, 정렬 후 맨 앞과 맨 끝의 높이 차이가 0 또는 1인지만 확인하면 된다.

//import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class Solution_D3_1208_Flatten {

	public static void main(String[] args) throws FileNotFoundException {
		//System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		for(int test_case = 1; test_case <= 10; test_case++){
			int dumpNum = sc.nextInt();
			int[] arr = new int[100];
			for(int i=0; i<100; i++) {
				arr[i]=sc.nextInt();
			}
			
			Arrays.sort(arr);
			while(dumpNum>0) {
				if(arr[99]-arr[0]==0 || arr[99]-arr[0]==1)
					break;
				arr[99]-=1;
				arr[0]+=1;
				dumpNum--;
				Arrays.sort(arr);
			}
			int answer = arr[99]-arr[0];
			
			System.out.println("#"+test_case+" "+answer);
		}
		sc.close();
	}

}

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

문제)

풀이)

이 문제는 재귀의 간단한 문제다.

글에서도 알 수 있지만, "____"이 문자로 어디에서 재귀가 호출되었는지 알 수도 있다.

나는 print, recursion이라는 함수를 따로 만들었다.

하지만 print 대신 언더바를 출력하는 string을 초기에 ""로 하고, "____"를 점점 더하는 방식도 코드가 깔끔하니 예쁘다.

import java.util.Scanner;

public class Main_BJ_17478_재귀함수가뭔가요 {
	public static void _print() {
		System.out.print("____");
	}
	public static void recursion(int cnt, int line) {
		for(int i=0; i<line; i++)
			_print();
		System.out.println("\"재귀함수가 뭔가요?\"");
		
		if(cnt > 0) {
			for(int i=0; i<line; i++)
				_print();
			System.out.println("\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.");
			
			for(int i=0; i<line; i++)
				_print();
			System.out.println("마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.");
			
			for(int i=0; i<line; i++)
				_print();
			System.out.println("그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"");
			
			recursion(cnt-1, line+1);
		}
		else {
			for(int i=0; i<line; i++)
				_print();
			System.out.println("\"재귀함수는 자기 자신을 호출하는 함수라네\"");	
		}
		
		for(int i=0; i<line; i++)
			_print();
		System.out.println("라고 답변하였지.");
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int cnt = sc.nextInt();
		int line = 0;
		System.out.println("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.");
		recursion(cnt, line);
		
		sc.close();
	}

}

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

문제1)

풀이)

일단, java가 어색해서 입력받는 부분이 이상할 수 있다는 점을 고려해주세요... 담에는 더 개선시켜 올게요..ㅠ

(입력 받는거는 저보다 잘 하겠죠...)

논리만 보자면, 남학생은 간단하다.

받은 수의 배수만 바꿔주면 되므로, 조건식에서 받은 숫자만 더해주면서 변경하면 끝!!

여자가 조금 까다로울 수 있는데,

먼저, 받은 스위치의 위치를 기준으로 왼쪽 또는 오른쪽의 개수를 센다.

이유는, for문을 돌릴때 조건식을 작성하기 위해!

-> 왼쪽이 적을 경우, 중심에서 점점 멀어지면서 가장 먼저 끝에 닿는 쪽이 왼쪽이기 때문에, 인덱스가 0이상임을 조건을 걸어야 한다.

-> 오른쪽이 적을 경우, 인덱스가 맨 끝보다 작아야 함을 조건에 명시해야 한다.

이때, 받은 스위치는 무조건 변경해야 하므로 잊지 말고 변경하기!!

변경할 때 남자와 마찬가지로 1, 0 여부를 판단하고 바꿔도 된다.

하지만 어차피 0, 1 인데 무조건 빼고 절댓값으로 만들면 되기에 이렇게 계산했다.

그리고 마지막 출력!!! 이부분에서 애를 먹었는데...

20개 단위로 출력되어야 하기 때문에 개행, 띄어쓰기, 숫자 출력을 잘 해줘야 한다.

이 부분만 주의한다면 완성!!

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


public class Main_BJ_1244_스위치켜고끄기 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine()); // 스위치 개수 
		int [] sw = new int [n];
		
		String str = br.readLine();	// 스위치 상태
		StringTokenizer st = new StringTokenizer(str, " ");
		
		for(int i =0; i<n; i++) {
			sw[i]=Integer.parseInt(st.nextToken());	//스위치 상태 배열에 저장
		}
		
		int students = Integer.parseInt(br.readLine());	//학생 수 
		for(int i =0; i<students; i++) {
			str = br.readLine();
			st = new StringTokenizer(str, " ");
			int sex = Integer.parseInt(st.nextToken());	// 셩별
			int num = Integer.parseInt(st.nextToken());	// 받은 수 
			
			if (sex == 1) {	//남성 
				for(int j = num-1; j<sw.length; j=j+num) {
					if (sw[j]==1) 	//켜져있으면 끄고 
						sw[j]=0;
					else 	//꺼져있으면 킨다 
						sw[j]=1;
				}
			}
			
			else {	// 여성 
				int left = num; // 받은 스위치기준 왼쪽개수
				int right = n-num-1; //받은스위치 오른쪽개수 
				sw[num-1] = Math.abs(sw[num-1]-1);	//일단 받은 스위치 상태 변경 
				
				if(left > right) {	//왼쪽 개수가 더 많으면 
					//인덱스로 따졌을 때, 왼쪽 시작은 num-2, 오른쪽은 num. 오른쪽이 더 적으므로 오른쪽 조건만 고려
					for(left = num-2, right=num; right<n; left--, right++) {
						if(sw[left] == sw[right]) {	//왼쪽과 오른쪽이 같으면 스위치 상태 변경
							sw[left] = Math.abs(sw[left]-1);
							sw[right] = Math.abs(sw[right]-1);
						}
						else 	// 안 같으면 탈출
							break;
						
					}
				}//if
				
				else {	//오른쪽 개수가 더 많으면
					//이번에는 왼쪽이 더 적으므로, 왼쪽 조건만 고려 
					for(left = num-2, right=num; left>=0; left--, right++) {
						if(sw[left] == sw[right]) {
							sw[left] = Math.abs(sw[left]-1);
							sw[right] = Math.abs(sw[right]-1);
						}
						else //다르면 탈출 
							break;
						
					}
				}//else
			}//else_여성
			
		}//학생들 경우의 수
		
		for(int i = 0; i<sw.length; i++) {	//출력
			//20개씩 끊어야 함을 주의
			if(i!= 0 && i % 20 == 0) {
				System.out.println();
			}
            if(i%20 != 0){
               	System.out.print(" ");
            }
            System.out.print(sw[i]);
		}

	}

}

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

문제)

풀이)

간단하게 생각했다!!

앞에서부터 1을 찾고, 찾으면 다음부터는 모두 그 반대로 만들어주는 것으로 짰다.

바꿔준 후 count를 하나 올려주었다.

물론, 이렇게 하면 바꿔줄 것이 많아서 데이터가 정말 많아지먄 나중엔 시간초과가 날 수 있다.

import java.util.Scanner;

public class swea1289 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++){
			String s = sc.next();
			int count = 0;
			char[] arr = s.toCharArray();
			for(int i =0; i<s.length(); i++) {
				if(arr[i] == '1') {
					arr[i] = '0';
					for(int j=i+1; j<s.length(); j++) {
						if(arr[j] == '1') 
							arr[j] = '0';
						else
							arr[j] = '1';
					}
					count += 1;
				}
			}
			System.out.println("#"+test_case+" "+count);
		}//test_case
	}//main
}//class

따라서 수정해본 코드!

처음에 1을 만나면, 일단 바꿔줘야 하므로 count를 +1 한다.

그리고 그 다음부터 그 자리와 옆 자리가 다르면 +1을 계속 해주었다.

왜냐하면!

101 -> 010 -> 001 -> 000 (answer: 3)

001101-> 000010 -> 000001 -> 000000 (answer: 3)

위의 예시에서 볼 수 있듯, 옆 자리의 숫자가 나와 다른 경우에만 count가 늘어남을 알 수 있다.

따라서, 모든 수를 바꿔줄 필요 없이 내 옆자리가 나와 다른 경우를 찾아보면 된다!

import java.util.Scanner;

public class swea_1289 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++){
			String s = sc.next();
			int size = s.length();
			int count=0;  									//횟수
			if(s.startsWith("1")) {
				count++;
			}
			for (int i = 0; i <size-1; i++) {
				if(s.charAt(i) != s.charAt(i+1)) {
					count++;
				}
			}		
			System.out.println("#"+test_case+" "+ count);
			
		}//테스트 케이스
		sc.close();
	}//main
}

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

문제)

풀이)

파악해야 하는 것

1. 어떻게 연속된 바둑알을 찾아낼 것인가

2. 6개 이상 연속된 바둑알을 어떻게 찾아낼 것인가

1. 연속된 바둑알 찾아내기

좌측 상단부터 바둑알을 찾아낼 것이기 때문에 8방향을 모두 살펴볼 필요 없이,

하, 우, 우상, 우하 방향만 보면 된다.

그리고 연속된 5개의 바둑알을 찾기 위해 다음 좌표를 같은 방향으로 반복문을 돌려준다.

2. 6개의 연속된 바둑알 찾아내기

6개의 연속된 바둑알은 두 가지로 생각했다.

1) 바라보는 방향에서 연속된 6개의 바둑알

2) 바라보는 방향에서 연속된 5개의 바둑알

+ 기준점에서 반대 방향으로 같은 색의 바둑알 존재

1)을 해결하기 위해,

for문을 5번 돌려 count 값이 5인지 6인지 확인한다.

6일 경우, 연속된 돌이 6개 있다는 것!

2)를 해결하기 위해,

count값이 5일 때, 기준점에 있던 돌의 반대편에 다른 돌이 있는지 체크한다.

이때, 반대편 돌이 map 범위 내에 없다면 5개가 확정!!

map 범위 내에 있다면 같은 색인지 아닌지 체크하면 된다.

만약, 같은 색이라면 연속된 돌이 6개 있다는 것!

코드)

import java.util.Scanner;

public class Main_BJ_2615_오목 {

	public static void main(String[] args) throws Exception{
		//System.setIn(new FileInputStream("Test5.txt"));
		Scanner sc = new Scanner(System.in);
		
        // input 받아오기
		int[][] map = new int[19][19];
		for(int i=0; i<19; i++) {
			for(int j=0; j<19; j++) {
				map[i][j] = sc.nextInt();
			}
		}
        
		// 하 우 우상 우하
		int[] dx = {1, 0, -1, 1};
		int[] dy = {0, 1, 1, 1}; 
		for (int i=0; i<19; i++) {
			for(int j=0; j<19; j++) {
            	// 바둑알 존재 여부
				if(map[i][j] == 1 || map[i][j] == 2) {
					int nx=i;
					int ny=j;
					for(int k=0; k<dx.length; k++) {
                    	// 다음 좌표 초기화 및 바둑알 개수 초기화
						int count=1;
						nx=i;
						ny=j;
                        
                        // 연속되게 바둑알이 있는지 확인
                        // 5번을 탐색하여 기준 돌로부터 그 방향에 돌 5개인지 6개인지 판단
						for(int c=0; c<5; c++) {
							nx = nx+dx[k];
							ny = ny+dy[k];
							
							if(0<=nx && nx<19 && 0<=ny && ny<19) {
								if(map[nx][ny] == map[i][j])
									count+=1;
								else
									break;
							}
							else
								break;
						}
						if (count == 5) {
                        	// 5개의 돌이 있는지 확인 후, 기준점의 반대편에 돌이 있는경우 확인	
							if(i-dx[k]>=0 && j-dy[k]>=0 && i-dx[k]<19 && j-dy[k]<19) {
                            	//돌이 map 내에 존재, 기준 바둑알과 일치하면 6개가 됨
								if(map[i-dx[k]][j-dy[k]]==map[i][j]) 
									continue;
                                //돌이 map 내에 존재, 기존 바둑알과 일치하지 않으면 5개가 됨
								else {
									System.out.println(map[i][j]);
									System.out.println((i+1)+ " " +(j+1));
									System.exit(0);
								}									
							}
                            
                           //이전 돌이 map 내애 존재하지 않는다면 연속된 돌 5개 확정.
							else {
								System.out.println(map[i][j]);
								System.out.println((i+1)+ " " +(j+1));
								System.exit(0);
							}
						}
						// 바둑알 6개 존재(기준점보다 앞에 존재) 혹은 5개 미만	
						else
							continue;
							
					}
				}
			}
		}
    // 승부가 나지 않았을 때
	System.out.println(0);
	}

}