→ Problems

문제 소개 17299번: 오등큰수첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.www.acmicpc.netAi가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다. 설명하기가 좀 복잡해서 아래 문제 캡처를 첨부한다. 문제 풀이처음 등장한 횟수를 어떻게 저장할까 고민했는데, 가장 효율적으로 접근이 가능한 데이터 구조는 딕셔너리 구조라고 생각했다. 따라서 아래와 같이 딕셔너리에 반복되는 횟수를 저장해 줬다.l..

문제 소개 10799번: 쇠막대기여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저www.acmicpc.net아래와 같이 ()로 이루어진 문자열이 주어졌을 때, 막대기는 몇조각으로 나뉠수 있는지를 물어보는 문제이다. 문제 풀이텍스트 대치 활용레이저를 "-" 로 바꿔준다음 "(" 가 나오게 된다면 막대기의 갯수를 더해주고, ")" 가 나오게 된다면 막대기의 갯수를 빼주고 count에 1을 더해주면 된다. 그리고 "-" 레이저가 나왔을때에는 총 조각의 count에 현재 막대기의 갯수를 더해준다. replacingOccurrences라는 것을 활용하면 쉽게 풀 수 있다.import..

문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제가 아주 심플한데, n명의 병사, k번의 무적권(?)을 가지고 enemy 배열이 주어졌을 때 최대 몇 라운드까지 갈 수 있는지를 구하는 문제였다. 문제 풀이 과정 문제 접근은 아래와 같다. 우선 무적권를 초반에 몰아서 쓴다. 그리고 그것을 stack에 넣어서 stack의 요소 중에 가장 적은 요소보다 큰 enemy가 나왔을 때 무적권을 취소하고, 그 enemy에 무적권을 쓰고, 그 제일 작은 요소에 병사를 사용하는 것으로 문제를 해결했다. 일종의 그리디 알고리즘 느낌이랄까...? 그때그때 최적을..

문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 시소 짝궁을 구하는 문제인데, 시소의 길이는 2, 3, 4가 있다. 만약 무게가 [100,180,360,100,270] 라고 한다면 [100, 100]은 시소 짝궁이 되고, [180, 360]도 4, 2길이에 앉게된다면 시소 짝궁이 된다. 문제 풀이 무게의 배열이 10만개가 주어지기 때문에 이중 for문을 하기에는 시간초과가 확실했다. 어떻게 하면 for문을 중복해서 사용하지 않을 수 있을까? 생각보다 정말 간단하게 접근이 가능했다. 우선 same 배열, multi 배열을 만들어서 무게의 최댓값이 ..

문제 소개 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 숫자의 배열이 주어지면 자신보다 뒤에 있는 숫자 중에 자신보다 크면서 가장 가까이 있는 수로 바꾸고 없다면 -1로 바꾸는 문제이다. 예를 들면 [2, 3, 3, 5]가 주어지면 [3, 5, 5, -1]을 출력해야 한다. 문제 풀이 뒤에 있는 숫자 중 자신보다 크면서 가장 가까이 있는 수라는 점에서 뒤에서 접근해야 한다는 힌트를 얻었다. 자기와 가장 가까워야 한다는 조건이 있어 정렬은 의미가 없다. 뒤에서부터 접근하면서 가장 마지막 값과 비교가 필요하다는 점에서 stack구조를 떠올렸다. 아이디어는 ..

문제 소개 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 아래와 같은 미로가 ["SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"] 와 같은 형태로 주어지고, L을 방문했다가 E를 방문하는 최소의 이동거리를 구하는 문제이다. 문제 풀이 (DFS, 실패) 처음 문제풀이는 가로, 세로 길이의 범위가 5 이상 100 이하인 조건이 있었기 때문에 숫자가 충분히 크지 않아서 DFS로 충분히 풀 수 있지 않을까? 하는 생각이 들었다. (보통 이런 최단거리문제는 BFS가 맞다) 아무튼 나는 move라는 재귀함수를 만들었다. 재귀함수의 탈출조건에 시..

문제 소개 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr N개의 마을이 있고, 이 마을간에는 도로가 연결되어있다. 그리고 각 마을간 최소거리가 k이하인 마을의 갯수를 구하는 문제이다. 플로이드-워셜이나 다익스트라 알고리즘을 사용하면 아주 손쉽게 풀 수 있다. 나는 플로이드-워셜 알고리즘을 사용했다. 하지만 이것은 너무나도 치트키 같은 느낌... 특히 문제를 풀어본뒤 질문들을 보는 습관이 생겼는데 BFS, DFS로도 충분히 풀수있는 사이즈이기 때문에 도전해보고자 했다. 플로이드 워셜 알고리즘 아주아주 코드가 쉽다. 3중 for문만 시원하게 써주면 문제풀이 ..

문제 소개 정말 정말 유명한 문제 중 하나인 "하노이의 탑" 문제. 이 문제를 풀면서 정말 점화식, 재귀함수에 관련된 깊은 생각을 한 것 같다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 아래와 같이 세 개의 기둥이 있고, 크기가 큰 원판부터 기둥에 꽂혀있다. 이제 이것을 크기가 작은 원판이 크기가 큰 원판보다 아래로 가지 않게 하면서, 한 번에 하나의 원판을 이동하며 세 번째 기둥으로 옮길 때 최소로 옮기는 방법을 return 하는 문제였다. 예를 들면, 2를 입력하게 된다면 2개의 원판이 1번에 있고, 이 원판을 세 번째 기둥으로 최소로 옮기는 방..