[프로그래머스(Programmers)][자바(java)] (Lv3) 브라이언의 고민

728x90

https://programmers.co.kr/learn/courses/30/lessons/1830

코딩테스트 연습 - 브라이언의 고민

브라이언의 고민 알림: '실행'을 눌렀을 시 올바른 코드가 틀린 결과로 표시되는 경우가 있습니다. 하단의 설명을 참고해주세요. 카카오스토리의 개발자 브라이언에게 최근 고민이 생겼다. 하루

programmers.co.kr

문제 풀이

< 코드 >

import java.util.*;

public class Solution {
	
	char[] sentence;
	
	class Word {
		int rule, start, end;
		public Word(int rule, int start, int end) {
			this.rule = rule;
			this.start = start;
			this.end = end;
		}
	}
	
	public String solution(String s) {
    
		sentence = s.toCharArray();
        
		String invalid = "invalid";
        
		/** 기호 위치 파악 **/
		LinkedHashMap<Character, List<Integer>> chars = new LinkedHashMap<>(); // charater's positions
		int len = s.length(), i; char c;
		for (i = 0; i < len; ++i) {
			c = sentence[i];
			// if (c == ' ') return invalid; // [X] 공백 존재
			if (c >= 'a' && c <= 'z') { // Character.isLowerCase(c)
				if (!chars.containsKey(c))
					chars.put(c, new ArrayList<>());
				chars.get(c).add(i);
			}
		}
		// if (positions.size() == 0) return sentence; // 기호 없음
        
		/** 기호의 규칙과 단어의 시작, 끝 인덱스 파악 **/
		List<Word> words = new ArrayList<>(); // word's rule, range
		int start_str = 0, 
			start_char, end_char, start_char_pre = -1, end_char_pre = -1, 
			start_word = 0, end_word = 0, end_word_pre = -1,
			num, rule = -1, distance; boolean isDistance2;
		for (List<Integer> positions : chars.values()) {
			num = positions.size();
			start_word = start_char = positions.get(0);
			end_word = end_char = positions.get(num - 1);
			isDistance2 = true;
			for (i = 1; i < num; i++) {
				distance = positions.get(i) - positions.get(i - 1);
				if (distance < 2) return invalid; // [X] 기호가 연속으로 붙어있음 (예외 1)
				if (distance > 2) {
					isDistance2 = false;
					break;
				}
			}
			if (num >= 3 && !isDistance2) return invalid; // [X] 규칙 1 - 간격 2 아님 (예외 2)
			if (num == 1 || num >= 3) {
				rule = 1;
				start_word--;
				end_word++;
				if (start_word < 0 || len <= end_word) return invalid; // [X] 규칙 1 - 맨 앞/뒤 글자 없음 (예외 3)
			}
			if (num == 2)
				rule = isDistance2 ? 0 : 2; // 규칙 0 => 규칙 1 또는 2
			if (start_char_pre < start_char && end_char < end_char_pre) {
				if (rule == 2) return invalid; // [X] 규칙 2 - 한 단어에 같은 규칙 2번 적용 (예외 4)
				continue; // 규칙 2 안에 규칙 1
			}
			if (end_word_pre >= start_word) return invalid; // [X] 단어 범위 안 맞음 (예외 5)
			words.add(new Word(rule, start_word, end_word));
			start_char_pre = start_char;
			end_char_pre = end_char;
			end_word_pre = end_word;
		}
        
		/** 기호를 제외한 단어 이어붙이기 **/
		StringBuilder answer = new StringBuilder();
		int size = words.size(); Word word;
		for (i = 0; i < size; ++i) {
			word = words.get(i);
			rule = word.rule;
			start_word = word.start;
			end_word = word.end;
			if (rule == 0) { // 규칙 1 또는 2
				if ((start_str <= start_word - 1) && (end_word + 1 < (i < size - 1 ? words.get(i + 1).start : len))) { // 규칙 1
					start_word--;
					end_word++;
				}
			}
			if (start_str < start_word)
				answer.append(getStr(start_str, start_word - 1));
			answer.append(getStr(start_word, end_word));
			start_str = end_word + 1;
		}
		if (start_str < len)
			answer.append(getStr(start_str, len - 1));
		return answer.toString().trim();
	}

