백준 3015 오아시스재결합

노문택·2022년 3월 17일
0

엥 ? 님 골3 골2 어디가고 골1로 넘어옴??

골3 오등큰수 문제는 오큰수에서 그냥 등호조건 비교 넣은 버전이여서 골3이랑 골4가 별다를바가없음..
추가적으로 골2도 같은 포맷이라 골1을 도전해보았다..

결과는 처참했지만..그래도 정리를 위해 기록.. 골1~골2 문제 하나를 더 풀어봐야겠다..

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

문제 설명

  1. A-B 두 인덱스를 골른다.
  2. A-B 인덱스 사이에 A와 B보다 작거나 같은 값을 가지고있는 쌍 A,B를 구하시오
    EX ) 1 3 2 4 이 있다고가정
    1과 2를 고르면 그사이에 3이 조건 부합하지 않으므로 X
    3과 4를 고르면 그사이에 2가 조건에 해당하므로 개수 카운팅

풀이 방법

  1. 클래스 만들어주기 (높이 , 갯수)
  2. 스택의 구성상 역순출발 ?? X
  3. 입력을 받으면서 받을때 그때 스택 검사를 진행

    2.1 스택이 비어져 있다면 그대로 넣고 갯수카운팅 X
    2.2 스택이 채워져 있다면 top을 현재 값과 비교
    2.2.1 현재값보다 크다 => 여기서보면 2라는 값은 결국 3이라는 벽에 막혀서 1이랑 매칭을 못할것이므로 => 1이라는 스택 제거 => 그래도 1쌍은 만들어지니까 갯수 1개만 더해주기
    2.2.2 현재값과 같다 => 스택에서 꺼내기 => 같은 값끼리는 스택에 들어있는 값의 갯수 최신화 해주기 => 그래도 쌍은 만들수있으니까 현재 쌍이 만들수있는 갯수만큼 더해주기
    2.2.3 현재값보다 작다 => 스택에서 꺼내기 => 쌍은 만들수 있으니까 현재쌍이 만들수있는 갯수만큼더해주기
    3. 검사가 끝난 현재 번호를 스택에 넣어주기

소스코드

import java.io.*;
import java.util.*;

public class Main {

// 저장할 타입
	static class people{
		int height;
		int count;
		public people(int height, int count) {
			this.height = height;
			this.count = count;
		}
		
	}
    
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int k = Integer.parseInt(br.readLine());
		long answer = 0;
        //저장할스택
		Stack<people> s =new Stack<>();
        // 진행
		for(int i=0;i<k;i++) {
        //입력받기
		int cur = Integer.parseInt(br.readLine());
        // 본인과 매칭 성공시 갯수니까 1로 초기화
		people cp = new people(cur,1);
		while(!s.isEmpty()) {
        //위에 꺼내오기
		people sp = s.peek();
			if(sp.height==cur) { // if문으로 값이 같으면 꺼내고 현재꺼의 갯수 ++
				answer += sp.count;
				cp.count += sp.count;
				s.pop();
				continue;
			}
            // 안에 들어있는게 더크면 거기있는 1개만 매칭이 가능하므로 1개 ++ 후 종료
			else if(sp.height>cur) {
				answer ++;
				break;
			}
            // 작거나 같은경우에는 갯수만큼 매칭이 가능하니까 count 갯수만큼 더해줌
			answer += sp.count;
			s.pop();
		}
        //만든 cp 넣어주기
		s.add(cp);
		}
		System.out.println(answer);

	}

}

결과.. 너무많이 실패했따 ㅠ

profile
노력하는 뚠뚠이

0개의 댓글