짝지어 제거하기 / 프로그래머스 연습문제 / programmers / level2 / Java

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

코딩테스트 연습 - 짝지어 제거하기

---

역시 레벨2는 쉽게 풀리지 않는다.

 

1레벨 처럼 for, if, while 만으로도 풀수는 있겠으나, 효율성 측면에서 실패한다. 하여 본격적으로 자바의 Stack을 활용해보기로 했다.

 

[알고리즘 flow]

1. Stack 선언

2. 문자열의 길이만큼 for 문 실행

3. Stack이 비어있으면 push

4. 맨위의 스택과 s.charAt(i) 비교

5. 비교하여 같으면 삭제, 틀리면 푸시

 

[작성코드]

import java.util.Stack;

public class DelPair {

	public static void main(String[] args) {
		DelPair res = new DelPair();
		res.solution("baabaa");

	}

	public int solution(String s) {
        int answer = -1;
        
            Stack<String> room = new Stack<String>();

        int pointer = 0;
         
        for (int i = 0; i < s.length(); i++) {
			System.out.println(room.isEmpty());
			System.out.println("room : " + room);
			System.out.println("i : " + i + " pointer : " + pointer);
			if (room.size() == 0) {
				room.push("" + s.charAt(i));
				pointer = 0;
			} else {
				String pop = room.pop();
				if (pop.equals("" + s.charAt(i))) {
					pointer--;
				} else {
					room.push(pop);
					room.push("" + s.charAt(i));
					pointer++;
				}
			}
			
			
			

		}
		
		if (room.size() == 0) {
			answer = 1;
		} else {
			answer = 0;
		}
		System.out.println(room);
		System.out.println(answer);
           return answer;
        	
        }
        
	
}

처음에는 문자열을 Arrays.asList(s.split("")) 으로 List에 담아준다음 리스트의 사이즈만큼 반복문을 통해 제출하였는데,

효율성테스트에서 번번히 막혔다.

 

하여 문자열 자체를 가지고 비교를 했는데 수월하게 풀렸다.

 

한가지 신기한점은 List는 문자열이 짧을 수록 처리속도가 빠르고, 문자열 그 자체는 문자열이 길수록 List에 비해 처리속도가 빠른 것이었다. 시간복잡도 O(n) 과 관련있는 것 같은데... 아직 100% 이해는 잘 되지 않는다.

문제나 더 풀자... 끝

 

---

[깃허브링크]

https://github.com/RUCKUSJERRY/practiceOfAlgorithm/blob/c494ae423e3a6a33cfb24751f2180ddb18d40d9f/Prs_Pratice/src/com/level02/DelPair.java

GitHub - RUCKUSJERRY/practiceOfAlgorithm