	public String getStr(int start, int end) {
		StringBuilder str = new StringBuilder(); char c;
		for (int i = start; i <= end; ++i) {
			c = sentence[i];
			if (c >= 'A' && c <= 'Z')
				str.append(c);
		}
		return str.toString() + " ";
	}
}

< 변수, 객체 설명 >

Type	Name	Description
String	s	입력 받은 문장
char[]	sentence	입력 받은 Struing s를 char[] 로 변환한 것
int	start_string	현재 문자열의 시작 인덱스
	start_word	현재 단어의 시작 인덱스
	end_word	현재 단어의 끝 인덱스
	start_word_pre	이전 단어의 시작 인덱스
	end_word_pre	이전 단어의 끝 인덱스
	start_char	현재 기호의 시작 인덱스
	end_char	현재 기호의 끝 인덱스
	start_char_pre	이전 기호의 시작 인덱스
	end_char_pre	이전 기호의 끝 인덱스
	num	각 기호의 개수
	distance	기호 간 간격
	rule	규칙

< 풀이 과정 >

1. 기호( 소문자 ) 위치 파악

- 입력받은 문자열을 char[]로 변환한 sentence를 순차적으로 탐색
- 기호의 위치들을 저장할 연결된 해시 맵 생성. 기호를 key로 하고 그 기호의 위치 리스트를 value로 한다.
( LinkedHashMap<Character, List<Integer>> chars )
( 연결된 해시 맵 -- 데이터를 넣은 순서대로 탐색하기 위함 )
- 기호를 찾을 때마다 chars에는 key에 기호, value에 그 위치(인덱스)들을 넣는다
- 기호가 없으면 문자열 그대로 리턴

2. 기호의 규칙과 단어의 시작, 끝 인덱스 파악

- 단어의 규칙( rule ), 시작 인덱스( start ), 끝 인덱스( end )로 구성된 Word Class 생성
- 단어들의 규칙과 위치하는 구간의 범위를 저장할 리스트 생성 ( List<Word> words )
- 연결된 해시 맵( chars )을 순차적으로 탐색
- 한 기호의 위치들( List<Integer> positions : chars.values() )에 대해 규칙과 단어의 시작, 끝 인덱스 판단 후
Word word를 생성하여 words에 차례로 담음

※ 기호의 개수( num = positions.size() )가 2개 이상이고 간격이 1 인 경우 ( = 한 기호가 연속으로 붙어 있는 경우 )
⇒ invalid (예외 1)
ex) A a a / a a A / ...

※ 기호의 개수가 3개 이상 이고, 각각의 위치 간격이 2 보다 큰 경우
⇒ invalid (예외 2)
ex) A a A A a A a / ...

  1)  기호( 소문자 )의 개수가 1개 또는 3개 이상  ⇒  규칙 1
     (1)  기호의 개수가 1개
        ex) A a A / ...
     (2)  기호의 개수가 3개 이상 이고, 각각의 위치 간격이 2
        ex) A a A a A a A / ...
     0 1 2 3 4 5 6
- 기호의 첫 위치 : 1
- 기호의 마지막 위치 : 5
- 단어의 시작 위치 : 0
- 단어의 끝 위치 : 6
*  단어 시작 인덱스 = 기호 시작 인덱스 - 1 ( start_word  = start_char - 1 )
*  단어 끝 인덱스 = 기호 끝 인덱스 + 1 ( end_word  = end_char + 1 )

※ 기호가 1개이거나, 3개 이상이고 기호 간의 간격이 2 여서 규칙 1 의 조건을 만족하나
단어 시작 인덱스나 단어 끝 인덱스가 다른 단어와 겹치거나 범위를 벗어나는 경우
⇒ invalid (예외 3)
ex) □ a A / A a A a A a □ / b B B B b a A a A a □ / ...

  2)  기호의 개수가 2개
     (1)  간격이 2 인 경우  ⇒  규칙 0 ( 규칙 1 이 될 수도 있지만 일단 규칙 2 적용 )
ex)  ? a A a ?
     (2) 간격이 2 보다 큰 경우  ⇒  규칙 2
        ex)  a A A A A a / ...
     0 1 2 3 4 5
- 기호의 첫 위치 : 0
- 기호의 마지막 위치 : 5
- 단어의 시작 위치 : 0
- 단어의 끝 위치 : 5
*  단어 시작 인덱스 = 기호 시작 인덱스 ( start_word  = start_char )
*  단어 끝 인덱스 = 기호 끝 인덱스 ( end_word  = end_char )

