코딩테스트

문제https://www.acmicpc.net/problem/4889  풀이단순히 스택을 사용하여 풀 수 있는 문제이다. 유명한 괄호 문제랑 거의 똑같은 문제긴 하다. 여는 괄호가 나오면 무조건 스택에 넣어준다. 그리고 빈 경우에 닫는 괄호라면, 여는 괄호로 바꿔줘서 넣어준다.스택에 } 이런 값이 하나 있어봤자 이 값은 여는 괄호일때만 사용할 수 있다. 그렇기 때문에 바꿔준 상태로 넣어준다. 그 외에 비지 않았는데 닫는 괄호라면, 스택에는 무조건 여는 괄호가 있기 때문에 짝이 맞는다.그렇기 때문에 여는 괄호를 빼주면 된다. 이 과정을 다 수행후에도 스택에 값이 남아있다면 이는 모두 여는 괄호일것이다. 수는 무조건 짝수로, 짝이 맞을거니까 {{{{ 이런 경우나 {{ 이런 경우가 있을것이다.하나만 닫는 괄호..

문제https://www.acmicpc.net/problem/2841  풀이맵과 우선순위큐를 활용해서 풀었다. (근데 우선순위큐 말고 스택 쓰는게 2억배는 맞는 접근이다.) Map 의 Key 는 기타줄로 하고, Value 를 플랫을 넣고 관리하는 우선순위 큐로 만든다. 플랫 같은 경우에는 같은 줄일때, 더 높은 플랫이 나오면 손가락을 추가(?)만 해주면 된다. (우선순위 큐에 플랫을 추가해주면 된다.) 단 낮은 플랫일 경우에는 입력으로 들어온 플랫보다 큰 값이 같은 줄에 있으면 안된다.따라서 우선순위 큐의 가장 큰 값을 보고 비교해본다음, 우선순위 큐의 가장 큰 값이 입력값보다 같거나 작을 때 까지 값을 빼준다. 그 다음이 중요한데, 같은 값인 경우에는 손가락을 추가해줄 필요가 없다. 이미 플랫을 짚고 ..

문제https://www.acmicpc.net/problem/6198  풀이스택을 활용해야 하는 문제이다. N이 8만이므로, 완탐은 당연히 안된다. 앞에서부터 스택에 데이터를 넣는데, 이때 빌딩번호와 높이를 같이 넣는다.다음 빌딩이 스택의 가장 위의 빌딩보다 낮으면 그냥 넣어준다. 만약 다음 빌딩이 만약 더 크다면? 스택에서 빼서, 빌딩 번호의 차를 구하고 답에 더해주면 된다. 스택에서 빼는 과정을 자신보다 낮은 빌딩이 나올때까지 반복하면 된다. 그렇게 끝까지 반복적으로 수행한다음에, 스택에 남아있다면 남아있는 빌딩들은 오른쪽 끝까지 볼 수 있는 빌딩이므로 값을 계산해서 답에 추가해주면 된다. 코드import java.util.*;import java.io.*;/** * [문제] (https://www...

문제https://www.acmicpc.net/problem/2002  풀이추월의 요점을 잘 생각해봐야한다. 난 처음에 들어가는 순서보다 나오는 순서가 빠른 순으로만 생각했는데 바로 틀렸다. 요는, 내 뒤에 있던 차량이 내 앞으로 갔는가? 이다. 게시판에 반례가 a        db        ac        cd        b 가 있었다. (왼쪽 줄이 들어간 순서, 오른쪽 줄이 나온 순서) 나오는 순서대로 체킹하면 d 하나만 체크가 될 것이다. 그러나 내 뒤에 있던 차량이 내 앞으로 간 것을 체크하면 d 와 c 2개가 있다. 우선 차량이 들어온 순서대로 리스트로 데이터를 받는다. 나가는 순서는 해쉬맵을 이용해서 로 저장한다. 해쉬맵을 이용하지 않으면 리스트에서 내 뒤에 있는 차량이 내 앞에 있는..

