자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 1. 문자열(3)

 

9. 숫자만 추출

 

<나의 풀이>

- Character.isDigit(문자형 변수): 해당 문자가 숫자이면 true, 아니면 false 반환

- 맞으면 새 문자열에 이어 붙인뒤, 마지막에 정수 변환하여 출력

import java.util.Scanner;

public class Ex1_9 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		String str=sc.nextLine();
		String nStr="";
		for(char c:str.toCharArray()) {
			if(Character.isDigit(c)) {
				nStr+=c;
			}
		}
		
		System.out.println(Integer.parseInt(nStr));
	}

}

 

<해설>

- 숫자 아스키코드: 48~57 사이의 수

import java.util.Scanner;

public class Main {
	
	public int solution(String s) {
		int answer=0;
		
		for(char x:s.toCharArray()) {
			if(x>=48&&x<=57) answer=answer*10+(x-48); //x-48 : 0
		}
		
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		String str=sc.nextLine();
		System.out.println(T.solution(str));
	}

}

 

 

---

 

 

10. 가장 짧은 문자거리

 

<나의 풀이>

- 문자 c 가 있는 index를 list형 변수 list에 저장

- left, right 변수에 문자c가 있는 첫번째 index와 두번째 index를 각각 저장한다.

- 문자열 str을 처음부터 돌면서 각각 문자c와의 최소거리를 계산하여 저장한다.

- left, right와 idx가 같으면 0을 저장한다.

- right와 같을 때는 left, right를 각각 다음 문자c가 있는 index로 변환해준다.

package inflearn_java;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Ex1_10 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		String line=sc.nextLine();
		
		StringTokenizer st=new StringTokenizer(line);
		String str=st.nextToken();
		char c=st.nextToken().charAt(0);
		
		List<Integer> list= new ArrayList<>();
		
		int i=0;
		for(char s:str.toCharArray()) {
			if(s==c) {
				list.add(i); //인덱스 삽입
			}
			
			i++;
		}

		int idx=0;
		int left=list.get(0);
		int right=list.get(1);
		int list_idx=2;
		StringBuilder sb= new StringBuilder();
		
		while(idx<str.length()) {
			
			if(left==idx) {
				sb.append(0+" ");
			}else if(right==idx){
				sb.append(0+" ");
				
				if(list_idx<list.size()) {
					left=right;
					right=list.get(list_idx++);
				}
			}else{
				int min= Math.min(Math.abs(left-idx), Math.abs(right-idx));
				sb.append(min+" ");
			}
			
			idx++;
		}
		
		System.out.println(sb.toString());
		
		
	}

}

 

<해설>

- 왼쪽 c로부터의 거리를 구해서 모든 값을 만듬(answer 배열)

- 오른쪽 c로부터의 거리를 구하는데, answer에 저장한 값과 해당 값을 비교해서 작은 값이 채택

import java.util.Scanner;

public class Main {
	
	public int[] solution(String s, char t) {
		int[] answer=new int[s.length()];
		
		//왼쪽 t부터의 거리
		int p=1000;
		for(int i=0;i<s.length();i++) {
			if(s.charAt(i)==t) {
				p=0;
				answer[i]=p;
			}else {
				p++;
				answer[i]=p;
			}
		}
		
		//오른쪽 t부터의 거리
		p=1000;
		for(int i=s.length()-1;i>=0;i--) {
			if(s.charAt(i)==t) {
				p=0;
			}else {
				p++;
				
				answer[i]=Math.min(answer[i], p);
			}
		}
		
		
		return answer;
	}
	
	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		String str=sc.next();
		char c=sc.next().charAt(0);
		for(int x:T.solution(str,c)) {
			System.out.print(x+" ");
		}
	}
}

=> 생각해내기엔 풀이가 더 간단하지만, 해당 loop 를 두번 돌아야하기에 조금더 비효율적

=> 하지만 O(N)= O(2N)이니 시간복잡도가 동일하여 컴퓨터에게는 비슷할 것 같음

 

---

 

 

11. 문자열 압축

 

<나의 풀이>

- 문자열을 한글자씩 가져온다.

- 이전 문자와 현재 문자가 같으면 cnt +1

- 다르면 cnt가 1보다 크면 cnt값 출력 후, 새로운 문자 출력 후 cnt값 1로 reset, 이전 문자를 새로운 문자로 변경'

- 마지막에 문자가 여러개 일 경우 세고 있던 값(cnt) 출력해줘야함

import java.util.Scanner;

public class Ex1_11 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		String str=sc.nextLine();
		
		char ch=' ';
		int cnt=1;
		String nStr="";
		
		for(char c:str.toCharArray()) {
			if(c==ch) {
				cnt++;
			}else {
				if(cnt>1) nStr+=cnt;
				
				nStr+=c;
				cnt=1;
				
				ch=c;
			}
			
		}
		
		if(cnt>1) nStr+=cnt;
		
		System.out.println(nStr);
	}

}

 

 

<해설>

- 문자와 다음 문자가 같은지 비교하여, 같으면 cnt++

- 다르면 해당 문자를 출력하고, 여태까지 더한 cnt값을 뒤이어 출력한 뒤, cnt값을 1로 초기화

import java.util.Scanner;

public class Main {

	public String solution(String s) {
		String answer="";
		s+=" ";
		int cnt=1;
		for(int i=0;i<s.length()-1;i++) {
			if(s.charAt(i)==s.charAt(i+1)) cnt++;
			else {
				answer+=s.charAt(i);
				if(cnt>1) answer+=String.valueOf(cnt);
				cnt=1; //초기화
			}
		}
		
		return answer;
	}
	
	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		String str=sc.nextLine();
		
		System.out.println(T.solution(str));
		
	}

}

=> 미리 다음문자와 비교하는 게 생각하기에 더 단순한듯 ! 

 

 

---

 

12. 암호

 

<나의 풀이>

- 7자코드 -> 7자씩 끊어서 sol함수로 전달

- sol 함수는 해당문자로 해석하여 문자 전달

- Integer.parseInt(문자열,n진수): 해당 n진수 문자열을 10진수로 반환

import java.util.Scanner;

public class Main {
	
	public static char sol(String s) {
		char c = ' ';
		String str="";
		
		for(char charS:s.toCharArray()) {
			if(charS=='#') str+='1';
			else str+='0';
		}
		
		c= (char)Integer.parseInt(str, 2); //2진수->10진수
		
		return c;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n=Integer.parseInt(sc.nextLine());
		String str=sc.nextLine();
		StringBuilder sb = new StringBuilder();
		
		for(int i=0;i<n;i++) {
			String s= str.substring(i*7,(i*7)+7);
			sb.append(sol(s));
		}
		
		System.out.println(sb.toString());
	}

}

 

 

참고)

https://dpdpwl.tistory.com/92

[Java]자바 진수변환(10진수->2진수,8진수,16진수)

 

<해설>

- 문자열. replace('문자1','문자2') : 문자1을 문자2로 변환 

import java.util.*;
class Main {	
	public String solution(int n, String s){
		String answer="";
		for(int i=0; i<n; i++){
			String tmp=s.substring(0, 7).replace('#', '1').replace('*', '0');
			int num=Integer.parseInt(tmp, 2);
			answer+=(char)num;
			s=s.substring(7);
		}
		return answer;
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		String str=kb.next();
		System.out.println(T.solution(n, str));
	}
}

- String클래스가 제공하는 replace()메소드를 통해, 한글자씩 확인하여 교체하지 않아도 된다.!