※  규칙 2 인 다른 기호 사이에 존재
(1) 규칙 2 인 경우 ( = 한 단어에 대해 같은 규칙 중복 적용 )  ⇒  invalid  (예외 4)
ex)  b a A A A a b / b A a A A A a A b / ...
(2) 나머지 경우  ⇒  words에 추가하지 않음 ( 이미 규칙 2 단어로 들어가 있음 )
ex)  b A a A a A b, ...

※ 이전 단어 끝 인덱스( end_word_pre )가 현재 단어 시작 인덱스( start_word )보다 크거나 같은 경우
( = 단어가 서로 겹치는 경우 )
⇒ invalid (예외 5)
ex) B b B b B a A a A a A / ...

3. 기호를 제외한 단어를 이어붙이고 공백을 추가하여 하나의 문자열 완성

- words 리스트의 단어들을 순차적으로 탐색
- 현재 단어의 규칙이 0인 경우 ( 규칙 1이 될 수도 있지만 일단 규칙 2를 적용 ( ex) ? a A a ? ) )
현재 단어의 시작 인덱스의 이전, 끝 인덱스의 이후에 여분의 문자가 있으면 규칙 1을 적용
- 단어의 시작, 끝 인덱스 범위의 구간에서 기호( 소문자 )를 제외한 문자들을 이어붙임 ( + 마지막에 공백 )

4. 이어붙인 문자열을 후행 공백 제거( trim() ) 후 리턴

< 통과 확인 >

<< 수정 전 코드 >>

< 코드 >

import java.util.*;

public class Solution {
	
	char[] sentence;
	
	public String solution(String s) {
    
		sentence = s.toCharArray();
        
		String invalid = "invalid";
        
		try {
			/** 기호 종류, 위치 파악 **/
			LinkedHashMap<Character, List<Integer>> chars = new LinkedHashMap<>();
			int len = s.length(), i; char c;
			for (i = 0; i < len; ++i) {
				c = sentence[i];
				// if (c == ' ') return invalid; // [X] 공백 존재
				if (c >= 'a' && c <= 'z') { // Character.isLowerCase(c)
					if (!chars.containsKey(c))
						chars.put(c, new ArrayList<>());
					chars.get(c).add(i);
				}
			}
			// if (positions.size() == 0) return sentence; // [O] 기호 없음
            
			/** 기호 제거 후 원래 문구로 변환하기 **/
			StringBuilder answer = new StringBuilder();
			int start_string = 0, 
				start_word = 0, end_word = 0, 
				start_char, end_char, 
				start_word_pre = -1, end_word_pre = -1, 
				start_char_pre = -1, end_char_pre = -1, 
				num, distance, rule = 0;
			for (List<Integer> positions : chars.values()) {
				num = positions.size();
				start_char = positions.get(0);
				end_char = positions.get(num - 1);
				// if (start_char_pre != -1 && start_char - start_char_pre < 2)
				// return invalid; // [X] 서로 다른 두 기호가 연달아 존재
                
				/** 기호의 규칙 판단 **/
				if (num == 1 || num >= 3) {
					for (i = 1; i < num; i++)
						if (positions.get(i) - positions.get(i - 1) != 2)
							return invalid; // [X] 규칙1 예외 - 간격 2 아님
					rule = 1;
				} else if (num == 2) {
					distance = end_char - start_char;
					if (distance == 2 && (start_char_pre < start_char && end_char < end_char_pre))
						rule = 1;
					else if (distance >= 2)
						rule = 2;
					else
						return invalid; // [X] 규칙2 예외 - 간격 2보다 작음 (한 기호가 연달아 존재)
				}
				// else {}
                
				/** 규칙에 따른 예외 처리 **/
				if (rule == 1) {
					start_word = start_char - 1;
					end_word = end_char + 1;
					if (start_word_pre < start_word && end_word < end_word_pre) {
						if (start_char - start_char_pre == 2 && end_char_pre - end_char == 2)
							continue;
						else
							return invalid; // [X] 규칙1 예외 - 간격 안 맞음
					}
				} else if (rule == 2) {
					start_word = start_char;
					end_word = end_char;
					if (start_word_pre < start_word && end_word < end_word_pre)
						return invalid; // [X] 똑같은 규칙 중복
				}
				// else {}
				if (end_word_pre >= start_word)
					return invalid; // [X] 단어 간격 안 맞음
                    
				/** 단어 단위로 공백 넣어 문자열 생성 **/
				if (start_string < start_word)
					answer.append(getStr(start_string, start_word - 1) + " ");
				answer.append(getStr(start_word, end_word) + " ");
				start_word_pre = start_word;
				end_word_pre = end_word;
				start_char_pre = start_char;
				end_char_pre = end_char;
				start_string = end_word + 1;
			}
			if (start_string < len)
				answer.append(getStr(start_string, len - 1));
			return answer.toString().trim();
		} catch (Exception e) {
			return invalid; // [X] 그 밖의 예외
		}
	}