문제https://www.acmicpc.net/problem/14719  풀이접근을 어떻게 하다가 좀 고민하다가, 나는 가장 긴 블록 기준으로 판별했다.  가장 긴 블록을 기준으로, 아래부터 좌우를 검사하면 빈 공간 찾아내기가 용이하다. 가장 높기 때문에 좌우로 빈 공간이 보이면 카운트하고, 그러다가 같은 행에 블록이 생기면 그 사이에 생긴 빈공간을 더해주면 된다. 빈공간이 계속 나왔지만 블록이 나오지 않았다면 옆면이 없는 것이므로 더하지 않으면 된다. 나는 입력을 받고, 2차원 배열로 형태를 잡았다. 그 다음 가장 큰 블록을 가지고 있는 x 좌표에서 가장 밑의 행부터 좌우로 검사하며 위쪽으로 올라갔다.  코드import java.util.*;import java.io.*;/** * [문제] (https..

문제https://www.acmicpc.net/problem/2615 풀이모든 오목칸을 순회하면서 오목이 있는지 검사하면 된다. 단 신경써야하는 부분이 크게 두가지가 있다. 1. 오직 세로일때는 가장 위의 돌 출력, 그 외에는 좌측 돌 출력 이 조건에서 대각선인 경우에도 가장 왼쪽 돌을 출력해야한다. 오로지 세로로 일자로 오목일때만 가장 위의 돌을 출력하고, 그 외에는 다 왼쪽돌이다. 그리고 이 조건을 만족하기 위해서는 순회를  → ↓ 순서가 아니라 ↓ → 순서로 순회하며 오목을 검사해야한다. 그래야지 세로일때는 가장 위의 오목돌에서 오목을 발견할 수 있고, 그 외에 대각선이나 가로일때도 왼쪽 돌부터 체킹하기 때문이다.  2. 6 목 검사 6목일 경우에는 취급하지 않는다. 6 목을 검사하기 위해서는 양쪽..

문제https://www.acmicpc.net/problem/13335 풀이https://whiporithm.tistory.com/131 LV2 - 다리를 지나는 트럭 (Java)문제 https://school.programmers.co.kr/learn/courses/30/lessons/42583 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이whiporithm.tistory.com 이 문제와 완전 동일하다!    코드import java.util.*;import java.io.*;/** * [문제] (https://www.acmicpc.net/problem/13335) */public class Main { publ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/159993 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  풀이전형적인 bfs 문제이다. 출발점에서 레버까지 도달한다음, 레버에서 다시 출구까지 도달하도록  2번을 나눠서 bfs를 수행하면 된다. 탐색하면서 거리를 계속 체크하다가, 타겟칸(레버나 출구칸) 으로 이동하면 그만큼의 거리를 반환하도록 bfs를 구성하면 된다.  참고로 나는 시작점을 0이 아닌 1로 줘서 시작했기 때문에 마지막에 반환할 때 -2를 빼줬다. (bfs를 두번 수행하기에)  코드..

문제https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이전~형적인 bfs 문제이다.사실 크게 얘기할 거리도 없이 방문 2차원 배열을 두고 방문했는지, X가 아닌지를 검사하고 가능한 곳에서 모두 탐색하면서 방문 체크를 한다음 더해진 값을 반환해준다. 이후 정렬만 해주면 끝이난다. 조금 신경쓴거는 char을 어떻게 int형으로 만드나였는데, 아스키코드로 계산해서 48을 빼주면 깔끔하게 값 처리가 가능했다.코드import java.util.*;clas..

문제https://school.programmers.co.kr/learn/courses/30/lessons/155651 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이우선 생각났던건 시작시간부터, 끝시간까지 1분 단위로 카운트를 하는것이었다.그 시간동안 몇개의 객실이 필요한지 파악하고 00:00 부터 23:59까지 모두 돈다음 가장 큰 수를 리턴하면 될거라 생각했다. 컨셉은 이렇게 잡았고, 초반에는 진짜 시간처럼 계산을 했었는데, 분기처리도 너무 까다롭고 퇴실 시간 이후 10분 처리도 까다로워서 생각을 바꿨다. 시간에 * 60 을 하고 분을 더하는 방식으..