	public String getStr(int start, int end) {
		StringBuilder str = new StringBuilder(); char c;
		for (int i = start; i <= end; ++i) {
			c = sentence[i];
			if (c >= 'A' && c <= 'Z')
				str.append(c);
		}
		return str.toString();
	}
}

< 문제 해설 참고 >

( https://tech.kakao.com/2017/08/11/code-festival-round-1/

문제의 조건에 의해, 삽입되는 기호는 총 26가지(알파벳 소문자의 수)이며 각각은 한 번씩만 적용될 수 있습니다. 즉, 각 알파벳의 개수와 위치를 세면 어떤 단어에 어떤 규칙으로 적용되었는지 알 수 있습니다.

기호의 개수가 1개 혹은 3개 이상인 경우, 이 기호는 규칙 1에 의해 추가된 기호임을 알 수 있습니다. 기호의 개수가 2개이면서 사이에 들어간 글자(대문자)의 수가 2개 이상인 경우, 이 기호는 규칙 2에 의해 추가된 기호임을 알 수 있습니다. 기호의 개수가 2개이면서 사이에 들어간 글자의 수가 1개일 때는 규칙 1 혹은 규칙 2가 모두 적용될 수 있는데, 이 경우에도 다음의 유일한 예외를 제외하고는 규칙 2가 적용된 기호로 간주할 수 있습니다. aAbBbCa 즉, 다른 기호의 구간 안에 있는 경우입니다.

즉, 각 기호 별로 개수를 세어, 기호의 개수가 2개가 아닌 경우 규칙 1, 2개인 경우 규칙 2(위에서 설명한 경우 제외)로 적용된 기호로 간주하고 그에 맞게 규칙이 올바르게 적용되었는지를 판단하면 됩니다.

< 문제 접근 + 풀이 >

0. 변수 설명

Type	Name	Description
String	s	입력 받은 문장
char[]	sentence	입력 받은 Struing s를 char[] 로 변환한 것
int	start_string	현재 문자열의 시작 인덱스
	start_word	현재 단어의 시작 인덱스
	end_word	현재 단어의 끝 인덱스
	start_word_pre	이전 단어의 시작 인덱스
	end_word_pre	이전 단어의 끝 인덱스
	start_char	현재 기호의 시작 인덱스
	end_char	현재 기호의 끝 인덱스
	start_char_pre	이전 기호의 시작 인덱스
	end_char_pre	이전 기호의 끝 인덱스
	num	각 기호의 개수
	distance	기호 간 간격
	rule	규칙

1. 입력받은 문자열에서 기호( 소문자 )를 찾아 해당 문자의 위치들을 구함

- 기호가 없으면 문자열 그대로 리턴
- 연결된 해시 맵 생성 -- 기호를 key로 하고 그 기호의 위치 리스트를 value로 한다.
( LinkedHashMap<Character, List<Integer>> chars )
( 데이터를 넣은 순서대로 탐색하기 위함 )
- 기호를 찾을 때마다 chars에는 key에 기호, value에 그 위치(인덱스)들을 넣는다

2. 해시맵를 순차적으로 탐색하며 각 기호의 개수를 각각 구해 규칙1인지 규칙2인지 판단

( 한 기호의 개수 num : 맵의 key안에 있는 value( List )의 size )

  1)  기호( 소문자 )의 개수가 1개 또는 3개 이상
      (1)  기호의 개수가 1개  =>  규칙 1
          ex) A a A, ...
      (2)  기호의 개수가 3개 이상 이고, 각각의 위치 간격이 2 =>  규칙 1
          ex) A a A a A a A, ...
      (3)  그렇지 않은 경우  =>  invalid
          ex) A a a a A, A a A A a A a, ...

  2)  기호의 개수가 2개
      (1)  간격이 2 이며, 다른 기호 안에 있는 경우  =>  규칙 1
         ex)  b A a A a A b, ...
      (2)  간격이 2 이상인 경우  =>  규칙 2
         ex)  a A a,  a A A a, ...
     (3)  그렇지 않은 경우  =>  invalid
        ex)  a a A,  A a a A,  ...

3. 규칙1, 2에 따른 단어의 시작 위치, 끝 위치 구하기 ( + 유효성 검사 )

  1) 규칙 1
    -  단어의 시작 위치 : 기호의 첫 위치 - 1
    -  단어의 끝 위치 : 기호의 마지막 위치 + 1
  ex)  A a A a A a A
     0 1 2 3 4 5 6
- 기호의 첫 위치 : 1
- 기호의 마지막 위치 : 5
- 단어의 시작 위치 : 0
- 단어의 끝 위치 : 6
     *  규칙 1과 규칙 2가 동시에 적용된 단어의 경우
( 현재 기호( 규칙 1 )의 첫 위치와 마지막 위치가
이전 기호( 규칙 2 )의 첫 위치 ~ 마지막 위치 사이에 있을 경우 )
규칙 1 기호와 규칙 2 기호의 양끝의 각각의 간격 또한 2
( 현재 기호의 첫 위치와 이전 기호의 첫 위치 간격이 2 이고,
이전 기호의 마지막 위치와 현재 기호의 마지막 위치 간격이 2 )
        ex)  b A a A a A a A b, ...     *  그렇지 않은 경우 invaild
        ex)  b A A a A a A a A b,  b A a A a A a A A A b,  ...

  2) 규칙 2
    -  단어의 시작 위치 : 기호의 첫 위치
    -  단어의 끝 위치 : 기호의 마지막 위치
ex)   a A A A A a
    0 1 2 3 4 5
- 기호의 첫 위치 : 0
- 기호의 마지막 위치 : 5
- 단어의 시작 위치 : 0
- 단어의 끝 위치 : 5
    *  이전 기호도 규칙2일 경우 invalid ( 같은 규칙 중복 )
        ex)  b A a A A A a A b, ...

* 단, 현재 단어의 시작 위치가 이전 단어가 끝난 위치보다 작거나 같으면 invalid

4. StringBuilder에 단어 단위로 공백을 넣어 추가

- sentence에서 임의의 getStr() 함수를 이용하여 [ 단어의 시작 인덱스 ~ 끝 인덱스+1 ] 의 단어를 잘라 추가
- 규칙을 적용하지 않은 단어가 있을 수 있으므로 [ 문자열의 시작 인덱스 ~ 단어의 시작 인덱스 ],
HashMap 탐색 후 마지막에 [ 문자열의 시작 인덱스 ~ sentence의 끝 인덱스( = sentence의 길이 ) ] 도 추가

5. try-catch 구문을 사용하여 오류가 있을 경우 invaild

< 코드 변경 사항 >

(21/09/02)

HashMap에서 데이터를 넣은 순서대로 탐색하기 위해
List에 순서대로 키값을 넣고 리스트를 탐색하며 HashMap에서 키를 가져왔었다
하지만 LinkedHashMap의 존재를 알고 난 후 List를 없앰.
subString() 함수로 단어 단위로 자르고, replaceAll() 함수로 소문자를 없앴던 코드를
임의의 getStr() 함수를 정의하여 지정한 시작,끝 인덱스의 글자들 중 소문자를 제외하고 StringBuilder에 넣어 리턴하도록 변경

(21/12/08)

변수명을 좀 더 알아보기 쉽게 변경 ( 로직은 같음 )

< 통과 확인 >

'코딩 문제 풀기 ( Algorithm problem solving ) > 프로그래머스 ( Programmers )' 카테고리의 다른 글

[프로그래머스(Programmers)][자바(java)] (Lv3) 리틀 프렌즈 사천성 (0)	2021.01.13
[프로그래머스(Programmers)][자바(java)] (Lv3) 보행자 천국 (0)	2021.01.13
[프로그래머스(Programmers)][자바(java)] (Lv3) 숫자 게임 (0)	2021.01.06
[프로그래머스(Programmers)][자바(java)] (Lv3) 기지국 설치 (0)	2021.01.06
[프로그래머스(Programmers)][자바(java)] (Lv3) 배달 (0)	2021.01.06